Introduction
In computer vision and robotics, outlier-robust estimation is critical for tasks like image stitching and autonomous navigation. While Iteratively Reweighted Least Squares (IRLS) has been a staple for decades, its most efficient variants—particularly those employing Graduated Non-Convexity (GNC)—have often been viewed as fast heuristics rather than mathematically grounded algorithms. This work provides the first rigorous convergence proofs for IRLS combined with GNC, establishing it as a provably correct and highly efficient framework.
Problem Statement
Robust estimation typically involves minimizing non-convex and non-smooth loss functions, such as $\ell_p$-loss or Truncated Least Squares (TLS). These functions present significant optimization challenges, often leading standard tools to stall in local minima. GNC addresses this by solving a sequence of smoothed problems that gradually approach the original objective. However, a general theory explaining the convergence properties and speed of GNC-IRLS has been missing.
Methodology: GNC-IRLS and Majorization
The proposed GNC-IRLS$_p$ algorithm integrates two core concepts:
- Two-Level Majorization: Instead of direct optimization of the non-smooth loss, the algorithm employs a "majorizer"—a surrogate function that upper-bounds the target loss and is easier to minimize. As shown in Figure 1, as the smoothing parameter $\epsilon$ approaches zero, the smooth majorizer $\rho_\epsilon(r)$ converges to the original robust loss $\rho(r)$.
- Superlinear GNC Schedule: Unlike traditional linear schedules that update smoothing parameters by a constant factor, this work introduces a superlinear schedule. This aggressive update mechanism significantly accelerates convergence.
Key Insights
- Theoretical Foundation for Truncation: Truncating small residuals in IRLS is proven to be a valid majorization strategy, ensuring convergence to stationary points rather than being a mere implementation "hack."
- Convergence Phases: The authors identify a "burn-in" phase where error reduction is minimal while the smoothing parameter is large, followed by a rapid descent once a critical threshold is reached.
- Quadratic Convergence: For robust regression, GNC-IRLS$_p$ can achieve quadratic convergence when initialized with standard least-squares estimates, effectively doubling the precision of the estimate with each iteration.
Experimental Results
The theory was validated through robust linear regression and point cloud registration tasks. In point cloud registration, the method maintained high accuracy even with 70-80% outliers.
As illustrated in Figure 2, the error follows a predictable decay path. Empirically, the proposed GNC-IRLS variant converged in just 5–10 iterations, a 3x speedup over the previous state-of-the-art GNC-TLS, which typically requires 30 or more iterations.
Conclusion
This research transforms GNC-IRLS from a heuristic into a well-founded optimization framework with provable convergence. By leveraging superlinear schedules and majorization theory, the authors achieve state-of-the-art speed and robustness in fundamental estimation tasks. Future work includes extending these proofs to a wider variety of robust losses and investigating automated threshold scheduling.
Implementation available at: GitHub
Summary updated