Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares
Not on the map. Why?
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.
Key facts. Cited by 1 paper 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
34 of 108 references.
References · 34
- 2017Attention Is All You Needcited by 60,361
- 2020Language Models are Few-Shot Learnerscited by 32,419
- 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsitycited by 3,073
- 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,262
- 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
- 2021Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networkscited by 527
- 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
- 2019Image Reconstruction: From Sparsity to Data-adaptive Methods and Machine Learningcited by 60
- 2014Sparse Modeling for Image and Vision Processingcited by 48
- 2016Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statisticscited by 45
- 2022Low-rank lottery tickets: finding efficient low-rank neural networks via matrix differential equationscited by 43
- 2013Square Deal: Lower Bounds and Improved Relaxations for Tensor Recoverycited by 37
22 more
- 2017Coordinating Filters for Faster Deep Neural Networkscited by 24
- 2015Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flowcited by 23
- 2021HARA: A Hierarchical Approach for Robust Rotation Averagingcited by 23
- 2017Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applicationscited by 16
- 2020Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problemscited by 15
- 2013Robust Spectral Compressed Sensing via Structured Matrix Completioncited by 13
- 2017Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimizationcited by 13
- 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samplescited by 13
- 2019Fast, Provably convergent IRLS Algorithm for p-norm Linear Regressioncited by 10
- 2020Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Ratecited by 10
- 2022Robust Group Synchronization via Quadratic Programmingcited by 10
- 2022Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regressioncited by 10
- 2023Learning Sparse and Low-Rank Priors for Image Recovery via Iterative Reweighted Least Squares Minimizationcited by 10
- 2013Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithmscited by 8
- 2015NP-Hardness and Inapproximability of Sparse PCAcited by 8
- 2015Simultaneously sparse and low-rank abundance matrix estimation for hyperspectral image unmixingcited by 8
- 2017Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recoverycited by 7
- 2019Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficientlycited by 6
- 2018Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approachcited by 5
- 2014Tight convex relaxations for sparse matrix factorizationcited by 3
- 2015Near-Optimal Estimation of Simultaneously Sparse and Low-Rank Matrices from Nested Linear Measurementscited by 3
- 2021Riemannian thresholding methods for row-sparse and low-rank matrix recoverycited by 2
Built on by
Citing papers per year: 2025: 1.
1 paper.