1
$\begingroup$

Suppose I have a randomly-generated set of numbers, where each number is indexed by $x$. This is equivalent to a 1-D scalar field, let's call that $u(x)$.

Let's say my objective is to minimize the distance between each subsequent pair of scalars, which may be expressed as minimizing the following energy functional:

$$E[u(x)] = \sum_{x}\left(\frac{du(x)}{dx}\right)^2$$

Thanks to comment/clarification by @BrianBorchers, setting $u(x)=0$ would ultimately achieve an unconstrained minimum. Thus, I introduce the following constraints: $u(x)$ is defined on $[a,b]$, so that $u(a)$ and $u(b)$ are fixed scalar values.

The first (or second) derivatives for the scalar field $u(x)$ can be approximated easily by taking finite differences. I would like to simply use gradient descent to get the scalar field u to converge to the desired state. Hence I need an update step for $u(x)$, something like:

$$u^{k+1} = u^{k} - \alpha\left(\frac{dE[u(x)]}{du(x)}\right)$$, where $\alpha$ is a constant update step/rate.

I'm doing this to gain thorough understanding of a research article which uses similar, albeit more complex energy functions expressed in terms of a vector field. The authors state that the update step, i.e. the equivalent of the term $\frac{dE[u(x)]}{du(x)}$ above is derived using the Euler-Lagrange equations. Links to the article and the supplementary material are given below.

I looked at numerous tutorials and some books, and if I understand correctly, the Euler-Lagrange equation for the said energy $E[u(x)]$ would be:

$$-\frac{d}{dx}E_{u'}[u(x)] + E_{u}[u(x)] = 0$$ or, using Lagrange's notation for derivatives, $$-\frac{d}{dx}\left(\frac{dE[u(x)]}{d\frac{du(x)}{dx}}\right) + \frac{dE[u(x)]}{du(x)} = 0$$

  1. Is the above formulation of the Euler-Lagrange equation correct?
  2. The Euler-Lagrange equation looks like it would directly yield a stationary point in the energy functional. I suppose, I cannot do that directly for some reason. How exactly does the Euler-Lagrange equation relate to the update step I should take in my gradient descent above?
  3. How exactly do I formulate the update step as a function of first and second derivatives of $u(x)$ w.r.t. $x$?

The original research article (see sec 4.2) and supplementary material (see sec 2.3) :

$\endgroup$
  • $\begingroup$ Your question is unclear- Simply setting $u(x)=0$ produces an unconstrained minimum of $E$. What additional constraints do you want to impose? $\endgroup$ – Brian Borchers Nov 14 '17 at 16:19
  • $\begingroup$ @BrianBorchers, I'm sorry for my relative illiteracy in this, what is an unconstrained minimum and how would $u(x) = 0$ yield this minimum? - Thanks $\endgroup$ – Algomorph Nov 14 '17 at 16:23
  • $\begingroup$ @BrianBorchers, on second thought, I think I understand what you're asking. Artificially setting $u(x) = 0$ would achieve a global minimum without additional constraints. I guess, I should introduce constraint that $u(x)$ is defined on an interval [a,b], and $u(a)$ and $u(b)$ cannot be modified. Should I modify the question like this? $\endgroup$ – Algomorph Nov 14 '17 at 16:28
  • $\begingroup$ If your only constraints are that $u(a)$ and $u(b)$ are given, then the solution (with an objective value of 0) is $u(x)=u(a)+((x-a)/(b-a))(u(b)-u(a))$. $\endgroup$ – Brian Borchers Nov 14 '17 at 17:06
  • $\begingroup$ Thanks, @BrianBorchers. I was looking for a way one would solve this with gradient descent, not directly, as I described in question #2. One of my colleagues, Nitin Sanket already provided the answer (big thanks to Nitin!). The update step $\frac{dE[u(x)]}{du(x)}$ may be difficult to compute. This gradient is exactly the second part of the Euler-Lagrange equation I wrote (after the plus sign). If we shift it to the right-hand side and solve for the left-hand side, we can compute this gradient locally, it becomes $-2\sum_{x} u_{xx}u_{x}$. $\endgroup$ – Algomorph Nov 14 '17 at 17:24
0
$\begingroup$

I'm answering on behalf of Nitin Sanket, and he deserves full credit for the explanation.

1) The Euler-Lagrange equation is essentially correct. Normally, with the exception of $-\frac{d}{dx}$ in the very beginning, we would have partial derivatives, but here the regular derivative works since $E$ is a function only in $u(x)$. There is a slight problem with the notation here, same as in the paper: the total energy needs to be expressed separately from the function inside the integral (in this case, sum). This way, it is clear that the update step at each point x of the scalar field does not involve the sum.

2) and 3) The update step $\frac{dE[u(x)]}{du(x)}$ can be obtained by moving the first term of the given Euler-Lagrange equation to the right-hand side, thereby solving for the step. Since first- and second-order derivatives are easy to compute on the scalar field, we can easily obtain the update at each step.

The rest of the Killing regularizer from the cited article is just a generalization of the above method from a Lagrangian of a scalar field in one dimension to a Lagrangian of a vector field in three dimensions, which can be easily derived following the Wikipedia entry on the subject.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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