docs/introduction.tex - ceres-solver - Git at Google

 %!TEX root = ceres.tex
 \chapter{Introduction}
 \label{sec:introduction}
 Ceres Solver\footnote{For brevity, in the rest of this document we will just use the term Ceres.} is a non-linear least squares solver developed at Google. It is designed to solve small and large sparse problems accurately and efficiently~\footnote{For a gentle but brief introduction to non-liner least squares problems, please start by reading the~\hyperref[chapter:tutorial]{Tutorial}}. Amongst its various features is a simple but expressive API with support for automatic differentiation, robust norms, local parameterizations, automatic gradient checking, multithreading and automatic problem structure detection.

 The key computational cost when solving a non-linear least squares problem is the solution of a linear least squares problem in each iteration. To this end Ceres supports a number of different linear solvers suited for different needs. This includes dense QR factorization (using \eigen) for small scale problems, sparse Cholesky factorization (using \cholmod) for general sparse problems and specialized Schur complement based solvers for problems that arise in multi-view geometry~\cite{hartley-zisserman-book-2004}.

 Ceres has been used for solving a variety of problems in computer vision and machine learning at Google with sizes that range from a tens of variables and objective functions with a few hundred terms to problems with millions of variables and objective functions with tens of millions of terms.

 \section{What's in a name?}
 While there is some debate as to who invented of the method of Least Squares~\cite{stigler1981gauss}. There is no debate that it was Carl Friedrich Gauss's prediction of the orbit of the newly discovered asteroid Ceres based on just 41 days of observations that brought it to the attention of the world~\cite{tennenbaum-director}. We named our solver after Ceres to celebrate this seminal event in the history of astronomy, statistics and optimization.

 \section{Contributing to Ceres}
 We welcome contributions to Ceres, whether they are new features, bug fixes or tests. If you have ideas on how you would like to contribute to Ceres, please join the Ceres mailing list (\texttt{ceres-solver@googlegroups.com}) or if you are looking for ideas, please let us know about your interest and skills and we will be happy to make a suggestion or three.

 We follow Google's C++ Style Guide~\footnote{\url{http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml}}.

 \section{Acknowledgements}
 A number of people have helped with the development and open sourcing of Ceres.

 Fredrik Schaffalitzky when he was at Google started the development of Ceres, and even though much has changed since then, many of the ideas from his original design are still present in the current code.

 Amongst Ceres' users at Google two deserve special mention: William Rucklidge and James Roseborough. William was the first user of Ceres. He bravely took on the task of porting production code to an as-yet unproven optimization library, reporting bugs and helping fix them along the way. James is perhaps the most sophisticated used of Ceres at Google. He has reported and fixed bugs and helped evolve the API for the better.

 Nathan Wiegand contributed the MacOS port.
 \clearpage

 \section{License}
 Ceres Solver is licensed under the New BSD license, whose terms are as follows.

 \begin{quotation}

 \noindent
 Copyright (c) 2010, 2011, 2012, Google Inc. All rights reserved.

 \noindent
 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are met:
 \begin{enumerate}
 \item Redistributions of source code must retain the above copyright notice,
       this list of conditions and the following disclaimer.
 \item Redistributions in binary form must reproduce the above copyright notice,
       this list of conditions and the following disclaimer in the documentation
       and/or other materials provided with the distribution.
 \item Neither the name of Google Inc.,  nor the names of its contributors may
       be used to endorse or promote products derived from this software without
       specific prior written permission.
 \end{enumerate}

 \noindent
 This software is provided by the copyright holders and contributors "AS IS" and
 any express or implied warranties, including, but not limited to, the implied
 warranties of merchantability and fitness for a particular purpose are
 disclaimed. In no event shall Google Inc. be liable for any direct, indirect,
 incidental, special, exemplary, or consequential damages (including, but not
 limited to, procurement of substitute goods or services; loss of use, data, or
 profits; or business interruption) however caused and on any theory of
 liability, whether in contract, strict liability, or tort (including negligence
 or otherwise) arising in any way out of the use of this software, even if
 advised of the possibility of such damage.
 \end{quotation}
	%!TEX root = ceres.tex
	\chapter{Introduction}
	\label{sec:introduction}
	Ceres Solver\footnote{For brevity, in the rest of this document we will just use the term Ceres.} is a non-linear least squares solver developed at Google. It is designed to solve small and large sparse problems accurately and efficiently~\footnote{For a gentle but brief introduction to non-liner least squares problems, please start by reading the~\hyperref[chapter:tutorial]{Tutorial}}. Amongst its various features is a simple but expressive API with support for automatic differentiation, robust norms, local parameterizations, automatic gradient checking, multithreading and automatic problem structure detection.

	The key computational cost when solving a non-linear least squares problem is the solution of a linear least squares problem in each iteration. To this end Ceres supports a number of different linear solvers suited for different needs. This includes dense QR factorization (using \eigen) for small scale problems, sparse Cholesky factorization (using \cholmod) for general sparse problems and specialized Schur complement based solvers for problems that arise in multi-view geometry~\cite{hartley-zisserman-book-2004}.

	Ceres has been used for solving a variety of problems in computer vision and machine learning at Google with sizes that range from a tens of variables and objective functions with a few hundred terms to problems with millions of variables and objective functions with tens of millions of terms.

	\section{What's in a name?}
	While there is some debate as to who invented of the method of Least Squares~\cite{stigler1981gauss}. There is no debate that it was Carl Friedrich Gauss's prediction of the orbit of the newly discovered asteroid Ceres based on just 41 days of observations that brought it to the attention of the world~\cite{tennenbaum-director}. We named our solver after Ceres to celebrate this seminal event in the history of astronomy, statistics and optimization.

	\section{Contributing to Ceres}
	We welcome contributions to Ceres, whether they are new features, bug fixes or tests. If you have ideas on how you would like to contribute to Ceres, please join the Ceres mailing list (\texttt{ceres-solver@googlegroups.com}) or if you are looking for ideas, please let us know about your interest and skills and we will be happy to make a suggestion or three.

	We follow Google's C++ Style Guide~\footnote{\url{http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml}}.

	\section{Acknowledgements}
	A number of people have helped with the development and open sourcing of Ceres.

	Fredrik Schaffalitzky when he was at Google started the development of Ceres, and even though much has changed since then, many of the ideas from his original design are still present in the current code.

	Amongst Ceres' users at Google two deserve special mention: William Rucklidge and James Roseborough. William was the first user of Ceres. He bravely took on the task of porting production code to an as-yet unproven optimization library, reporting bugs and helping fix them along the way. James is perhaps the most sophisticated used of Ceres at Google. He has reported and fixed bugs and helped evolve the API for the better.

	Nathan Wiegand contributed the MacOS port.
	\clearpage

	\section{License}
	Ceres Solver is licensed under the New BSD license, whose terms are as follows.

	\begin{quotation}

	\noindent
	Copyright (c) 2010, 2011, 2012, Google Inc. All rights reserved.

	\noindent
	Redistribution and use in source and binary forms, with or without
	modification, are permitted provided that the following conditions are met:
	\begin{enumerate}
	\item Redistributions of source code must retain the above copyright notice,
	this list of conditions and the following disclaimer.
	\item Redistributions in binary form must reproduce the above copyright notice,
	this list of conditions and the following disclaimer in the documentation
	and/or other materials provided with the distribution.
	\item Neither the name of Google Inc., nor the names of its contributors may
	be used to endorse or promote products derived from this software without
	specific prior written permission.
	\end{enumerate}

	\noindent
	This software is provided by the copyright holders and contributors "AS IS" and
	any express or implied warranties, including, but not limited to, the implied
	warranties of merchantability and fitness for a particular purpose are
	disclaimed. In no event shall Google Inc. be liable for any direct, indirect,
	incidental, special, exemplary, or consequential damages (including, but not
	limited to, procurement of substitute goods or services; loss of use, data, or
	profits; or business interruption) however caused and on any theory of
	liability, whether in contract, strict liability, or tort (including negligence
	or otherwise) arising in any way out of the use of this software, even if
	advised of the possibility of such damage.
	\end{quotation}