Background Reading

For a short but informative introduction to the subject we recommend the booklet by [Madsen] . For a general introduction to non-linear optimization we recommend [NocedalWright]. [Bjorck] remains the seminal reference on least squares problems. [TrefethenBau] is our favorite text on introductory numerical linear algebra. [Triggs] provides a thorough coverage of the bundle adjustment problem.



S. Agarwal, N. Snavely, S. M. Seitz and R. Szeliski, Bundle Adjustment in the Large, Proceedings of the European Conference on Computer Vision, pp. 29–42, 2010.


A. Bjorck, Numerical Methods for Least Squares Problems, SIAM, 1996


D. C. Brown, A solution to the general problem of multiple station analytical stereo triangulation, Technical Report 43, Patrick Airforce Base, Florida, 1958.


R. H. Byrd, J. Nocedal, R. B. Schanbel, Representations of Quasi-Newton Matrices and their use in Limited Memory Methods, Mathematical Programming 63(4):129-156, 1994.


R.H. Byrd, R.B. Schnabel, and G.A. Shultz, Approximate solution of the trust region problem by minimization over two dimensional subspaces, Mathematical programming, 40(1):247-263, 1988.


Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam, Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate, TOMS, 35(3), 2008.


A.R. Conn, N.I.M. Gould, and P.L. Toint, Trust region methods, Society for Industrial Mathematics, 2000.


F. Dellaert, J. Carlson, V. Ila, K. Ni and C. E. Thorpe, Subgraph-preconditioned conjugate gradients for large scale SLAM, International Conference on Intelligent Robots and Systems, 2010.


G.H. Golub and V. Pereyra, The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate, SIAM Journal on numerical analysis, 10(2):413-432, 1973.


N. Gould and J. Scott, The State-of-the-Art of Preconditioners for Sparse Linear Least-Squares Problems, ACM Trans. Math. Softw., 43(4), 2017.


R.I. Hartley & A. Zisserman, Multiview Geometry in Computer Vision, Cambridge University Press, 2004.


C. Hertzberg, R. Wagner, U. Frese and L. Schroder, Integrating Generic Sensor Fusion Algorithms with Sound State Representations through Encapsulation of Manifolds, Information Fusion, 14(1):57-77, 2013.


K. Kanatani and D. D. Morris, Gauges and gauge transformations for uncertainty description of geometric structure with indeterminacy, IEEE Transactions on Information Theory 47(5):2017-2028, 2001.


R. G. Keys, Cubic convolution interpolation for digital image processing, IEEE Trans. on Acoustics, Speech, and Signal Processing, 29(6), 1981.


A. Kushal and S. Agarwal, Visibility based preconditioning for bundle adjustment, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2012.


C. Kanzow, N. Yamashita and M. Fukushima, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, Journal of Computational and Applied Mathematics, 177(2):375-397, 2005.


K. Levenberg, A method for the solution of certain nonlinear problems in least squares, Quart. Appl. Math, 2(2):164-168, 1944.


Na Li and Y. Saad, MIQR: A multilevel incomplete qr preconditioner for large sparse least squares problems, SIAM Journal on Matrix Analysis and Applications, 28(2):524-550, 2007.


K. Madsen, H.B. Nielsen, and O. Tingleff, Methods for nonlinear least squares problems, 2004.


J. Mandel, On block diagonal and Schur complement preconditioning, Numer. Math., 58(1):79-93, 1990.


D.W. Marquardt, An algorithm for least squares estimation of nonlinear parameters, J. SIAM, 11(2):431-441, 1963.


T.P.A. Mathew, Domain decomposition methods for the numerical solution of partial differential equations, Springer Verlag, 2008.


S.G. Nash and A. Sofer, Assessing a search direction within a truncated newton method, Operations Research Letters, 9(4):219-221, 1990.


J. Nocedal, Updating Quasi-Newton Matrices with Limited Storage, Mathematics of Computation, 35(151): 773–782, 1980.


J. Nocedal & S. Wright, Numerical Optimization, Springer, 2004.


S. S. Oren, Self-scaling Variable Metric (SSVM) Algorithms Part II: Implementation and Experiments, Management Science, 20(5), 863-874, 1974.


W. H. Press, S. A. Teukolsky, W. T. Vetterling & B. P. Flannery, Numerical Recipes, Cambridge University Press, 2007.


C. J. F. Ridders, Accurate computation of F’(x) and F’(x) F”(x), Advances in Engineering Software 4(2), 75-76, 1978.


A. Ruhe and P.Å. Wedin, Algorithms for separable nonlinear least squares problems, Siam Review, 22(3):318-337, 1980.


Y. Saad, Iterative methods for sparse linear systems, SIAM, 2003.


I. Simon, N. Snavely and S. M. Seitz, Scene Summarization for Online Image Collections, International Conference on Computer Vision, 2007.


S. M. Stigler, Gauss and the invention of least squares, The Annals of Statistics, 9(3):465-474, 1981.


J. Tenenbaum & B. Director, How Gauss Determined the Orbit of Ceres.


L.N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, 1997.


B. Triggs, P. F. Mclauchlan, R. I. Hartley & A. W. Fitzgibbon, Bundle Adjustment: A Modern Synthesis, Proceedings of the International Workshop on Vision Algorithms: Theory and Practice, pp. 298-372, 1999.


T. Wiberg, Computation of principal components when data are missing, In Proc. Second Symp. Computational Statistics, pages 229-236, 1976.


S. J. Wright and J. N. Holt, An Inexact Levenberg Marquardt Method for Large Sparse Nonlinear Least Squares, Journal of the Australian Mathematical Society Series B, 26(4):387-403, 1985.