Linear solver failure: Matrix not positive semi-definite

[Johannes Schönberger]

Hi,

I am using Ceres for bundle-adjustment and combined pose and point cloud optimization. The "connection" between frames is typically very weak and the feature / image quality is poor. I am assuming a Cauchy distribution for the MLE to account for (overall rare) outliers in the data of the BA. For very small problems with 50k residuals and 10k parameters the optimization works without any failures, but with increasing size (dealing with problems > 10 million residuals) I get lots of linear solver failures - however the result of the optimization still looks good. I am setting two poses as fixed to avoid datum defects. At the same time each world point is observed at least twice in separate images to eliminate any singularity caused by a configuration defect. I produced an example with small size:

I1123 21:38:36.312932 2026492688 solver_impl.cc:320] Initial problem: 6082 parameter blocks, 17641 parameters,  65833 residual blocks, 131666 residuals.

I1123 21:38:36.319118 2026492688 solver_impl.cc:1088] Reduced problem: 6073 parameter blocks, 17625 parameters,  65833 residual blocks, 131666 residuals.

I1123 21:38:36.936172 2026492688 block_sparse_matrix.cc:78] Allocating values array with 9318864 bytes.

   0: f: 5.649553e+04 d: 0.00e+00 g: 5.18e+04 h: 0.00e+00 rho: 0.00e+00 mu: 1.00e+04 li:  0 it: 1.07e-01 tt: 7.12e-01

I1123 21:38:38.218369 2026492688 block_random_access_sparse_matrix.cc:75] Matrix Size [594,594] 177012

I1123 21:38:38.243227 2026492688 detect_structure.cc:88] Dynamic f block size because the block size changed from 3 to 1

I1123 21:38:38.243754 2026492688 detect_structure.cc:107] Schur complement static structure <2,3,-1>.

CHOLMOD version 2.1.2, April 25, 2013: Symbolic Analysis: status: OK

  Architecture: Mac

    sizeof(int):      4

    sizeof(SuiteSparse_long):  8

    sizeof(void *):   8

    sizeof(double):   8

    sizeof(Int):      4 (CHOLMOD's basic integer)

    sizeof(BLAS_INT): 4 (integer used in the BLAS)

  Results from most recent analysis:

    Cholesky flop count: 7.0038e+07

    Nonzeros in L:       1.7672e+05

  memory blocks in use:          15

  memory in use (MB):           2.1

  peak memory usage (MB):       4.1

  maxrank:    update/downdate rank:   8

  supernodal control: 1 40 (supernodal if flops/lnz >= 40)

  nmethods:   number of ordering methods to try: 1

    method 0: natural

        flop count: 7.0038e+07

        nnz(L):     1.7672e+05

  OK

   1: f: 2.678360e+04 d: 2.97e+04 g: 1.47e+05 h: 1.72e+03 rho: 1.61e+00 mu: 3.00e+04 li:  1 it: 2.63e+00 tt: 3.35e+00

   2: f: 2.275270e+04 d: 4.03e+03 g: 5.18e+03 h: 4.25e+03 rho: 1.64e+00 mu: 9.00e+04 li:  1 it: 1.36e+00 tt: 4.71e+00

   3: f: 2.158328e+04 d: 1.17e+03 g: 6.54e+03 h: 9.43e+04 rho: 1.77e+00 mu: 2.70e+05 li:  1 it: 1.37e+00 tt: 6.08e+00

   4: f: 2.100601e+04 d: 5.77e+02 g: 1.72e+04 h: 4.06e+04 rho: 2.08e+00 mu: 8.10e+05 li:  1 it: 1.36e+00 tt: 7.44e+00

   5: f: 2.083282e+04 d: 1.73e+02 g: 3.41e+03 h: 6.87e+04 rho: 1.45e+00 mu: 2.43e+06 li:  1 it: 1.35e+00 tt: 8.79e+00

   6: f: 2.074319e+04 d: 8.96e+01 g: 6.41e+03 h: 1.11e+05 rho: 1.25e+00 mu: 7.29e+06 li:  1 it: 1.36e+00 tt: 1.02e+01

   7: f: 2.064222e+04 d: 1.01e+02 g: 2.20e+05 h: 1.53e+05 rho: 1.67e+00 mu: 2.19e+07 li:  1 it: 1.37e+00 tt: 1.15e+01

   8: f: 2.053467e+04 d: 1.08e+02 g: 1.71e+06 h: 2.46e+05 rho: 2.07e+00 mu: 6.56e+07 li:  1 it: 1.35e+00 tt: 1.29e+01

   9: f: 2.051371e+04 d: 2.10e+01 g: 1.36e+07 h: 4.75e+05 rho: 1.14e+00 mu: 1.97e+08 li:  1 it: 1.36e+00 tt: 1.42e+01

  10: f: 2.050807e+04 d: 5.64e+00 g: 3.12e+07 h: 1.01e+06 rho: 6.06e-01 mu: 1.99e+08 li:  1 it: 1.34e+00 tt: 1.56e+01

  11: f: 2.050359e+04 d: 4.48e+00 g: 6.15e+07 h: 3.36e+05 rho: 6.59e-01 mu: 2.05e+08 li:  1 it: 1.36e+00 tt: 1.70e+01

  12: f: 2.049229e+04 d: 1.13e+01 g: 5.48e+07 h: 2.64e+05 rho: 1.39e+00 mu: 6.16e+08 li:  1 it: 1.39e+00 tt: 1.83e+01

W1123 21:38:55.878710 2026492688 suitesparse.cc:275] CHOLMOD warning: Matrix not positive definite.

W1123 21:38:55.878758 2026492688 schur_complement_solver.cc:317] CHOLMOD solve failed.

W1123 21:38:55.878772 2026492688 levenberg_marquardt_strategy.cc:110] Linear solver failure. Failed to compute a finite step.

  13: f: 2.049229e+04 d: 0.00e+00 g: 5.48e+07 h: 0.00e+00 rho: 0.00e+00 mu: 3.08e+08 li:  1 it: 1.21e+00 tt: 1.95e+01

W1123 21:38:57.082247 2026492688 suitesparse.cc:275] CHOLMOD warning: Matrix not positive definite.

W1123 21:38:57.082285 2026492688 schur_complement_solver.cc:317] CHOLMOD solve failed.

W1123 21:38:57.082294 2026492688 levenberg_marquardt_strategy.cc:110] Linear solver failure. Failed to compute a finite step.

  14: f: 2.049229e+04 d: 0.00e+00 g: 5.48e+07 h: 0.00e+00 rho: 0.00e+00 mu: 7.70e+07 li:  1 it: 1.20e+00 tt: 2.08e+01

  15: f: 2.049229e+04 d:-1.02e+01 g: 0.00e+00 h: 8.24e+04 rho:-1.66e+00 mu: 9.63e+06 li:  1 it: 1.26e+00 tt: 2.20e+01

  16: f: 2.048563e+04 d: 6.66e+00 g: 1.13e+06 h: 1.06e+04 rho: 1.10e+00 mu: 2.89e+07 li:  1 it: 1.35e+00 tt: 2.34e+01

  17: f: 2.047595e+04 d: 9.68e+00 g: 2.57e+06 h: 3.07e+04 rho: 1.27e+00 mu: 8.66e+07 li:  1 it: 1.35e+00 tt: 2.47e+01

  18: f: 2.045513e+04 d: 2.08e+01 g: 1.53e+06 h: 8.94e+04 rho: 1.52e+00 mu: 2.60e+08 li:  1 it: 1.39e+00 tt: 2.61e+01

W1123 21:39:03.625394 2026492688 suitesparse.cc:275] CHOLMOD warning: Matrix not positive definite.

W1123 21:39:03.625435 2026492688 schur_complement_solver.cc:317] CHOLMOD solve failed.

W1123 21:39:03.625444 2026492688 levenberg_marquardt_strategy.cc:110] Linear solver failure. Failed to compute a finite step.

  19: f: 2.045513e+04 d: 0.00e+00 g: 1.53e+06 h: 0.00e+00 rho: 0.00e+00 mu: 1.30e+08 li:  1 it: 1.20e+00 tt: 2.73e+01

  20: f: 2.043716e+04 d: 1.80e+01 g: 9.59e+05 h: 1.25e+05 rho: 6.20e-01 mu: 1.32e+08 li:  1 it: 1.34e+00 tt: 2.86e+01

  21: f: 2.041979e+04 d: 1.74e+01 g: 3.07e+05 h: 1.17e+05 rho: 3.98e-01 mu: 1.31e+08 li:  1 it: 1.34e+00 tt: 3.00e+01

  22: f: 2.040504e+04 d: 1.48e+01 g: 9.95e+04 h: 1.07e+05 rho: 3.25e-01 mu: 1.25e+08 li:  1 it: 1.36e+00 tt: 3.13e+01

  23: f: 2.040052e+04 d: 4.52e+00 g: 8.18e+04 h: 1.77e+05 rho: 1.02e-01 mu: 8.34e+07 li:  1 it: 1.36e+00 tt: 3.27e+01

  24: f: 2.039342e+04 d: 7.11e+00 g: 6.96e+04 h: 6.27e+04 rho: 1.60e+00 mu: 2.50e+08 li:  1 it: 1.34e+00 tt: 3.40e+01

  25: f: 2.038697e+04 d: 6.45e+00 g: 6.29e+06 h: 1.80e+05 rho: 1.43e+00 mu: 7.50e+08 li:  1 it: 1.35e+00 tt: 3.54e+01

  26: f: 2.038107e+04 d: 5.90e+00 g: 1.82e+06 h: 4.84e+05 rho: 1.10e+00 mu: 2.25e+09 li:  1 it: 1.36e+00 tt: 3.67e+01

  27: f: 2.037983e+04 d: 1.24e+00 g: 1.37e+07 h: 1.14e+06 rho: 3.57e-01 mu: 2.20e+09 li:  1 it: 1.34e+00 tt: 3.81e+01

  28: f: 2.037466e+04 d: 5.17e+00 g: 6.44e+06 h: 6.77e+05 rho: 1.15e+00 mu: 6.60e+09 li:  1 it: 1.34e+00 tt: 3.94e+01

  29: f: 2.037260e+04 d: 2.06e+00 g: 1.53e+06 h: 1.58e+06 rho: 1.43e+00 mu: 1.98e+10 li:  1 it: 1.35e+00 tt: 4.08e+01

  30: f: 2.037260e+04 d:-6.74e-01 g: 0.00e+00 h: 2.90e+06 rho:-5.50e-01 mu: 9.90e+09 li:  1 it: 1.25e+00 tt: 4.20e+01

  31: f: 2.037260e+04 d:-6.38e-01 g: 0.00e+00 h: 1.45e+06 rho:-5.21e-01 mu: 2.47e+09 li:  1 it: 1.24e+00 tt: 4.33e+01

  32: f: 2.037260e+04 d:-7.16e-01 g: 0.00e+00 h: 3.62e+05 rho:-5.87e-01 mu: 3.09e+08 li:  1 it: 1.25e+00 tt: 4.45e+01

  33: f: 2.037260e+04 d:-6.59e-01 g: 0.00e+00 h: 4.53e+04 rho:-5.42e-01 mu: 1.93e+07 li:  1 it: 1.25e+00 tt: 4.58e+01

  34: f: 2.037260e+04 d:-1.25e+00 g: 0.00e+00 h: 3.11e+03 rho:-1.03e+00 mu: 6.04e+05 li:  1 it: 1.26e+00 tt: 4.70e+01

  35: f: 2.037136e+04 d: 1.25e+00 g: 3.16e+04 h: 1.34e+03 rho: 1.22e+00 mu: 1.81e+06 li:  1 it: 1.36e+00 tt: 4.84e+01

  36: f: 2.037084e+04 d: 5.19e-01 g: 1.24e+05 h: 9.73e+02 rho: 1.02e+00 mu: 5.44e+06 li:  1 it: 1.34e+00 tt: 4.97e+01

  37: f: 2.037084e+04 d:-5.50e+00 g: 0.00e+00 h: 1.05e+03 rho:-9.30e+00 mu: 2.72e+06 li:  1 it: 1.25e+00 tt: 5.10e+01

  38: f: 2.037031e+04 d: 5.30e-01 g: 3.32e+05 h: 7.94e+02 rho: 9.36e-01 mu: 8.07e+06 li:  1 it: 1.34e+00 tt: 5.23e+01

  39: f: 2.037031e+04 d:-8.04e-01 g: 0.00e+00 h: 1.30e+03 rho:-9.60e-01 mu: 4.03e+06 li:  1 it: 1.24e+00 tt: 5.35e+01

  40: f: 2.036896e+04 d: 1.35e+00 g: 4.35e+05 h: 7.96e+02 rho: 1.63e+00 mu: 1.21e+07 li:  1 it: 1.35e+00 tt: 5.49e+01

  41: f: 2.036896e+04 d:-1.70e+01 g: 0.00e+00 h: 1.82e+03 rho:-1.06e+01 mu: 6.05e+06 li:  1 it: 1.23e+00 tt: 5.61e+01

  42: f: 2.036555e+04 d: 3.41e+00 g: 1.01e+06 h: 9.85e+02 rho: 2.15e+00 mu: 1.81e+07 li:  1 it: 1.36e+00 tt: 5.75e+01

  43: f: 2.035414e+04 d: 1.14e+01 g: 4.04e+06 h: 2.67e+03 rho: 2.17e+00 mu: 5.44e+07 li:  1 it: 1.33e+00 tt: 5.88e+01

  44: f: 2.032718e+04 d: 2.70e+01 g: 9.18e+06 h: 7.93e+03 rho: 1.91e+00 mu: 1.63e+08 li:  1 it: 1.34e+00 tt: 6.02e+01

  45: f: 2.028814e+04 d: 3.90e+01 g: 9.39e+05 h: 2.38e+04 rho: 2.11e+00 mu: 4.90e+08 li:  1 it: 1.40e+00 tt: 6.16e+01

  46: f: 2.027112e+04 d: 1.70e+01 g: 1.64e+05 h: 7.10e+04 rho: 1.55e+00 mu: 1.47e+09 li:  1 it: 1.36e+00 tt: 6.29e+01

  47: f: 2.026867e+04 d: 2.45e+00 g: 7.54e+04 h: 2.09e+05 rho: 1.20e+00 mu: 4.41e+09 li:  1 it: 1.36e+00 tt: 6.43e+01

  48: f: 2.026785e+04 d: 8.25e-01 g: 6.06e+04 h: 5.93e+05 rho: 1.13e+00 mu: 1.32e+10 li:  1 it: 1.33e+00 tt: 6.56e+01

  49: f: 2.026766e+04 d: 1.87e-01 g: 5.06e+03 h: 1.53e+06 rho: 9.54e-01 mu: 3.97e+10 li:  1 it: 1.34e+00 tt: 6.70e+01

  50: f: 2.026752e+04 d: 1.36e-01 g: 6.90e+02 h: 3.31e+06 rho: 7.74e-01 mu: 4.75e+10 li:  1 it: 1.35e+00 tt: 6.83e+01

  51: f: 2.026738e+04 d: 1.42e-01 g: 7.38e+02 h: 2.23e+06 rho: 1.69e+00 mu: 1.42e+11 li:  1 it: 1.35e+00 tt: 6.97e+01

  52: f: 2.026725e+04 d: 1.35e-01 g: 6.24e+02 h: 4.91e+06 rho: 1.75e+00 mu: 4.27e+11 li:  1 it: 1.34e+00 tt: 7.10e+01

  53: f: 2.026714e+04 d: 1.08e-01 g: 5.40e+02 h: 8.53e+06 rho: 1.74e+00 mu: 1.28e+12 li:  1 it: 1.36e+00 tt: 7.24e+01

  54: f: 2.026707e+04 d: 7.15e-02 g: 4.48e+02 h: 1.28e+07 rho: 1.73e+00 mu: 3.85e+12 li:  1 it: 1.35e+00 tt: 7.37e+01

  55: f: 2.026702e+04 d: 4.44e-02 g: 3.70e+02 h: 1.85e+07 rho: 1.74e+00 mu: 1.15e+13 li:  1 it: 1.34e+00 tt: 7.50e+01

  56: f: 2.026699e+04 d: 3.08e-02 g: 2.98e+02 h: 2.67e+07 rho: 1.82e+00 mu: 3.46e+13 li:  1 it: 1.34e+00 tt: 7.64e+01

  57: f: 2.026696e+04 d: 2.83e-02 g: 2.36e+02 h: 3.85e+07 rho: 1.98e+00 mu: 1.04e+14 li:  1 it: 1.35e+00 tt: 7.77e+01

  58: f: 2.026693e+04 d: 3.49e-02 g: 1.80e+02 h: 5.55e+07 rho: 2.15e+00 mu: 3.11e+14 li:  1 it: 1.33e+00 tt: 7.91e+01

  59: f: 2.026688e+04 d: 5.21e-02 g: 1.29e+02 h: 8.00e+07 rho: 2.26e+00 mu: 9.34e+14 li:  1 it: 1.32e+00 tt: 8.04e+01

  60: f: 2.026679e+04 d: 8.70e-02 g: 9.54e+01 h: 1.15e+08 rho: 2.35e+00 mu: 2.80e+15 li:  1 it: 1.36e+00 tt: 8.17e+01

  61: f: 2.026663e+04 d: 1.58e-01 g: 1.33e+02 h: 1.66e+08 rho: 2.43e+00 mu: 8.41e+15 li:  1 it: 1.34e+00 tt: 8.31e+01

  62: f: 2.026632e+04 d: 3.12e-01 g: 1.96e+02 h: 2.40e+08 rho: 2.54e+00 mu: 1.00e+16 li:  1 it: 1.33e+00 tt: 8.44e+01

  63: f: 2.026566e+04 d: 6.64e-01 g: 3.10e+02 h: 1.37e+08 rho: 2.68e+00 mu: 1.00e+16 li:  1 it: 1.34e+00 tt: 8.58e+01

  64: f: 2.026417e+04 d: 1.49e+00 g: 5.47e+02 h: 9.93e+07 rho: 2.85e+00 mu: 1.00e+16 li:  1 it: 1.33e+00 tt: 8.71e+01

  65: f: 2.026122e+04 d: 2.95e+00 g: 9.75e+02 h: 8.08e+07 rho: 2.87e+00 mu: 1.00e+16 li:  1 it: 1.35e+00 tt: 8.84e+01

  66: f: 2.025875e+04 d: 2.47e+00 g: 8.65e+02 h: 6.94e+07 rho: 2.00e+00 mu: 1.00e+16 li:  1 it: 1.35e+00 tt: 8.98e+01

  67: f: 2.025802e+04 d: 7.27e-01 g: 7.30e+02 h: 6.14e+07 rho: 1.83e+00 mu: 1.00e+16 li:  1 it: 1.34e+00 tt: 9.11e+01

  68: f: 2.025755e+04 d: 4.76e-01 g: 8.04e+02 h: 5.54e+07 rho: 2.08e+00 mu: 1.00e+16 li:  1 it: 1.34e+00 tt: 9.25e+01

  69: f: 2.025709e+04 d: 4.53e-01 g: 9.25e+02 h: 5.07e+07 rho: 2.15e+00 mu: 1.00e+16 li:  1 it: 1.35e+00 tt: 9.38e+01

  70: f: 2.025671e+04 d: 3.80e-01 g: 8.34e+02 h: 4.69e+07 rho: 1.97e+00 mu: 1.00e+16 li:  1 it: 1.35e+00 tt: 9.52e+01

  71: f: 2.025654e+04 d: 1.79e-01 g: 4.57e+02 h: 4.38e+07 rho: 1.62e+00 mu: 1.00e+16 li:  1 it: 1.34e+00 tt: 9.65e+01

  72: f: 2.025650e+04 d: 3.82e-02 g: 1.62e+02 h: 4.12e+07 rho: 1.40e+00 mu: 1.00e+16 li:  1 it: 1.35e+00 tt: 9.79e+01

I1123 21:40:15.462482 2026492688 trust_region_minimizer.cc:376] Terminating. Function tolerance reached. |cost_change|/cost: 2.53889e-07 <= 1e-06

Is this something I need to be concerned about or is this normal? Let me know if any additional information may be helpful for you.

Thanks in advance!

[Sameer Agarwal]

Johannes,

The short answer is, it is not anything to worry about.

The long answer is, it happens as the LM step computation is factorizing the Gauss-Newton hessian, and it maybe poorly conditions/rank deficient, in which case the factorization breaks down. Ceres handles it by increasing the regularization on the linear system and trying to solve again. Which is what you observe by looking at the log.

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/aa4ae053-491b-4511-bb9f-ec45e787882d%40googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Johannes Schönberger]

Sameer

Great and thanks a lot for your immediate reply!

Johannes

> You received this message because you are subscribed to a topic in the Google Groups "Ceres Solver" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/ceres-solver/wVieZdOpEc4/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to ceres-solver...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CABqdRUAZz75OEn_1gvh0zqivj7QxVwFXqsYAo%3DEzP4G1%2BjUhqA%40mail.gmail.com.