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

Question

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?

Answer 1

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.