# Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2020.

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

- [Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Finance](https://mlsanity.com/paper/2509.03898/) (2025)
- [Non-Asymptotic Uncertainty Quantification in High-Dimensional Learning](https://mlsanity.com/paper/2407.13666/) (2024)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [A Flag Decomposition for Hierarchical Datasets](https://mlsanity.com/paper/2502.07782/) (2025)
- [Recovery Guarantees for Continual Learning of Dependent Tasks: Memory, Data-Dependent Regularization, and Data-Dependent Weights](https://mlsanity.com/paper/2604.17578/) (2026)
- [Outlier-Robust Diffusion Solvers for Inverse Problems](https://mlsanity.com/paper/2605.09477/) (2026)
- [Argus: Metric Panoramic 3D Reconstruction for Indoor Scenes](https://mlsanity.com/paper/2606.30047/) (2026)
- [Introducing the Huber mechanism for differentially private low-rank matrix completion](https://mlsanity.com/paper/2206.07910/) (2022)
- [Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimization](https://mlsanity.com/paper/2302.05865/) (2023)
- [Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow](https://mlsanity.com/paper/2609.09295/) (2026)

## Abstract (arXiv)

The recovery of sparse data is at the core of many applications in machine learning and signal processing. While such problems can be tackled using ℓ1-regularization as in the LASSO estimator and in the Basis Pursuit approach, specialized algorithms are typically required to solve the corresponding high-dimensional non-smooth optimization for large instances. Iteratively Reweighted Least Squares (IRLS) is a widely used algorithm for this purpose due its excellent numerical performance. However, while existing theory is able to guarantee convergence of this algorithm to the minimizer, it does not provide a global convergence rate. In this paper, we prove that a variant of IRLS converges with a global linear rate to a sparse solution, i.e., with a linear error decrease occurring immediately from any initialization, if the measurements fulfill the usual null space property assumption. We support our theory by numerical experiments showing that our linear rate captures the correct dimension dependence. We anticipate that our theoretical findings will lead to new insights for many other use cases of the IRLS algorithm, such as in low-rank matrix recovery.