# How to Use the DFT (FFT) to Solve a Least Squares Regularization Problem (Inverse Problem)?

Let $X$ and $K$ be an image and a Point Spread Function (PSF), respectively.

The blur image $B$ is obtained as follows

$$B = X * K$$

I want to solve the following general regularization problem

$$\min_X \left\|X * K - B\right\|_2^2 + \lambda \| f(X) \|_2^2$$

where $f$ is a regularization function. In some literature I have seen, the authors use the FFT to solve such a problem. However, I cannot find any resources that show the procedure. My questions are:

1. How one can use FFT to solve the above problem?
2. Is there any condition that must be satisfied to use FFT?
• The problem itself has an optimization based solution, I believe the literature you had mentioned use FFT for calculating PSF. – MimSaad Oct 30 '17 at 7:15
• Does $*$ denote convolution? What does "PSF" stand for? – Rodrigo de Azevedo Oct 30 '17 at 10:01
• It would be much easier for us if you can cite some literatures where authors use FFT. – AlexTP Oct 30 '17 at 10:23
• @Azevedo Yes. Point Spread Function. Also blurring kernel. – user153245 Oct 30 '17 at 11:57
• You could use fourier transform to pose this as an optimization problem in frequency domain (convolution turns into multiplication). – Atul Ingle Oct 30 '17 at 15:33

The question really depends on $$f \left( \cdot \right)$$.
Yet in order to show how to use FFT we can even use 1D signals.

Let's rewrite the problem:

$$\hat{x} = \arg \min_{x} \frac{1}{2} \left\| K x - b \right\|_{2}^{2} + \frac{\lambda}{2} \left\| f \left( x \right) \right\|_{2}^{2}$$

The derivative is given by:

$$g = {K}^{T} \left( K x - b \right) + \lambda f' \left( x \right)^{T} f \left( x \right)$$

Now, $$K$$ as a matrix is given by a Circulant Convolution Matrix.
Hence the operation $$K v$$ or $${K}^{T} v$$ can be done in the Fourier Domain.
Under some circumstances it might accelerate the operation significantly.