# Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 108 references that are in the map.
- First posted on arXiv 8 Jun 2023.

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Image Reconstruction: From Sparsity to Data-adaptive Methods and Machine Learning](https://mlsanity.com/paper/1904.02816/) (2019)
- [Sparse Modeling for Image and Vision Processing](https://mlsanity.com/paper/1411.3230/) (2014)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [Low-rank lottery tickets: finding efficient low-rank neural networks via matrix differential equations](https://mlsanity.com/paper/2205.13571/) (2022)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [Coordinating Filters for Faster Deep Neural Networks](https://mlsanity.com/paper/1703.09746/) (2017)
- [Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow](https://mlsanity.com/paper/1506.03382/) (2015)
- [HARA: A Hierarchical Approach for Robust Rotation Averaging](https://mlsanity.com/paper/2111.08831/) (2021)
- [Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applications](https://mlsanity.com/paper/1708.07850/) (2017)
- [Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems](https://mlsanity.com/paper/2006.14211/) (2020)
- [Robust Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.8126/) (2013)
- [Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization](https://mlsanity.com/paper/1702.06175/) (2017)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression](https://mlsanity.com/paper/1907.07167/) (2019)
- [Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate](https://mlsanity.com/paper/2012.12250/) (2020)
- [Robust Group Synchronization via Quadratic Programming](https://mlsanity.com/paper/2206.08994/) (2022)
- [Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression](https://mlsanity.com/paper/2208.11846/) (2022)
- [Learning Sparse and Low-Rank Priors for Image Recovery via Iterative Reweighted Least Squares Minimization](https://mlsanity.com/paper/2304.10536/) (2023)
- [Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms](https://mlsanity.com/paper/1311.2745/) (2013)
- [NP-Hardness and Inapproximability of Sparse PCA](https://mlsanity.com/paper/1502.05675/) (2015)
- [Simultaneously sparse and low-rank abundance matrix estimation for hyperspectral image unmixing](https://mlsanity.com/paper/1504.01515/) (2015)
- [Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery](https://mlsanity.com/paper/1703.05038/) (2017)
- [Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently](https://mlsanity.com/paper/1911.11167/) (2019)

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

- [Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training](https://mlsanity.com/paper/2511.04485/) (2025)

## Abstract (arXiv)

We propose a new algorithm for the problem of recovering data that adheres to multiple, heterogeneous low-dimensional structures from linear observations. Focusing on data matrices that are simultaneously row-sparse and low-rank, we propose and analyze an iteratively reweighted least squares (IRLS) algorithm that is able to leverage both structures. In particular, it optimizes a combination of non-convex surrogates for row-sparsity and rank, a balancing of which is built into the algorithm. We prove locally quadratic convergence of the iterates to a simultaneously structured data matrix in a regime of minimal sample complexity (up to constants and a logarithmic factor), which is known to be impossible for a combination of convex surrogates. In experiments, we show that the IRLS method exhibits favorable empirical convergence, identifying simultaneously row-sparse and low-rank matrices from fewer measurements than state-of-the-art methods. Code is available at https://github.com/ckuemmerle/simirls.