Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For a image denoising problem (below):

http://www.bekirdizdaroglu.com/ceng/Downloads/ISCE10.pdf

the author has a functional E defined

$E(u) = \int\int_\Omega F \\ 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{d}{dx} \frac{\partial F}{\partial u_x} - \frac{d}{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 (ROF)

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)

share|improve this question
3  
They got published for this in 2010?! Look at Lena's feather hat and the castle image in the results. Denoising by solving the heat equation worsens the image by blurring the edges. There are thousands of papers on how to fix this (cf en.wikipedia.org/wiki/Total_variation_denoising, dx.doi.org/10.1016/0167-2789(92)90242-F and ipol.im/pub/algo/bcm_non_local_means_denoising for a start). Is this a homework problem? –  dranxo Apr 1 '11 at 23:08
    
Oh ok I see you've already linked the ROF paper. Did you read it? –  dranxo Apr 1 '11 at 23:11
    
I have to agree that reading and understanding the ROF paper is a good idea here- that paper is a very widely cited and important source and it includes some more sophisticated ideas than the ones in the first paper that you linked to. –  Brian Borchers Apr 2 '11 at 1:30
    
Also, state of the art ROF minimization isn't too hard to implement. cf ftp.math.ucla.edu/pub/camreport/cam08-29.pdf if you go to the authors website you can download code for it. –  dranxo Apr 2 '11 at 2:08
    
this is not a homework problem no, it's for my own learning. –  user23534523 Apr 2 '11 at 7:29

2 Answers 2

up vote 3 down vote accepted

If the solution to

$ u_t=u_{xx}+u_{yy} $

reaches an equilibrium solution, then $u_{t}=0$ at that equilibrium, so $u_{xx}+u_{yy}=0$. The author has shown that a necessary condition for $u$ to be minimizer of $E(u)$ is $u_{xx}+u_{yy}=0$.

This isn't steepest descent in the way that it is normally presented as an optimization algorithm for minimizing a function $f(x)$, but it is conceptually the same.

Of course you don't want to simply minimize $E(u)$ without respecting the original image- you want to somehow balance the minimization of $E(u)$ with keeping the original image. By starting the time dependent PDE with the original image and then stopping after a finite time, you can achieve this balance.

share|improve this answer

The equation

$ u_t = u_{xx} + u_{yy} $

is a gradient flow, or gradient descent, in the following sense. You should think of the equation as being placed in the space $L^2$. The Fréchèt derivative of the functional $E$ is the linear mapping

$ \displaystyle E'(u): v \mapsto -2\iint \nabla u\cdot \nabla v = -2\iint v(u_{xx}+u_{yy}), $

where for simplicity I'm assuming that the boundary conditions don't give rise to boundary terms in the partial integration. The second version, after partial integration, is relevant because it's written in the form of an $L^2$ inner product, allowing us to write the Fréchèt derivative as

$ E'(u)\cdot v = (-2(u_{xx}+u_{yy}),v)_{L^2} =: (\mathrm{grad}\ E(u),v)_{L^2} $

The $L^2$-gradient flow of $E$ is then the equation

$ u_t = -\mathrm{grad}\ E(u) = 2(u_{xx}+u_{yy}). $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.