  In recent years, many estimation problems in robotics have been shown to be
solvable to global optimality using their semidefinite relaxations. However,
the runtime complexity of off-the-shelf semidefinite programming solvers is up
to cubic in problem size, which inhibits real-time solutions of problems
involving large state dimensions. We show that for a large class of problems,
namely those with chordal sparsity, we can reduce the complexity of these
solvers to linear in problem size. In particular, we show how to replace the
large positive-semidefinite variable by a number of smaller interconnected ones
using the well-known chordal decomposition. This formulation also allows for
the straightforward application of the alternating direction method of
multipliers (ADMM), which can exploit parallelism for increased scalability. We
show in simulation that the algorithms provide a significant speed up for two
example problems: matrix-weighted and range-only localization.
