OpenOF Framework for Sparse Non-linear Least Squares Optimization on a GPU

2013-3-2
OpenOF Framework for Sparse Non-linear Least Squares Optimization on a GPU
With OpenOF, a framework is presented, which enables developers to design sparse optimizations regarding parameters and measurements and utilize the parallel power of a GPU


This code is written in Python with three major libraries: Thrust, CUSP and SymPy. Code framework is written in Python but can also generate C++ code.


Code website
https://github.com/OpenOF/OpenOF

Process of Nonlinear least squares optimization: 
1. Iterative method
2. Linearize the cost function in each iteration
3. Levenberg-Marquardt(LM) algorithm is standard, combing the Gauss-Newton algorithm with the gradient descent approach. LM guarantees convergence.
4. In each interation , solving linear Ax = b is most intensive.
5. Sparse matrix representation is used: sparseLM (Lourakis, 2010) and g2o (Kummerle et al., 2011), but on CPU
6. Solving Ax =b, many algorithms can achieve, Cholesky docomposition A = LDL'
7. this paper use Conjugate gradient (CG) approach on GPU.

Nonlinear least squares optimization is widely used in SLAM and BA. 
The authors' some comments about three BA libraries:
   1.The SBA library (Lourakis and Argyros,2009) takes advantage of the special structure of the Hessian matrix to apply the Schur complement for solving the linear system. Nevertheless it has several drawbacks. Integrating additional parameters which remain identical for all measurements (e.g. camera calibration) is not possible, as the structure would change such that the Schur complement could not be applied anymore.

2. sparseLM (Lourakis, 2010) is slow.
3. g2o: the Jacobian is evaluated by numerical differentiation which is time consuming and also degrades the convergence rate.
4. ISAM: (Kaess et al., 2011),which address only a subset of problems, have been presented previously for least squares optimization

Overall Comment: this paper is claims to present an open source framework for sparse nonlinear opitmization. The cost functions is described in high level scripting language. It can not be used without GPU yet. It seems for me g2o or iSam would be more useful on CPU.