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

 %!TEX root = ceres.tex
 \chapter{Frequently Asked Questions}
 \label{chapter:faq}
 \commentsoff{Question}
 \commentsoff{Answer}
 \begin{enumerate}
 \item \begin{Question}
 Why does Ceres use blocks (ParameterBlocks and ResidualBlocks) ?
 \end{Question}\\ \\
 \begin{Answer}
 Most non-linear solvers we are aware of, define the problem and residuals in terms of scalars and it is possible to do this with Ceres also. However, it is our experience that in most problems small groups of scalars occur together. For example the three components of a translation vector and the four components of the quaternion that define the pose of a camera. Same is true for residuals, where it is common to have small vectors of residuals rather than just scalars. There are a number of advantages of using blocks. It saves on indexing information, which for large problems can be substantial. Blocks translate into contiguous storage in memory which is more cache friendly and last but not the least, it allows us to use SIMD/SSE based BLAS routines to significantly speed up various matrix operations.
 \end{Answer}

 \item \begin{Question}
 	What is a good ParameterBlock?
 \end{Question}\\ \\
 \begin{Answer}
 In most problems there is a natural parameter block structure, as there is a semantic meaning associated with groups of scalars -- mean vector of a distribution, color of a pixel etc. To group two scalar variables,  ask yourself if residual blocks will always use these two variables together. If the answer is yes, then the two variables belong to the same parameter block.
 \end{Answer}

 \item \begin{Question}
 	What is a good ResidualBlock?
 \end{Question}\\ \\
 \begin{Answer}
 While it is often the case that problems have a natural blocking of parameters into parameter blocks, it is not always clear what a good residual block structure is.  One rule of thumb for non-linear least squares problems since they often come from data fitting problems is to create one residual block per observation. So if you are solving a Structure from Motion problem, one 2 dimensional residual block per 2d image projection is a good idea.

 The flips side is that sometimes, when modeling the problem it is tempting to group a large number of residuals together into a single residual block as it reduces the  number of CostFunctions you have to define.

 For example consider the following residual block of size 18 which depends on four parameter blocks of size 4 each. Shown below is the Jacobian structure of this residual block, the numbers in the columns indicate the size, and the  numbers in the rows show a grouping of the matrix that best capture its sparsity structure. \texttt{X} indicates a non-zero block, the rest of the blocks are zero.

 \begin{equation*}
 \begin{matrix}
  	& 4	& 4	& 4	& 4 \\
  2	& \texttt{X}	& \texttt{X}	& \texttt{X}	& \texttt{X} \\
  4	& \texttt{X}	& 	& 	&   \\
  4	& 	& \texttt{X}	& 	&   \\
  4	& 	& 	& \texttt{X}	&   \\
  4	& 	& 	& 	& \texttt{X} \\
 \end{matrix}
 \end{equation*}

 Notice that out of the 20 cells, only 8 are non-zero, in fact out of the 288 entries only 48 entries are non-zero, thus we are hiding substantial sparsity from the solver, and using up much more memory. It is much better to break this up into 5 residual blocks. One residual block of size 2 that depends on all four parameter block and four residual blocks of size 4 each that depend on one parameter block at a time.
 \end{Answer}

 \item \begin{Question}
 Can I set part of a parameter block constant?
 \end{Question}\\ \\
 \begin{Answer}
 Yes, use \texttt{SubsetParameterization} as a local parameterization for the parameter block of interest. See \texttt{local\_parameterization.h} for more details.
 \end{Answer}


 \item \begin{Question}
 Can Ceres solve constrained non-linear least squares?
 \end{Question}\\ \\
 \begin{Answer}
 Not at this time. We have some ideas on how to do this, but we have not had very many requests to justify the effort involved. If you have a problem that requires such a functionality we would like to hear about it as it will help us decide directions for future work. In the meanwhile, if you are interested in solving bounds constrained problems, consider using some of the tricks described by John D'Errico in his fminsearchbnd toolkit~\footnote{\url{http://www.mathworks.com/matlabcentral/fileexchange/8277-fminsearchbnd}}.
 \end{Answer}

 \item \begin{Question}
 Can Ceres solve problems that cannot be written as robustified non-linear least squares?
 \end{Question}\\ \\
 \begin{Answer}
 No. Ceres was designed from the grounds up to be a non-linear least squares solver. Currently we have no plans of extending it into a general purpose non-linear solver.
 \end{Answer}
 \end{enumerate}
	%!TEX root = ceres.tex
	\chapter{Frequently Asked Questions}
	\label{chapter:faq}
	\commentsoff{Question}
	\commentsoff{Answer}
	\begin{enumerate}
	\item \begin{Question}
	Why does Ceres use blocks (ParameterBlocks and ResidualBlocks) ?
	\end{Question}\\ \\
	\begin{Answer}
	Most non-linear solvers we are aware of, define the problem and residuals in terms of scalars and it is possible to do this with Ceres also. However, it is our experience that in most problems small groups of scalars occur together. For example the three components of a translation vector and the four components of the quaternion that define the pose of a camera. Same is true for residuals, where it is common to have small vectors of residuals rather than just scalars. There are a number of advantages of using blocks. It saves on indexing information, which for large problems can be substantial. Blocks translate into contiguous storage in memory which is more cache friendly and last but not the least, it allows us to use SIMD/SSE based BLAS routines to significantly speed up various matrix operations.
	\end{Answer}

	\item \begin{Question}
	What is a good ParameterBlock?
	\end{Question}\\ \\
	\begin{Answer}
	In most problems there is a natural parameter block structure, as there is a semantic meaning associated with groups of scalars -- mean vector of a distribution, color of a pixel etc. To group two scalar variables, ask yourself if residual blocks will always use these two variables together. If the answer is yes, then the two variables belong to the same parameter block.
	\end{Answer}

	\item \begin{Question}
	What is a good ResidualBlock?
	\end{Question}\\ \\
	\begin{Answer}
	While it is often the case that problems have a natural blocking of parameters into parameter blocks, it is not always clear what a good residual block structure is. One rule of thumb for non-linear least squares problems since they often come from data fitting problems is to create one residual block per observation. So if you are solving a Structure from Motion problem, one 2 dimensional residual block per 2d image projection is a good idea.

	The flips side is that sometimes, when modeling the problem it is tempting to group a large number of residuals together into a single residual block as it reduces the number of CostFunctions you have to define.

	For example consider the following residual block of size 18 which depends on four parameter blocks of size 4 each. Shown below is the Jacobian structure of this residual block, the numbers in the columns indicate the size, and the numbers in the rows show a grouping of the matrix that best capture its sparsity structure. \texttt{X} indicates a non-zero block, the rest of the blocks are zero.

	\begin{equation*}
	\begin{matrix}
	& 4 & 4 & 4 & 4 \\
	2 & \texttt{X} & \texttt{X} & \texttt{X} & \texttt{X} \\
	4 & \texttt{X} & & & \\
	4 & & \texttt{X} & & \\
	4 & & & \texttt{X} & \\
	4 & & & & \texttt{X} \\
	\end{matrix}
	\end{equation*}

	Notice that out of the 20 cells, only 8 are non-zero, in fact out of the 288 entries only 48 entries are non-zero, thus we are hiding substantial sparsity from the solver, and using up much more memory. It is much better to break this up into 5 residual blocks. One residual block of size 2 that depends on all four parameter block and four residual blocks of size 4 each that depend on one parameter block at a time.
	\end{Answer}

	\item \begin{Question}
	Can I set part of a parameter block constant?
	\end{Question}\\ \\
	\begin{Answer}
	Yes, use \texttt{SubsetParameterization} as a local parameterization for the parameter block of interest. See \texttt{local\_parameterization.h} for more details.
	\end{Answer}


	\item \begin{Question}
	Can Ceres solve constrained non-linear least squares?
	\end{Question}\\ \\
	\begin{Answer}
	Not at this time. We have some ideas on how to do this, but we have not had very many requests to justify the effort involved. If you have a problem that requires such a functionality we would like to hear about it as it will help us decide directions for future work. In the meanwhile, if you are interested in solving bounds constrained problems, consider using some of the tricks described by John D'Errico in his fminsearchbnd toolkit~\footnote{\url{http://www.mathworks.com/matlabcentral/fileexchange/8277-fminsearchbnd}}.
	\end{Answer}

	\item \begin{Question}
	Can Ceres solve problems that cannot be written as robustified non-linear least squares?
	\end{Question}\\ \\
	\begin{Answer}
	No. Ceres was designed from the grounds up to be a non-linear least squares solver. Currently we have no plans of extending it into a general purpose non-linear solver.
	\end{Answer}
	\end{enumerate}