Question

[melhashash]

Hi Nikolaus,

Thanks for open-sourcing the code.

Would you please explain how rootba method is different from DENSE_QR solver in Ceres? I presume this one avoids the computation of the Hessian and not scalable for large problems, similar to rootba.

[NikolausDemmel]

Hi Mostafa,

thanks for your interest.

DENSE_QR in Ceres is a very different solver and unsuitable for all but the smallest BA problems, but there are similarities. Some points:

• DENSE_QR stores the Jacobian matrix for the whole problem (w.r.t. landmarks und cameras) as one dense matrix and does QR on that. Even just storing that matrix will make the solver run out of memory for medium or large problems. But for very small problems it can be good. (Ceres docs: "For small problems (a couple of hundred parameters and a few thousand residuals) with relatively dense Jacobians, DENSE_QR is the method of choice [Bjorck].")
• It's true that rootba also doesn't scale well to very large or very dense problems b/c of the memory use, but there is still orders of magnitude difference in the memory use compared to DENSE_QR.
• In rootba we do a partial QR on the Jacobian, by bringing only the landmark part of the Jacobian in upper Rectangular form. Moreover, we exploit the sparsity structure, and do this partial QR on dense memory blocks per landmark. This is crucial for good performance, but it's specific to the problem (BA), whereas DENSE_QR is general purpose and works (in principle) for any problem.
• DENSE_QR is also a "square root" approach, like rootba. It doesn't compute the Hessian and stays in "Jacobian form" (even more so than rootba, since after "square root landmark elimination" we still do PCG on the reduced camera system in squared form, even if we don't explicitly compute Hessian and gradient). Thus, the numeric properties of DENSE_QR should be similar to rootba, or even better (i.e. it should also work well with single-precision, if Ceres supported that).

[melhashash]

Thanks so much, Nikolaus, for the detailed explanation.