# Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression

arXiv: https://arxiv.org/abs/2208.11846 · HTML: https://mlsanity.com/paper/2208.11846/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2022.

## Built on by (most cited first, 10 of 10)

- [Scalable 3D Registration via Truncated Entry-wise Absolute Residuals](https://mlsanity.com/paper/2404.00915/) (2024)
- [Efficient and Robust Point Cloud Registration via Heuristics-guided Parameter Search](https://mlsanity.com/paper/2404.06155/) (2024)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming](https://mlsanity.com/paper/2603.25442/) (2026)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [Recovery Guarantees for Continual Learning of Dependent Tasks: Memory, Data-Dependent Regularization, and Data-Dependent Weights](https://mlsanity.com/paper/2604.17578/) (2026)
- [A Smoothing Newton Method for Rank-one Matrix Recovery](https://mlsanity.com/paper/2507.23017/) (2025)
- [Outlier-robust Autocovariance Least Square Estimation via Iteratively Reweighted Least Square](https://mlsanity.com/paper/2603.08158/) (2026)
- [TailedTS: Benchmark Dataset for Heavy-Tailed Time Series Prediction and Periodicity Quantification](https://mlsanity.com/paper/2605.16361/) (2026)

## Abstract (arXiv)

We advance both the theory and practice of robust ℓp-quasinorm regression for p ∈ (0,1] by using novel variants of iteratively reweighted least-squares (IRLS) to solve the underlying non-smooth problem. In the convex case, p=1, we prove that this IRLS variant converges globally at a linear rate under a mild, deterministic condition on the feature matrix called the textitstable range space property. In the non-convex case, p∈(0,1), we prove that under a similar condition, IRLS converges locally to the global minimizer at a superlinear rate of order 2-p; the rate becomes quadratic as p→ 0. We showcase the proposed methods in three applications: real phase retrieval, regression without correspondences, and robust face restoration. The results show that (1) IRLS can handle a larger number of outliers than other methods, (2) it is faster than competing methods at the same level of accuracy, (3) it restores a sparsely corrupted face image with satisfactory visual quality. https://github.com/liangzu/IRLS-NeurIPS2022