1
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ shouldn't this be $\min_u$ not $\min_f$? $\endgroup$
    – wlad
    Commented Dec 12, 2020 at 13:58
  • $\begingroup$ 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$ $\endgroup$
    – wlad
    Commented Dec 12, 2020 at 14:00
  • $\begingroup$ I assume it should also minimize the square of the norm. $\endgroup$
    – Wolfgang Bangerth
    Commented Dec 12, 2020 at 19:02
  • 3
    $\begingroup$ I have to admit that I don't understand the question. Why would it not remove the blur? $\endgroup$
    – Wolfgang Bangerth
    Commented Dec 12, 2020 at 19:02
  • $\begingroup$ 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. $\endgroup$
    – Brian Borchers
    Commented Dec 12, 2020 at 21:51

1 Answer 1

Reset to default
2
$\begingroup$

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.
Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Commented Jul 14, 2023 at 8:50
  • $\begingroup$ @lightxbulb, I agree. Please feel free to edit the answer and add your insightful remarks. $\endgroup$
    – Royi
    Commented Jul 14, 2023 at 8:53
  • 1
    $\begingroup$ Feel free to add it in. I feel uncomfortable editing other's people posts. It's probably also fine if it stays in the comments. $\endgroup$
    – lightxbulb
    Commented Jul 14, 2023 at 8:54
  • $\begingroup$ @lightxbulb, By the way, in practice you'd usually solve such inverse problem with some regularization. Then, I think, CG becomes irrelevant, right? $\endgroup$
    – Royi
    Commented Jul 14, 2023 at 8:54
  • 2
    $\begingroup$ @lightxbulb. I agree. It is not in the question. Just practically you'd add regularization. Anyhow, found what I looked for. See dsp.stackexchange.com/questions/87500. At the bottom of my answer I link to a paper using CG for Total Variation regularization. $\endgroup$
    – Royi
    Commented Jul 14, 2023 at 9:04

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.