step size tolerance in trust region minimizer when using local parameterization

[Chao Qu]

Hi,

I have a question regarding the convergence criterion of step size tolerance.

In Madsen's note (2004), one of the termination criteria is:

if ||h_lm|| <= e2(||x|| - e2), as can be found in algorithm 3.16 on page 27.

The corresponding code in ceres I believe is in trust_region_minimizer.cc:

iteration_summary.step_nom = (x - x_plus_delta).norm() and several lines after that.

This makes perfect sense to me when the parameters being optimized lie in euclidean space.

But when using a local parameterization, such as a homogeneous vector that lies on a unit sphere, is this criterion still valid?

What's confusing me is that since the parameter vector is on some manifold, is this simple subtraction of x and x_plus_delta a good representation of step norm?

I wrote myself a simple lm optimizer in python that refines a homography (which is just identity), what I notice is that if I use a local parameterization, it takes more iterations to converge (31 iterations).

But when I optimize this homography without minimum parameterization, it takes much less iterations (5 iterations) and still gives a good estimation.

I'd appreciate if anyone can show me what I'm missing. Thanks.

[Sameer Agarwal]

Chao,

There are two different things here. 

1. The behaviour of the solver with the local parameterization.

2. The right way to measure the step norm.

For (1), it is not necessarily the case that it is always a win. Sometimes the structure of the manifold is too complicated for the trust region algorithm to navigate well and its easier to actually go off the manifold and make large jumps.

(2) is more complicated. It is actually not clear to me what the best choice there is. Two reasons for it.

a. If you have bounds constraints in the ambient space, then you actually need to perform a line search in that space (as the algorithm is structured currently) before the actual step norm can be computed. So then we have the problem of computing the geodesic or some other distance between the previous estimate of the solution and the new one.

b. The convergence tolerance criterion will need to have units in the tangent space. Users have a simpler time reasoning about distance in ambient space and asking them to reason about distance in tangent space is making things harder.

HTH,

Sameer

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/f9ec723c-d0c9-4169-90b5-c4ad915362e9%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Chao Qu]

Thanks for your reply. 

I guess for local parameterization I will have to test it first before committing to it.

Regarding 2, are you suggesting there's no satisfying solution currently? What about lifting delta from tangent space to ambient space and compare that with the step size norm?

This plain subtraction just looks suspicious to me.

Chao

[Sameer Agarwal]

Chao,

On Sun, Sep 13, 2015 at 10:34 AM Chao Qu <versa...@gmail.com> wrote:

 

Regarding 2, are you suggesting there's no satisfying solution currently? What about lifting delta from tangent space to ambient space and compare that with the step size norm?

This plain subtraction just looks suspicious to me.

How do you propose we lift the step into the ambient space? 

Are you suggesting that delta be lifted up by itself? Which would mean that you are doing the lifting at x = 0. That is incorrect mathematically since the delta corresponds to the local tangent space at x.

So that leaves lifting it up into the ambient space at x, which is exactly what 

x_plus_delta is. It is computed by doing that lifting at line 411 of trust_region_minimizer.cc. At which point x_plus_delta - x is the norm of the step in the ambient space since we assume that the ambient space is a Euclidean space.

Sameer

 

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/89cd043e-1efa-460e-ad31-575f2effbaee%40googlegroups.com.

[Chao Qu]

Sameer,

What I meant is calculating the geodesic distance as the step norm, if it's defined.

For example, if I'm using quaternion as my parameter, instead of using step_norm = ||q' - q||, where q' is x_plus_delta and q is x, we could use step_norm = ||log(R' * R^T)||, where R' and R is the corresponding rotation matrix from q' and q.

If I'm using homogeneous parameterization, this could be some other distance metric defined on the hyper sphere.

I think there's a slight difference between "x_plus_deta - x" and "some_distance_function(x_plus_delta, x)" (which is just Plus(x_plus_delta, -x) in ceres?), but I'm not sure practically this will change anything significantly.

Does this make sense to you?

best,

Chao

[Sameer Agarwal]

Chao,

Computing the geodesic distance will further require extending the local parameterization object to compute these distances. And it is not clear if this is necessarily worth the effort.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/51722968-70dd-4e9f-88cd-c890fa315fe0%40googlegroups.com.