# Speed up minimizing quadratic function by FFT

I'm trying to understand the following excerpt from a paper:

Subproblem 1: computing $S$. The $S$ estimation subproblem corresponds to minimizing $$\sum_{p}(S_p - I_p)^2 + \beta((\partial_xS_p - h_p)^2 + (\partial_yS_p - v_p)^2) \tag {7}\label{7}$$ by omitting the terms not involving $S$ in Eq $(6)$. The function is quadratic and thus has a global minimum even by gradient descent. Alternatively, we diagonalize derivative operators after Fast Fourier Transform (FFT) for speedup. [Emphasis added] This yields the solution $$S = \mathscr{F}^{-1} \left( \frac{\mathscr{F}(I) + \beta(\mathscr{F}(\partial_x)^*\mathscr{F}(h) + \beta(\mathscr{F}(\partial_y)^*\mathscr{F}(v))}{\mathscr{F}(1) + \beta(\mathscr{F}(\partial_x)^*\mathscr{F}(\partial_x) + \beta(\mathscr{F}(\partial_y)^*\mathscr{F}(\partial_y))} \right) \tag{8}\label{8}$$ where $\mathscr{F}$ is the FFT operator and $\mathscr{F}^*$ denotes the complex conjugate. $\mathscr{F}(1)$ is the Fourier transform of the delta function. The plus, multiplication, and division are all component-wise operators. Compared to minimizing Eq. $\eqref{7}$ directly in the image space, which involves very-large-matrix inversion, computation in the Fourier domain is much faster due to the simple component-wise division.

I don't understand how Eq.(8) was derived. How can FFT speed up gradient descent?

Cited by

"Image Smoothing via L0 Gradient Minimization" Li Xu, Cewu Lu, Yi Xu, Jiaya Jia  ACM Transactions on Graphics, Vol. 30, No. 5 (SIGGRAPH Asia 2011), Dec 2011

pdf link in page 4

• Alternatively, wait for the fussy, semi-obsessive editors like me to take a look at it. :D – DylanSp May 3 '16 at 20:24
• @D.W. Can I post this question to the other site, like math.stackexchange.com ? – Yu Dai May 4 '16 at 3:48
• @YuDai, thanks for asking! cross-posting the same question on multiple SE sites is not allowed. (Each community should have an honest shot at answering without anybody's time being wasted.) However, if you'd prefer to see the question migrated to a different site, you can delete it here and post it there, or flag it for moderator attention (via "flag" under the post) and ask the moderators to migrate it there. – D.W. May 4 '16 at 4:45