Levenberg optimizer halts quickly when given more variables, or fewer constraints

Question

I'm using the g2o C++ optimization library to refine a GPS trajectory using accelerometer data.

The program uses a Levenberg-Marquardt optimizer over data points representing the position and orientation (vector part of quaternion) of the accelerometer. The only constraints are the accelerations in the local reference frame.

Error is measured as the difference between the accelerometer reading, and the local second derivative of the path traced by the data points — the change in velocity from (a to b) to (b to c), disregarding change in orientation, plus the upward acceleration counteracting gravity.

The initial path is a polygon drawn between GPS readings.

The optimizer runs for five iterations of gradient descent, and seems to make good adjustments. The polygon corners get rounded off a bit. But then it seems to get stuck, and Levenberg's lambda goes up for five iterations before the program terminates.

BUT

It does a lot more refinement if I further constrain it using data from the gyroscope. However, not at as much as I'd expect, and the gyro data needs have artificially high Fisher information.

Working on segments of the whole problem doesn't terminate so quickly. It does more refinement using acceleration alone.

What could be going wrong? The inability to refine the initial estimate by acceleration alone seems to indicate a serious problem.

Answer 1

It could be that your optimization problem is very badly conditioned when using only the accelerometer data. In other words, the accelerometer data might not sufficiently constrain the parameters so that many different paths adequately fit the data. In terms of the minimization problem this means that you'd have a large "flat spot" at the minimum of different paths with nearly the same objective value.

To test for this, look at the condition number of $J^{T}J$ at the optimal trajectory. If this matrix is ill-conditioned, then you do indeed have a badly conditioned problem.

This would explain the increase in the LM's $\lambda$. If $J^{T}J$ is approaching singularity, LM will increase $\lambda$ to overcome that singularity. This results in shorter and shorter steps, and eventually the LM code just gives up.

Answer 2

The last vertex (data point) in the initial estimate was not getting initialized.

I'm not sure why this choked the solver. Something to do with the error from one outlier point propagating to the other data points, and pulling everything out of the minimum. It still doesn't make sense that everything would be pulled out after so few iterations, though, and the effect isn't obvious on inspection of the premature solution.