Sparse Variable Projection in Robotic Perception: Exploiting Separable Structure for Efficient Nonlinear Optimization
Alan Papalia, Nikolas Sanderson, Haoyu Han, HENG YANG, Hanumant Singh, Michael Everett
AI summary
Problem
Robotic perception relies on solving large nonlinear least-squares problems, but standard variable projection methods struggle with gauge symmetries that cause rank deficiencies and dense matrices, limiting efficiency gains from separable structure.
Approach
The authors introduce a one-time preprocessing step that analytically eliminates linear variables using a matrix-free Schur complement operator. This operator computes costs and gradients via sparse operations and Cholesky factorizations, preserving sparsity and handling gauge symmetries efficiently.
Key results
- Novel sparsity-preserving variable projection scheme for perception problems
- Precise graph-theoretic conditions characterizing method applicability
- Runtime reductions of 2×–35× across SLAM, SfM, and SNL benchmarks
- Open-source C++ implementation and experimental datasets released
Why it matters
Enables faster, more scalable optimization for large-scale robotic perception tasks like SLAM and structure-from-motion, directly improving deployment reliability and efficiency.
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 separability – where some variables (e.g., visual landmarks) appear linearly in the residuals and, for any estimate of the remaining variables (e.g., poses), have a closed-form solution. Variable projection (VarPro) methods are a family of techniques that exploit this structure by analytically eliminating the linear variables and presenting a reduced problem in the remaining variables that has favorable properties. However, VarPro has seen limited use in robotic perception; a major challenge arises from gauge symmetries (e.g., cost invariance to global shifts and rotations), which are common in perception and 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 matrix- free Schur complement operator. This operator allows efficient evaluation of 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 2×–35× faster runtimes than state-of-the-art methods while maintaining accuracy. We release an open-source C++ implementation and all datasets from our experiments.