FFT based solution for multivariable L2 equations using KKT system via FFT and efficient pixel-wise inverse calculation

摘要

When solving l2 optimization problems based on linear filtering with some regularization in signal/image processing such as Wiener filtering, the fast Fourier transform (FFT) is often available to reduce its computational complexity. Most of the problems, in which the FFT is used to obtain their solutions, are based on single variable equations. On the other hand, the Karush-Kuhn-Tucker (KKT) system, which is often used for solving constrained optimization problems, generally results in multivariable equations. In this paper, we propose a FFT based computational method for multivariable l2 equations. Our method applies a FFT to each block of the KKT system, and represents the equation as an image-wise simultaneous equation consisting of Fourier transformed filters and images. In our method, an inverse matrix calculation that consists of complex pixel values gathered from each transformed image is required for each pixel. We exploit the homogeneity of neighboring values and solve them efficiently.