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.