4
$\begingroup$

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)

$\endgroup$
6
  • 3
    $\begingroup$ 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? $\endgroup$
    – dranxo
    Apr 1, 2011 at 23:08
  • $\begingroup$ Oh ok I see you've already linked the ROF paper. Did you read it? $\endgroup$
    – dranxo
    Apr 1, 2011 at 23:11
  • $\begingroup$ 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. $\endgroup$ Apr 2, 2011 at 1:30
  • $\begingroup$ 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. $\endgroup$
    – dranxo
    Apr 2, 2011 at 2:08
  • $\begingroup$ this is not a homework problem no, it's for my own learning. $\endgroup$ Apr 2, 2011 at 7:29

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

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}). $

$\endgroup$
3

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.