xref: /external/ceres-solver/docs/introduction.tex

%!TEX root = ceres-solver.tex
\chapter{Introduction}
\label{chapter: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[part: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 \texttt{SuiteSparse}) 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 Solver}

We welcome contributions to Ceres, whether they are new features, bug fixes or tests. The Ceres mailing list\footnote{\url{http://groups.google.com/group/ceres-solver}} is the best place for all development related discussions. Please consider joining it. If you have ideas on how you would like to contribute to Ceres, it is a good idea to let us know on the mailinglist before you start development. We may have suggestions that will save effort when trying to merge your work into the main branch. 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}} and use \texttt{git} for version control.

\section{Citing Ceres Solver}
If you use Ceres for an academic publication, please cite this manual. e.g.,
\begin{verbatim}
@manual{ceres-manual,
	Author = {Sameer Agarwal and Keir Mierle},
	Title = {Ceres Solver: Tutorial \& Reference},
	Organization = {Google Inc.}
}
\end{verbatim}
	

\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 user of Ceres at Google. He has reported and fixed bugs and helped evolve the API for the better.

Nathan Wiegand contributed the MacOS port.


\chapter{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}