0
$\begingroup$

Some context before my question

I'm trying to make some object tracking software where the tracking is achieved by minimizing an energy function. The energy is a function of the pose parameters of the object. That means I'm trying to find those parameters that give me a transformation matrix (rotation and translation) that minimizes the energy. I express my transformations using twist coordinates(from screw theory) as parameters.


Minimizing that function led me to some numerical analysis/ optimization methods which I'm not familiar with. Basically, I first came across gradient descent. I get that gradient descent gives me the vector $V$ that points towards the local minima. The tricky part is the step. I wanted to find a coefficient to multiply $V$ so that convergence is fast and without overstepping. That's where Newton's method came to play and I realized that multiplying my $V$ with the inverse of the Hessian of the function $H^{-1}$ I make a good step towards the minima. However, this is giving me weird results so I'm trying to debug my code and see what's wrong.

Of course, the debugging is my part. But as I'm trying to find what's wrong I came up with a question. Instead of using a coefficient to limit my step, I now use the matrix $H^{-1}$ and multiply that by $V$. Doesn't the result have a different direction from the initial $V$? That means we don't travel along the initial direction. So, if $H^{-1}$ doesn't actually dictate the step, what does it do and helps us in this case? How does it correct the initial vector $V$ ?

I think after applying gradient descent for one iteration, in the second iteration I would end up with another $V$. Is the Hessian kind of "predicting" the next vectors of gradient descent and trying to give us one vector that combines them?

I hope I explained it well enough.


TLDR

The basic Newton method does this: $x_{x+1}=x_k -af'(x)$ where a is the step. A better iteration would be $x_{k+1}=x_k-\frac{f'(x)}{f''(x)}$ which for multivariable functions leads to $\vec X_{k+1}=\vec X_k-H^{-1}\nabla f$ Multiplying the step by $H^-1$ is not as simple as multiplying by a coefficient $a$. It doesn't just limit the step, it changes its direction. So, how exactly does $H^{-1}$ change $\nabla f$ to a better step towards the local minima?

$\endgroup$
5
  • $\begingroup$ It first sounds like you are trying to get a scalar to scale the direction of the gradient descent, but, then you have a hessian matrix, so exactly what are you here (preferably in math, not words)? $\endgroup$ Commented Aug 6, 2021 at 15:31
  • $\begingroup$ @MikaelÖhman I'm not sure I understand your question. I clarified some stuff in case it helps. The basic Newton method does this: $x_{x+1}=x_k -af'(x)$ where a is the step. A better iteration would be $x_{k+1}=x_k--\frac{f'(x)}{f"(x)}$ which for multivariable functions leads to $\vec X_{k+1}=\vec X_k-H^{-1}\nabla f$ $\endgroup$ Commented Aug 6, 2021 at 15:50
  • $\begingroup$ It gives you the solution of $\frac{\partial}{\partial \vec{\delta}} f(\vec{x}+\vec{\delta}) = \vec{0}$ using the second order Taylor expansion $f(\vec{x}+\vec{\delta}) \approx f(\vec{x}) + \nabla f(\vec{x})\cdot\vec{\delta} + \frac12 \vec{\delta} \cdot H_f(\vec{x}) \cdot \vec{\delta}$. I wouldn't even think of it as "changing" the direction. $\endgroup$ Commented Aug 6, 2021 at 16:53
  • $\begingroup$ @MikaelÖhman Isn't $H^{-1}\nabla f$ a different direction from $\nabla f$ ? The gradient descent gives us a specific direction to walk towards the minimum. The Hessian changes that direction. What is the geometric meaning of that change? That's what I'm trying to figure out. $\endgroup$ Commented Aug 6, 2021 at 17:37
  • $\begingroup$ There are techniques that pick the gradient direction and then scales it via some line-search technique, but this isn't one. The $H^{-1}\cdot\nabla f$ just directly solves for the minimum (with second order approximation). If $f$ actually was a simple quadratic function you would just exactly solve for the minimum (without iterations) just like this. Just let go of the idea of the idea that it must be direction*scale. $\endgroup$ Commented Aug 6, 2021 at 17:49

1 Answer 1

0
$\begingroup$

Using quadratic approximation to the function near the minimum, we can write:

$f(\mathbf{x}_k) = \frac{1}{2} (\mathbf{x}_k - \mathbf{x}_0)^T H (\mathbf{x}_k - \mathbf{x}_0)$

where the Hessian matrix is assumed positive definite ( so that we have a minimum at $\mathbf{x}_0 $ )

Take the gradient of the above,

$ \nabla f = H (\mathbf{x}_k - \mathbf{x}_0) $

From which it follows that,

$ \mathbf{x}_0 = \mathbf{x}_k - H^{-1} \nabla f $

And this is the best approximation of the minimum given a quadratic approximation to the function.

So we'll take,

$ \mathbf{x}_{k+1} = \mathbf{x}_k - H^{-1} \nabla f $

then repeat the process again and again with a new $H$ and a new $\nabla f$.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer. I'm familiar with this but I'm mostly concerned about the difference between using a linear approximation and a quadratic one. With a linear approximation we would have $x_{k+1}=x_k -\nabla f$. $\nabla f$ has a specific direction. Multiplying $\nabla f$ by $H^{-1}$ we end up with a different direction. What is the geometric meaning of this change in direction? $\endgroup$ Commented Aug 6, 2021 at 17:43
  • $\begingroup$ The modified formula that involves $H^{-1}$ comes, as explained in my answer, by using a quadratic approximation instead of just following the descent direction. The change in direction results in the exact minimum in one step if the function $f$ was truly quadratic, otherwise several iterations are needed to reach the minimum. $\endgroup$
    – Quadrics
    Commented Aug 6, 2021 at 17:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .