Nonstandard Hessian approximations in Gauss-Newton

2012-09-05T22:50:19Z

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)

Answer by Brian Borchers for Nonstandard Hessian approximations in Gauss-Newton

2012-09-06T05:04:04Z

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:

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

Nonstandard Hessian approximations in Gauss-Newton - MathOverflow

Nonstandard Hessian approximations in Gauss-Newton

Answer by Brian Borchers for Nonstandard Hessian approximations in Gauss-Newton