Generalized Subgraph Preconditioners for Large-Scale Bundle Adjustment

View/ Open
Date
2011-11Author
Jian, Yong-Dian
Balcan, Doru C.
Dellaert, Frank
Metadata
Show full item recordAbstract
We present a generalized subgraph preconditioning
(GSP) technique to solve large-scale bundle adjustment
problems efficiently. In contrast with previous work which
uses either direct or iterative methods as the linear solver,
GSP combines their advantages and is significantly faster
on large datasets. Similar to [11], the main idea is to identify
a sub-problem (subgraph) that can be solved efficiently
by sparse factorization methods and use it to build a preconditioner
for the conjugate gradient method. The difference
is that GSP is more general and leads to much more effective
preconditioners. We design a greedy algorithm to build
subgraphs which have bounded maximum clique size in the
factorization phase, and also result in smaller condition
numbers than standard preconditioning techniques. When
applying the proposed method to the “bal” datasets [1],
GSP displays promising performance.