[ https://issues.apache.org/jira/browse/MATH352?page=com.atlassian.jira.plugin.system.issuetabpanels:alltabpanel
]
Luc Maisonobe closed MATH352.

Closing issue as it was included in version 2.2, which has been released
> Jacobian rank determination in LevenbergMarquardtOptimizer is not numerically robust
> 
>
> Key: MATH352
> URL: https://issues.apache.org/jira/browse/MATH352
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 2.0
> Environment: commonsmath 2.0
> Reporter: Gene Gorokhovsky
> Priority: Critical
> Labels: DifferentiableMultivariateVectorialOptimizer, Levenberg, Marquardt,
commonsmath, optimizer, qr, rank
> Fix For: 2.2
>
>
> LevenbergMarquardtOptimizer is designed to handle singular jacobians, i.e. situations
when some of the fitted parameters depend on each other. The check for that condition is in
LevenbergMarquardtOptimizer.qrDecomposition uses precise comparison to 0.
> if (ak2 == 0 ) {
> rank = k;
> return;
> }
> A correct check would be comparison with a small epsilon. Hard coded 2.2204e16 is used
elsewhere in the same file for similar purpose.
> final double QR_RANK_EPS = Math.ulp(1d); //2.220446049250313E16
> ....
> if (ak2 < QR_RANK_EPS) {
> rank = k;
> return;
> }
> Current exact equality check is not tolerant of the real world poorly conditioned situations.
For example I am trying to fit a cylinder into sample 3d points. Although theoretically cylinder
has only 5 independent variables, derivatives for optimizing function (signed distance) for
such minimal parametrization are complicated and it it much easier to work with a 7 variable
parametrization (3 for axis direction, 3 for axis origin and 1 for radius). This naturally
results in rankdeficient jacobian, but because of the numeric errors the actual ak2 values
for the dependent rows ( I am seeing values of 1e18 and less), rank handling code does not
kick in.
> Keeping these tiny values around then leads to huge corrections for the corresponding
very slowly changing parameters, and consequently to numeric errors and instabilities. I have
noticed the problem because tiny shift in the initial guess (on the order of 1e12 in the
axis component and origins) resulted in significantly different finally converged answers
(origins and radii differing by as much as 0.02) which I tracked to loss of precision due
to numeric error with root cause described above.
> Providing a cutoff as suggested fixes the issue. After the fix, small perturbations in
the initial guess had practically no effect to the converged result  as expected from a robust
algorithm.

This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
