Inquiry about Schur complement and marginalization in theseus

[kamzero]

Hi there,

I am interested in using the theseus library for bundle adjustment in my research project, and I have a couple of questions about its capabilities. Specifically, I was wondering:

• Does the theseus library support Schur complement for the sparse Hessian matrix in bundle adjustment?
• Does the theseus library support marginalization for specified camera and landmark points in sliding window bundle adjustment?

I would greatly appreciate any information you could provide on these questions. Thank you very much for your time and assistance!

Best regards,
kamzero

[mhmukadam]

Hi @kamzero thanks for your interest!

Currently we do not support those two. However, if you are using BaSpaCho solver you won't need Schur complement since the solver is built to work without it. @maurimo (author) can share further insights if you have questions. Also tagging @fantaosha if you have anything to add.

[maurimo]

Great question!
In short (more details on BaSpaCho github page):
Cholesky decomposition, marginalization and Schur complement are essentially the same thing (if we allow some confusion of the languages of probability and linear algebra): Cholesky decomposition works doing iterative marginalization, while Schur complement (as used in bundle adjustment) is the realization that hey, you can marginalize simulateneously all the points, and can do so in parallel.
Since the best Cholesky solvers (like CHOLMOD) are of supernodal type, it means that they get their speed from adding some zero fill and using dense BLAS operations, but this strategy is very bad in the case of marginalization of points in bundle adjustment as the camera-point matrix is very sparse and little structured. Therefore traditionally (eg Ceres) do a separate Schur complement step, to spoon feed a partly solved problem to the supernodal sparse solver.
Theseus solver BaSpaCho has this "sparse elimination" strategy (akin to Schur complement) built-in and doesn't need to do a separate Schur complement step, but you will get the same speed as the combination of Schur complement + supernodal solver (assuming the points are correctly ordered "first", this can be hinted in C++ but it's not yet available in Theseus wrapper). About the ordering, in practice you can rely on the ordering heuristic to be doing the right thing, but this explicit hinting might be added to Theseus one day.
About marginalization: a way to build a marginal covariance is by computing a "partial" Cholesky decomposition (with a prescribed ordering keeping at the beginning the parameters you want to marginalize, then you stop Cholesky decomposition after processing only the relative columns), and this is something BaSpaCho is well able to do and I've been using it heavily from my C++ code, but it's not yet exported by Theseus. However the "engine" is there and it would not be hard to add some code to the Python wrapper to make the sparse solver return you the marginal covariance.
Where "sliding window" is concerned I think what you want is being able to build at the next window a BA problem using the marginal covariance on a subset of parameters coming from the previous window. Not sure if Theseus allows this at the time being however?

On a practical note, probably you're better off doing sliding window directly in C++, unless you want to do differentiable sliding window, and then you need Theseus support for differentiable optimization? I think this is not something that is currently supported by Theseus, but here I think @mhmukadam @luisenp can correct me!

[kamzero]

Thank you for your prompt and helpful response to my inquiry. Your explanation on the relationship between Cholesky decomposition, marginalization and Schur complement was very clear and greatly helped me to understand the engineering tools available for my project.

Regarding the second point, I appreciate your confirmation that theseus does not currently support differentiable sliding window bundle adjustment. I will consider alternative approaches for achieving this functionality.

Thank you again for your time and assistance.