Euler-Lagrange, Gradient Descent, Heat Equation and Image Denoising

For an image denoising problem, the author has a functional $E$ defined

$$E(u) = \iint_\Omega F \;\mathrm d\Omega$$

which he wants to minimize. $F$ is defined as

$$F = \|\nabla u \|^2 = u_x^2 + u_y^2$$

Then, the E-L equations are derived:

$$\frac{\partial E}{\partial u} = \frac{\partial F}{\partial u} - \frac{\mathrm d}{\mathrm dx} \frac{\partial F}{\partial u_x} - \frac{\mathrm d}{\mathrm dy} \frac{\partial F}{\partial u_y} = 0$$

Then it is mentioned that gradient descent method is used to minimize the functional $E$ by using

$$\frac{\partial u}{\partial t} = u_{xx} + u_{yy}$$

which is the heat equation. I understand both equations, and have solved the heat equation numerically before. I also worked with functionals. I do not understand however how the author jumps from the E-L equations to the gradient descent method. How is the time variable $t$ included? Any detailed derivation, proof on this relation would be welcome. I found some papers on the Net, the one by Colding et al. looked promising.

References:

http://arxiv.org/pdf/1102.1411 (Colding et al.)

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.1675&rep=rep1&type=pdf

http://dl.dropbox.com/u/1570604/tmp/functional-grad-descent.pdf

http://dl.dropbox.com/u/1570604/tmp/gelfand_var_time.ps (Gelfand and Romin)

Solution 1:

You should note that a solution, $f$, to your differential equation, $\mathcal{L}[f] = 0$, is the steady state solution to the second equation, as $\partial_t f = 0$. By turning this into a parabolic equation, only the error term will depend on $t$, and it will decay with time. This can be seen by letting

$$h(x,y,t) = f(x,y) + \triangle f(x,y,t),$$

where $f$ is as before. Then

$$\mathcal{L}[h] = \mathcal{L}[\triangle f] = \partial_t \triangle f$$

In general, this method makes the equations amenable to minimization routines like steepest descent.

Edit: Since you mentioned that you wanted a book to reference, when I was taking numerical analysis, we used v. 3 of Numerical Mathematics and Computing by Cheney and Kincaid, and I found it very useful. Although, at points it lacked depth, however it provided a good jumping off point. They also have a more mathematically in depth book Numerical analysis: mathematics of scientific computing that may be useful to you, which I have not read.

Solution 2:

This is essentially a matter of definitions. The steepest descent gradient flow of a functional $F$ in an inner product space $S(M,N)$ (for example) is a family $u:M\times [0,T)\rightarrow N$ which satisfies $$ \partial_t F = - \lVert u_t \rVert^2. $$ For example, suppose $\Sigma$ is a surface immersed in $\mathbb{R}^3$ (for simplicity) via an immersion $f:M\rightarrow\mathbb{R}^3$ and consider the Willmore functional $$ \mathcal{W}(f) = \frac{1}{2}\int_M H^2 d\mu, $$ where $H$ is the mean curvature of $M$. We wish to compute from this functional, the Willmore flow, which is the steepest descent gradient flow in $L^2(M,\mathbb{R}^3)$. To do this, one computes the first variation of $\mathcal{W}$ along normal variations of $f$ (the Willmore functional is invariant under tangential diffeomorphisms, (among other things) which are essentially reparametrisations).

Now, any critical point of the functional will have zero first variation. This is a simple fact from basic calculus. The equation "first-variation = 0" is the Euler-Lagrange equation. It is a necessary condition that all minimal points of the functional must satisfy, although it is not in general sufficient.

The Euler-Lagrange equation is $$ \Delta H + H|A^o|^2 = 0, $$ where $A^o$ is the tracefree second fundamental form. A detailed explanation of how one derives this equation can be found in the back of Riemannian Geometry by Willmore. Any immersion satisfying this equation is a critical point of the Willmore functional and is called a Willmore surface.

Finally, suppose we have a one-parameter family of immersions $f:M\times[0,T)\rightarrow\mathbb{R}^3$ satisfying $$ \partial_t^\perp f = \Delta H + H|A^o|^2. $$ Along this family of immersions we have $$ \partial_t\mathcal{W} = -\int_M |\Delta H + H|A^o|^2|^2 d\mu, $$ and thus it is by definition the steepest descent gradient flow of $\mathcal{W}$ in $L^2$. Usually one doesn't bother writing all that (or any of it) and just goes directly from the Euler-Lagrange operator in some function space to the gradient flow, since it is quiet straightforward.