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?
  • $\begingroup$ The problem itself has an optimization based solution, I believe the literature you had mentioned use FFT for calculating PSF. $\endgroup$
    – MimSaad
    Oct 30, 2017 at 7:15
  • 1
    $\begingroup$ Does $*$ denote convolution? What does "PSF" stand for? $\endgroup$ Oct 30, 2017 at 10:01
  • $\begingroup$ It would be much easier for us if you can cite some literatures where authors use FFT. $\endgroup$
    – AlexTP
    Oct 30, 2017 at 10:23
  • $\begingroup$ @Azevedo Yes. Point Spread Function. Also blurring kernel. $\endgroup$
    – user153245
    Oct 30, 2017 at 11:57
  • 2
    $\begingroup$ You could use fourier transform to pose this as an optimization problem in frequency domain (convolution turns into multiplication). $\endgroup$
    – Atul Ingle
    Oct 30, 2017 at 15:33

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.