1
$\begingroup$

The Gauss-Newton algorithm optimizes functions

$$ E(x) = \sum f(x)^2 $$

by approximating f as (locally) linear, in which case the Hessian of $E$ is approximated as

$$ H = 2 \sum {J_f}^T J_f $$

Now if I introduce a robust cost function in place of the squared cost above, I can similarly approximate the Hessian of $E$ using a linear approximation to $f$. For example, using the Cauchy robustifier

$$ E(x) = \sum \log\bigl(1+\frac{f^2}{\sigma^2}\bigr) $$

The hessian for $E$ assuming $f$ is linear is:

$$ H = \sum \frac{2 J^T J}{\sigma^2 + f^2} - \frac{4 (J^T f) (J^T f)^T}{(\sigma^2 + f^2)^2} $$

So is it a good idea to use this Hessian to solve the normal equations during gradient descent? Can I still use the Levenberg-Marquardt damping trick? Are there better options than this?

Some extra details of my problem:

  • $x$ is small (6 dimensions parametrizing Fundamental matrices)
  • $f$ is the Sampson error (a geometric error measure for two-image correspondences)
  • I expect to have 100-400 residual terms in the summation
  • I have a very low computation budget (a few milliseconds on a mobile device)
Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

You could certainly try this, but you'd have to do a lot of careful analysis to derive any convergence results. Among other things to consider:

  1. Your objective E(x) is more likely to have local minima due to the nonconvexity introduced by the logarithms. This could also happen with the sum of squares objective, but in practice it's uncommon for reasonably well behaved f(x).

  2. Your approximate Hessian will typically be fully dense, and depending on the size of $x$, this might make the solution of the equations impractical.

You haven't said anything about how you're computing $J$ or how you might be able to compute the second derivatives of $f$.

You haven't said anything about how large your vector of parameters $x$ is. If it is large, then rather than attempting this, I'd suggest using a limited memory BFGS method to avoid storing the dense $H$.

If it's small, then depending on the difficulty of computing the second derivatives of $f$, I'd probably use the full Hessian and implement Newton's method rather than doing all of the work to show that this Gauss-Newton like method had good theoretical properties. If the second derivatives are hard to compute, then I'd just use a conventional BFGS quasi-Newton method.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks Brian, have added your suggested clarifications to the question. The problem is very small (6 parameters) but the second derivatives are quite expensive because x lives in a non-euclidean manifold (I'm optimizing over Fundamental matrices) and $f$ is a nasty geometric error. Also we have about 2ms on an iPhone to do the optimization :). I'll take your advice and look into the second derivates though. BTW is there a text you can recommend on the numerical details of these kinds of problems? $\endgroup$
    – Alex Flint
    Commented Sep 6, 2012 at 15:27
  • $\begingroup$ Now I'm even more confused about your problem. You say that x lives "in a non-euclidean manifold", so it appears that you don't have an unconstrained optimization problem. In that case, you'd have a constrained nonlinear optimization problem and you'd need to consider algorithms for constrained problems rather than methods for unconstrained optimization. A good (but somewhat old) textbook that deals with mathematics and many practical aspects of optimization is "Practical Optimization" by Gill, Murray, and Wright. You'd find lots of good advice in that book on how to approach this. $\endgroup$
    – Brian Borchers
    Commented Sep 7, 2012 at 4:18
  • $\begingroup$ On the other hand, if this really an unconstrained problem, I'd simply use BFGS. The computations inside the BFGS method won't be time consuming for a small problem like this, so the big concern will be the cost of function and derivative computations. You'll probably want to experiment with finite difference derivatives vs. derivatives by automatic differentiation vs. analytical formulas for the derivatives to see what works best (both in terms of accuracy and speed.) You can also play with the convergence criteria- perhaps a relatively imprecise solution will be adequate for your work. $\endgroup$
    – Brian Borchers
    Commented Sep 7, 2012 at 13:08
0
$\begingroup$

I'd suggest looking at the paper Deep Learning Via Hessian-free optimization which seems to use methods similar to the one you're asking about. In particular

In the development of his on-line 2nd-order method “SMD”, Schraudolph (2002) generalized Pearlmutter’smethod in order to compute the product Gd where G is the Gauss-Newton approximation to the Hessian

[...]

on all of the learning problems we tested, using G instead of H consistently resulted in much better search directions...

They also address Levenberg-Marquardt style damping in the paper.

Improve this answer
$\endgroup$

You must log in to answer this question.

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