.. _chapter-tricks:

===================
Tips, Tricks & FAQs
===================

A collection of miscellanous tips, tricks and answers to frequently
asked questions.

1. Use analytical/automatic derivatives when possible.

   This is the single most important piece of advice we can give to
   you. It is tempting to take the easy way out and use numeric
   differentiation. This is a bad idea. Numeric differentiation is
   slow, ill-behaved, hard to get right, and results in poor
   convergence behaviour.

   Ceres allows the user to define templated functors which will
   be automatically differentiated. For most situations this is enough
   and we recommend using this facility. In some cases the derivatives
   are simple enough or the performance considerations are such that
   the overhead of automatic differentiation is too much. In such
   cases, analytic derivatives are recommended.

   The use of numerical derivatives should be a measure of last
   resort, where it is simply not possible to write a templated
   implementation of the cost function.

   In many cases where it is not possible to do analytic or automatic
   differentiation of the entire cost function. But it is generally
   the case that it is possible to decompose the cost function into
   parts that need to be numerically differentiated and parts that can
   be automatically or analytically differentiated.

   To this end, Ceres has extensive support for mixing analytic,
   automatic and numeric differentiation. See
   :class:`NumericDiffFunctor` and :class:`CostFunctionToFunctor`.


2. Use `google-glog <http://code.google.com/p/google-glog>`_.

   Ceres has extensive support for logging various stages of the
   solve. This includes detailed information about memory allocations
   and time consumed in various parts of the solve, internal error
   conditions etc. This logging structure is built on top of the
   `google-glog <http://code.google.com/p/google-glog>`_ library and
   can easily be controlled from the command line.

   We use it extensively to observe and analyze Ceres's
   performance. Starting with ``-logtostdterr`` you can add ``-v=N``
   for increasing values of N to get more and more verbose and
   detailed information about Ceres internals.

   Building Ceres like this introduces an external dependency, and it
   is tempting instead to use the `miniglog` implementation that ships
   inside Ceres instead. This is a bad idea.

   ``miniglog`` was written primarily for building and using Ceres on
   Android because the current version of `google-glog
   <http://code.google.com/p/google-glog>`_ does not build using the
   NDK. It has worse performance than the full fledged glog library
   and is much harder to control and use.

3. `Solver::Summary::FullReport` is your friend.

   When diagnosing Ceres performance issues - runtime and convergence,
   the first place to start is by looking at the output of
   ``Solver::Summary::FullReport``. Here is an example

   .. code-block:: bash

     ./bin/bundle_adjuster --input ../data/problem-16-22106-pre.txt


     0: f: 4.185660e+06 d: 0.00e+00 g: 2.16e+07 h: 0.00e+00 rho: 0.00e+00 mu: 1.00e+04 li:  0 it: 9.20e-02 tt: 3.35e-01
     1: f: 1.980525e+05 d: 3.99e+06 g: 5.34e+06 h: 2.40e+03 rho: 9.60e-01 mu: 3.00e+04 li:  1 it: 1.99e-01 tt: 5.34e-01
     2: f: 5.086543e+04 d: 1.47e+05 g: 2.11e+06 h: 1.01e+03 rho: 8.22e-01 mu: 4.09e+04 li:  1 it: 1.61e-01 tt: 6.95e-01
     3: f: 1.859667e+04 d: 3.23e+04 g: 2.87e+05 h: 2.64e+02 rho: 9.85e-01 mu: 1.23e+05 li:  1 it: 1.63e-01 tt: 8.58e-01
     4: f: 1.803857e+04 d: 5.58e+02 g: 2.69e+04 h: 8.66e+01 rho: 9.93e-01 mu: 3.69e+05 li:  1 it: 1.62e-01 tt: 1.02e+00
     5: f: 1.803391e+04 d: 4.66e+00 g: 3.11e+02 h: 1.02e+01 rho: 1.00e+00 mu: 1.11e+06 li:  1 it: 1.61e-01 tt: 1.18e+00

     Ceres Solver Report
     -------------------
                                          Original                  Reduced
     Parameter blocks                        22122                    22122
     Parameters                              66462                    66462
     Residual blocks                         83718                    83718
     Residual                               167436                   167436

     Minimizer                        TRUST_REGION

     Sparse linear algebra library    SUITE_SPARSE
     Trust region strategy     LEVENBERG_MARQUARDT

                                              Given                     Used
     Linear solver                    SPARSE_SCHUR             SPARSE_SCHUR
     Threads                                     1                        1
     Linear solver threads                       1                        1
     Linear solver ordering              AUTOMATIC                22106, 16

     Cost:
     Initial                          4.185660e+06
     Final                            1.803391e+04
     Change                           4.167626e+06

     Minimizer iterations                        5
     Successful steps                            5
     Unsuccessful steps                          0

     Time (in seconds):
     Preprocessor                            0.243

       Residual evaluation                   0.053
       Jacobian evaluation                   0.435
       Linear solver                         0.371
     Minimizer                               0.940

     Postprocessor                           0.002
     Total                                   1.221

     Termination:                   NO_CONVERGENCE (Maximum number of iterations reached.)

  Let us focus on run-time performance. The relevant lines to look at
  are


   .. code-block:: bash

     Time (in seconds):
     Preprocessor                            0.243

       Residual evaluation                   0.053
       Jacobian evaluation                   0.435
       Linear solver                         0.371
     Minimizer                               0.940

     Postprocessor                           0.002
     Total                                   1.221

  Which tell us that of the total 1.2 seconds, about .4 seconds was
  spent in the linear solver and the rest was mostly spent in
  preprocessing and jacobian evaluation.

  The preprocessing seems particularly expensive. Looking back at the
  report, we observe

   .. code-block:: bash

     Linear solver ordering              AUTOMATIC                22106, 16

  Which indicates that we are using automatic ordering for the
  ``SPARSE_SCHUR`` solver. This can be expensive at times. A straight
  forward way to deal with this is to give the ordering manually. For
  ``bundle_adjuster`` this can be done by passing the flag
  ``-ordering=user``. Doing so and looking at the timing block of the
  full report gives us

   .. code-block:: bash

     Time (in seconds):
     Preprocessor                            0.058

       Residual evaluation                   0.050
       Jacobian evaluation                   0.416
       Linear solver                         0.360
     Minimizer                               0.903

     Postprocessor                           0.002
     Total                                   0.998

  The preprocessor time has gone down by more than 4x!.


4. Putting `Inverse Function Theorem
   <http://en.wikipedia.org/wiki/Inverse_function_theorem>`_ to use.

   Every now and then we have to deal with functions which cannot be
   evaluated analytically. Computing the Jacobian in such cases is
   tricky. A particularly interesting case is where the inverse of the
   function is easy to compute analytically. An example of such a
   function is the Coordinate transformation between the `ECEF
   <http://en.wikipedia.org/wiki/ECEF>`_ and the `WGS84
   <http://en.wikipedia.org/wiki/World_Geodetic_System>`_ where the
   conversion from WGS84 to ECEF is analytic, but the conversion back
   to ECEF uses an iterative algorithm. So how do you compute the
   derivative of the ECEF to WGS84 transformation?

   One obvious approach would be to numerically
   differentiate the conversion function. This is not a good idea. For
   one, it will be slow, but it will also be numerically quite
   bad.

   Turns out you can use the `Inverse Function Theorem
   <http://en.wikipedia.org/wiki/Inverse_function_theorem>`_ in this
   case to compute the derivatives more or less analytically.

   The key result here is. If :math:`x = f^{-1}(y)`, and :math:`Df(x)`
   is the invertible Jacobian of :math:`f` at :math:`x`. Then the
   Jacobian :math:`Df^{-1}(y) = [Df(x)]^{-1}`, i.e., the Jacobian of
   the :math:`f^{-1}` is the inverse of the Jacobian of :math:`f`.

   Algorithmically this means that given :math:`y`, compute :math:`x =
   f^{-1}(y)` by whatever means you can. Evaluate the Jacobian of
   :math:`f` at :math:`x`. If the Jacobian matrix is invertible, then
   the inverse is the Jacobian of the inverse at :math:`y`.

   One can put this into practice with the following code fragment.

   .. code-block:: c++

      Eigen::Vector3d ecef; // Fill some values
      // Iterative computation.
      Eigen::Vector3d lla = ECEFToLLA(ecef);
      // Analytic derivatives
      Eigen::Matrix3d lla_to_ecef_jacobian = LLAToECEFJacobian(lla);
      bool invertible;
      Eigen::Matrix3d ecef_to_lla_jacobian;
      lla_to_ecef_jacobian.computeInverseWithCheck(ecef_to_lla_jacobian, invertible);