Robust Estimation via Iterative Outlier Downweighting

62 concepts55 papers1 proposal

Standard optimization techniques often rely on the method of least squares ($L_2$-norm minimization) because it is computationally convenient and yields clean, closed-form linear solutions. However, least squares possesses a notorious vulnerability: it is exceptionally sensitive to outliers. Because the penalty for an error grows quadratically, a single heavily corrupted data point can exert immense leverage, pulling the entire estimation away from the true underlying structure.

To combat this, robust statistics replaces the quadratic penalty with error metrics that grow more slowly, such as the absolute error ($L_1$-norm) or specialized M-estimators. While these robust loss functions prevent outliers from dominating the solution, they introduce a new challenge: they are often non-smooth or non-linear, stripping away the computational simplicity of standard linear algebra solvers.

Iteratively Reweighted Least Squares (IRLS) elegantly bridges this gap. It transforms a difficult, non-smooth robust optimization problem into a sequence of standard, easily solvable weighted least squares problems. By dynamically updating data weights based on current residuals, IRLS achieves robust estimation while preserving the efficiency of classical linear solvers.

The Core Intuition: Turning Robustness into Weighted Smoothness

To understand why IRLS works, consider the task of minimizing the $L_1$-norm of a residual vector, where we want to find parameters that minimize $\sum |r_i|$. The absolute value function is non-smooth at zero, meaning we cannot simply take its derivative and solve a linear system.

However, we can apply a simple algebraic identity to rewrite the objective:

$$|r_i| = \frac{r_i^2}{|r_i|}$$

If we treat the denominator as a fixed inverse weight, $w_i = 1/|r_i|$, the objective looks exactly like a weighted least squares problem: $\sum w_i r_i^2$.

This reveals a circular dependency: to find the optimal model parameters, we need the weights $w_i$; but to calculate the weights, we need the residuals $r_i$, which depend on the model parameters. IRLS resolves this loop by alternating between two straightforward steps:

  1. Freeze the weights, update the model: Solve a standard weighted least squares problem using the current weights. Because this subproblem is quadratic, it can be solved efficiently using standard linear algebra.
  2. Freeze the model, update the weights: Calculate the new residuals from the updated model, and compute fresh weights for the next iteration. Data points with large residuals receive smaller weights, while points close to the model receive larger weights.

As noted by Gilad Lerman et al. in Robust Computation of Linear Models by Convex Relaxation, minimizing the sum of unsquared residuals via iterative reweighting dynamically suppresses the influence of data points that lie far from the true subspace, providing a rigorous defense against adversarial noise.

┌────────────────────────────────────────────────────────┐
│             Initial Guess (e.g., Standard L2)          │
└───────────────────────────┬────────────────────────────┘
                            │
                            ▼
              ┌───────────────────────────┐
        ┌────►│     Compute Residuals     │
        │     └─────────────┬─────────────┘
        │                   │
        │                   ▼
  Update Weights      Update Weights
  w_i = f(r_i)        Assign lower weights to large residuals
        │                   │
        │                   ▼
        │     ┌───────────────────────────┐
        └─────┤ Solve Weighted L2 Problem │
              └───────────────────────────┘

Why It Works: Dynamic Soft Outlier Rejection

Rather than forcing a hard, binary decision about whether a data point is an clean inlier or a corrupted outlier, IRLS performs soft outlier rejection.

In Blind Image Deblurring with Outlier Handling, Jiangxin Dong et al. demonstrate that incorporating a non-quadratic robust function into an iterative reweighting scheme implicitly generates continuous weight maps. These maps automatically identify pixels that violate the standard linear model (such as saturated pixels or non-Gaussian noise), allowing the optimization to focus entirely on reliable image regions.

This continuous adjustment allows the algorithm to recover from poor initializations. Even if an initial estimate is skewed by outliers, the data points closest to the true signal will begin to pull the model toward the correct solution. As the model aligns with the true structure, the actual outliers develop progressively larger residuals, causing their weights to drop in subsequent iterations.

This empirical resilience is backed by strong theoretical guarantees. Christian Kümmerle et al. in Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression proved that specific IRLS variants converge globally at a linear rate for $p=1$ optimization, and locally at a superlinear rate for non-convex $p < 1$ settings. This means iterative reweighting is not just a heuristic; it is a mathematically rigorous path to fast, optimal robust solutions.

Generalizing Beyond Linear Spaces

The true elegance of the iterative reweighting framework is its adaptability. It generalizes far beyond simple line-fitting to handle complex geometric manifolds, low-rank matrix approximations, and multi-model estimation.

Geometric Manifolds and Trajectories

In computer vision and robotics, data often lives on non-Euclidean geometric structures where standard subtraction and addition do not apply. Khurrum Aftab et al. in Generalized Weiszfeld Algorithms for Lq Optimization extended iterative reweighting to Riemannian manifolds, providing a robust framework for rotation averaging in 3D reconstruction.

Similarly, Benjamin Busam et al. integrated IRLS into local regression on the Riemannian manifold of unit dual quaternions in Camera Pose Filtering with Local Regression Geodesics on the Riemannian Manifold of Dual Quaternions. By automatically down-weighting sensor noise and tracking glitches, their method stabilizes camera trajectories smoothly without requiring manual outlier removal.

Robust Subspace Recovery and PCA

Principal Component Analysis (PCA) is highly sensitive to corrupted data. By utilizing distance-based iterative reweighting, researchers can recover low-dimensional structures from heavily corrupted datasets. In A Novel M-Estimator for Robust PCA, Gilad Lerman et al. showed that dynamically assigning lower weights to points deviating from a candidate subspace yields linear convergence to an optimal, outlier-resistant subspace. To handle even more abstract geometric primitives, Nathan Mankovich et al. introduced The Flag Median and FlagIRLS, applying an IRLS strategy to compute robust averages of subspaces directly on a Grassmann manifold.

Disentangling Mixed Models

Iterative down-weighting can also be used to isolate individual structures within a mixture of models. In Imbalanced Mixed Linear Regression, Pini Zilber leverages an IRLS variant to solve mixed linear regression problems. By treating data points belonging to undiscovered components as "outliers" to be down-weighted, the algorithm can cleanly isolate and solve for one linear trend at a time, avoiding the local minima that often plague traditional mixture-model solvers.

Duality and Graduated Non-Convexity

Why does this alternating minimization between weights and parameters work so reliably? The mechanism can be understood deeply through optimization duality and auxiliary variables.

As explored by Heng Yang et al. in Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection, introducing weights into a least squares objective is mathematically dual to introducing auxiliary variables that represent the probability of a data point being an inlier.

By pairing this duality with Graduated Non-Convexity (GNC), solvers can systematically smooth a highly non-convex robust cost function. The algorithm begins by solving a convex approximation of the problem where all data points are partially embraced. It then iteratively "hardens" the objective function back to its true, non-convex, outlier-rejecting form. At each step, it solves a weighted least squares problem, updating the weights in a closed-form step. This global optimization strategy allows systems to bypass local minima entirely, successfully rejecting up to 90% outlier contamination without requiring a lucky initial guess.

Key Foundational Work

Robust Parameter Estimation and Model Selection for Neural Network Regression (1993) — contributed 1 concept elements to this direction.
Fluid Motion Recovery by Coupling Dense and Parametric Vector Fields (1999) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_iteratively_reweighted_least_squares_3518ccad,
  title = {iteratively reweighted least squares},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iteratively-reweighted-least-squares/rdr_3518ccadc9924214bee784d2e9239776},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_iteratively_reweighted_least_squares_3518ccad_v1,
  title = {iteratively reweighted least squares},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iteratively-reweighted-least-squares/rdr_3518ccadc9924214bee784d2e9239776/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake