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?
  • $\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 '17 at 7:15
  • 1
    $\begingroup$ Does $*$ denote convolution? What does "PSF" stand for? $\endgroup$ – Rodrigo de Azevedo Oct 30 '17 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 '17 at 10:23
  • $\begingroup$ @Azevedo Yes. Point Spread Function. Also blurring kernel. $\endgroup$ – user153245 Oct 30 '17 at 11:57
  • 1
    $\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 '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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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