# How applying the gradient descent method for solving a least square problem can remove the blur from an image?

I got an assignment where it asked to implement (in MATLAB) the gradient descent algorithm in order to resolve an ill posed least square problem:

$$\min_u \Vert Gu - f \Vert$$

where $$u$$ is the reconstructed image, $$G$$ is the blur applied to $$u$$ and $$f$$ is the blurred image.

I have successfully implemented it with MATLAB, it is effectively removing a portion of the applied blur, but I do not understand why applying a gradient descent method to this ill posed least square problem can effectively remove the blur from an image.

• shouldn't this be $\min_u$ not $\min_f$?
Dec 12, 2020 at 13:58
• The answer is because you're solving the equation $G u = f$. In other words, you're finding an image $u$ that when blurred produces $f$
Dec 12, 2020 at 14:00
• I assume it should also minimize the square of the norm. Dec 12, 2020 at 19:02
• I have to admit that I don't understand the question. Why would it not remove the blur? Dec 12, 2020 at 19:02
• How badly conditioned is the $G$ matrix? If it's not badly conditioned, then gradient descent should work (albeit slowly) to minimize the difference between Gu and f. Dec 12, 2020 at 21:51

The problem is equivalent to:

$$\arg \min_{\boldsymbol{u}} \frac{1}{2} {\left\| \boldsymbol{G} \boldsymbol{u} - \boldsymbol{f} \right\|}_{2}^{2}$$

The solution is given by $$\hat{\boldsymbol{u}} = {\left( \boldsymbol{G}^{T} \boldsymbol{G} \right)}^{-1} \boldsymbol{G}^{T} \boldsymbol{f}$$.
Basically inverting the operation of $$\boldsymbol{G}$$ on $$\boldsymbol{f}$$.

The Gradient Descent is just a way to solve the problem.
So once it is converged, it is equivalent to the closed form solution.

Remarks

• If you solve this actual formulation of the problem, Gradient Descent is a poor choice as it is slow. You may improve it with some acceleration (Momentum / Nesterov) or use Conjugate Gradient.
• This is an inverse problem. In practice it is usually solved with added regularization.
• Also gradient descent has poor convergence - it is equivalent to a Richardson iteration/explicit Euler which are one of the simplest and slowest methods (at least without acceleration strategies). They ought to use the conjugate gradient for the normal equations or variants of it. Jul 14, 2023 at 8:50