scaling

[s1m...@gmail.com]

Reading Nocedal and Wright's book Numerical Optimization, and your discussion in topic "Initialization of Levenberg-Marquardt", I was wondering how ceres-solver handels scaling issues.
In the documentation I found the option Solver::Options::jacobi_scaling which is enabled by default.
In the book I read about scaling fit parameters so that they are expected to have the same order magnitude (diagonal sacling chapter 2.1).
And about using elliptical trust regions (chapter 4.5).

I use Levenberg Marquardt to solve curve fitting problems and I am wondering if I should scale my fit parameters.  Is it not needed when Solver::Options::jacobi_scaling is enabled?
Maybe I am mixing things up, and the jacobi_scaling only refers to a numerical issue.
The sensitivity of some of the fit parameters depends on the values of other fitparameters. (e.g. you have two fitparameters a and b. When a is small,  changes in b will highly afffect the total cost, but when a is big, changes in b will have only very small effect on the cost.)

Reading the documentation about Preconditioner, chapter 5.1 in the textbook  and Sameer Agarwal's comments:

If the problem is poorly conditioned, it basically means that different variables require vastly varying magnitudes of change to decrease the objective function value.

 

If you start with the linear system itself, and you are using a direct solver + exact arithmetic, then preconditioning has no effect on the solution. In floating point + direct solver it will improve the accuracy of the solution, in floating point + iterative solver, it will be the difference between getting a usable solution in a reasonable amount of time or not.

The default preondictioner is JACOBI. As a linear solver I use DENSE_QR.

Summing up my questions:

• Should I scale my fitparameters (diagonal sacling)?
• Does scaling (diagonal sacling or jacobi_scaling) influences the condition of my problem?
• How does ceres-solver handels scaling (can it use elliptical trust regions)?

• How does scaling and preconditioning are related?
• How do I find out if my problem is ill conditioned?

Regards

Simeon

[Sameer Agarwal]

Simeon,

A lot of things going on in this email. I will try and answer inline.

On Fri, Jul 31, 2015 at 1:39 AM <s1m...@gmail.com> wrote:

Reading Nocedal and Wright's book Numerical Optimization, and your discussion in topic "Initialization of Levenberg-Marquardt", I was wondering how ceres-solver handels scaling issues.

The short answer is, it doesn't. If your problem is poorly conditioned, there is only so much any non-linear solver can do on its own.

 

In the documentation I found the option Solver::Options::jacobi_scaling which is enabled by default.

Yes, this improves the conditioning of the Jacobian, and in turn of the trust-region problem. But this is a heuristic.

 

In the book I read about scaling fit parameters so that they are expected to have the same order magnitude (diagonal sacling chapter 2.1).
And about using elliptical trust regions (chapter 4.5).

I use Levenberg Marquardt to solve curve fitting problems and I am wondering if I should scale my fit parameters.  Is it not needed when Solver::Options::jacobi_scaling is enabled?

Please DO scale your fit parameters. 

 

Maybe I am mixing things up, and the jacobi_scaling only refers to a numerical issue.

Yes, this improves conditioning of the linear system, but your overall non-linear problem remains poorly conditioned.

 

The sensitivity of some of the fit parameters depends on the values of other fitparameters. (e.g. you have two fitparameters a and b. When a is small,  changes in b will highly afffect the total cost, but when a is big, changes in b will have only very small effect on the cost.)

Reading the documentation about Preconditioner, chapter 5.1 in the textbook  and Sameer Agarwal's comments:

If the problem is poorly conditioned, it basically means that different variables require vastly varying magnitudes of change to decrease the objective function value.

 

If you start with the linear system itself, and you are using a direct solver + exact arithmetic, then preconditioning has no effect on the solution. In floating point + direct solver it will improve the accuracy of the solution, in floating point + iterative solver, it will be the difference between getting a usable solution in a reasonable amount of time or not.

The default preondictioner is JACOBI. As a linear solver I use DENSE_QR.

The preconditioner choice is only applicable when you are using an iterative solver. If you are using any of the factorization based solvers, the preconditioner is not used. The Jacobi preconditioner and the Jacobi scaling are very similarly named but refer to two different things. The Jacobi is a scaling of the jacobian by a diagonal matrix. It is done independent of the choice of linear solver.

The JACOBI preconditioner is only used when you use an iterative solver, i.e. CGNR or ITERATIVE_SCHUR and in those cases too, it means different things. In case of CGNR, it means the block diagonal of J'J + \lambda D. In case of ITERATIVE_SCHUR it just means the block diagonal of the camera matrix.

Summing up my questions:

• Should I scale my fitparameters (diagonal sacling)?
• Does scaling (diagonal sacling or jacobi_scaling) influences the condition of my problem?
• How does ceres-solver handels scaling (can it use elliptical trust regions)?

• How does scaling and preconditioning are related?

I hope I answered these questions above.

• How do I find out if my problem is ill conditioned?

The condition number of J'J is a great indication.

Sameer

 

Regards

Simeon

--
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/bbf76b2b-f3a1-46b8-9422-fa0a729fa729%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Hariprasad Kannan]

This discussion answers my doubt. I was wondering how one can scale/precondition the Levenber-Marquardt problem. One can start with Jacobi scaling and see.

[s1m...@gmail.com]

Thank you for your reply.

[Jon Zubizarreta Gorostidi]

I am using variable scaling to improve the conditioning of the jacobian.

However, I was wondering how should I determine the stop criteria when scaling jacobians. This is, when scaling each block of the jacobian with constant values, the estimated step is also scaled. Thus, how should I proceed?

Ceres API provides a parameter called "parameter_tolerance" to control the stop criteria based on the norm of the step. What happens if the step is scaled in the situation stated above?

I would like to stop iterating when my parameters converge.

Thanks for all the support,

Jon

[Sameer Agarwal]

Parameter Tolerance is a relative tolerance. So it is really a matter of your taste as to what you consider to be a small enough increment.

--

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/93849d36-a3bd-4ed5-b84b-2590fee4d3d5%40googlegroups.com.