# 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 blurred 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 (e.g. Blur kernel estimation via salient edges and low rank prior for blind image deblurring) 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. Oct 30, 2017 at 7:15
• Does $*$ denote convolution? What does "PSF" stand for? Oct 30, 2017 at 10:01
• It would be much easier for us if you can cite some literatures where authors use FFT. Oct 30, 2017 at 10:23
• @Azevedo Yes. Point Spread Function. Also blurring kernel. Oct 30, 2017 at 11:57
• You could use fourier transform to pose this as an optimization problem in frequency domain (convolution turns into multiplication). Oct 30, 2017 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.