# 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://dl.dropbox.com/u/1570604/tmp/gelfand_var_time.ps (Gelfand and Romin)

-
Struwe's "Variational Methods" and the joint work "Six themes on variation" are good places to look for general calculus of variations material. –  Glen Wheeler Mar 29 '11 at 14:29
Glen Wheeler and rcollyer already gave good answers. Let me just comment on two things: (a) the main reason why you ignore the EL equations is that it is easier to numerically solve a parabolic equation then an elliptic one (b) you can try to visualize this is finite dimensional spaces (instead of $\infty$-dim function space): on a hilly terrain, you want to find a local minimum of altitude. One way is to just follow the curve of steepest descent, which you find by taking the gradient of the height function of the terrain... –  Willie Wong Mar 29 '11 at 18:47
@Willie Wong: my only addition here is Willmore surfaces, Riemannian geometry are a bit more than I planned to get in right now. I was looking for something I could use based on my basic var. calculus, diffn eqns knowledge. I do appreciate both answers. –  BB_ML Mar 29 '11 at 21:57
@user6786 It's just an example. As an exercise you might want to try verifying that the mean curvature flow (with speed $\partial^\perp_tf = -H$) is the steepest descent gradient flow of the area functional. A good survey paper which is very readable with a numeric bent and which has AFAIR most computational details within is Deckelnick, Dziuk, Elliot "Computation of geometric partial differential equations and mean curvature flow" in Acta Numerica. You are going to want to learn some Riemannian geometry in the future, for sure. –  Glen Wheeler Mar 30 '11 at 8:26

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.

-
I now have the first Cheney et al book; thx. –  BB_ML Mar 29 '11 at 21:32

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.

-
I am looking at Wilmore's book right now, thanks for the answer and the reference. –  BB_ML Mar 29 '11 at 21:31