Sparse Variable Projection in Robotic Perception: Exploiting Separable Structure for Efficient Nonlinear Optimization

Abstract

Robotic perception often requires solving large nonlinear least-squares (NLS) problems. While sparsity has been well-exploited to scale solvers, a complementary and underexploited structure is emph{separability} -- where some variables (e.g., visual landmarks) enter the residuals linearly and, for any estimate of the remaining variables (e.g., poses), have a closed-form least-squares solution that can be substituted back to reduce the problem size and improve conditioning. Variable projection (VarPro) methods are a family of techniques to exploit this structure, however they have seen limited use in robotic perception; this is in part because gauge symmetries (e.g., cost invariance to global shifts and rotations) which are common in perception problems induce specific computational challenges in standard VarPro approaches. We present a VarPro scheme designed for problems with gauge symmetries that jointly exploits separability and sparsity. Our method can be applied as a one-time preprocessing step to construct a emph{matrix-free Schur complement operator}. This operator allows for efficiently evaluating costs, gradients, and Hessian-vector products of the reduced problem and readily integrates with standard iterative NLS solvers. We provide precise conditions under which our method applies, and describe extensions when these conditions are only partially met. Across synthetic and real benchmarks in SLAM, SNL, and SfM, our approach achieves up to textbf{2times--35times faster runtimes} than state-of-the-art methods while maintaining accuracy. We release an open-source C++ implementation and all datasets.