Research map / Learning theory and algorithms / Matrix and tensor methods
Nonconvex low-rank and sparse optimization
Gives global convergence and landscape results for matrix factorization and primal-dual coordinate methods.
112 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Matrix and tensor methods, keyword cluster “sparse · recovery · pca”
State History Tried Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
17 papers in 2023–24 and 19 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic held steady, from 9.8% to 10.2%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Provable Non-convex Phase Retrieval with Outliers: Median TruncatedWirtinger Flow (ICML 2016 · 72 citations)
- 2017 · No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (ICML 2017 · 215 citations)
- 2018 · Asynchronous Doubly Stochastic Sparse Kernel Learning (AAAI 2018 · 28 citations)
- 2019 · Screening rules for Lasso with non-convex Sparse Regularizers (ICML 2019 · 10 citations)
- 2020 · A Generalized Framework for Edge-Preserving and Structure-Preserving Image Smoothing (AAAI 2020 · 127 citations)
- 2021 · Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate (NeurIPS 2021 · 12 citations)
- 2022 · Gradient Step Denoiser for convergent Plug-and-Play (ICLR 2022 · 18 citations)
- 2023 · On the Convergence of IRLS and Its Variants in Outlier-Robust Estimation (CVPR 2023 · 22 citations)
- 2024 · Privacy Amplification by Iteration for ADMM with (Strongly) Convex Objective Functions (AAAI 2024 · 1 citation)
- 2025 · Non-Convex Tensor Recovery from Local Measurements (AAAI 2025 · 2 citations)
- 2026 · Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA (ICML 2026 · 0 citations)
Earliest papers here
- Provable Non-convex Phase Retrieval with Outliers: Median TruncatedWirtinger Flow (ICML 2016 · 72 citations)
- Stochastic Optimization for Kernel PCA (AAAI 2016 · 22 citations)
- Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity (ICML 2016 · 21 citations)
What has been tried
95 papers here report 678 measured changes (a component added, removed or swapped, compared with a baseline): helped 73%, no clear effect 10%, hurt 12%, mixed 6%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| use random initialization instead of spectral initialization | Synthetic tensor, random initialization · convergence rate | Mixed | Non-Convex Tensor Recovery from Local Measurements (AAAI 2025 · 2 citations) | |
| Use amplitude-based loss to select Newton-update support instead of intensity-based loss | Sparse phase retrieval convergence · convergence speed | Helped | A Fast and Provable Algorithm for Sparse Phase Retrieval (ICLR 2024 · 1 citation) | |
| Increase power iterations from α=0 to α=1 | w8a · condition number κ(V) | 4 -> 120 | Hurt | In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting (AAAI 2025 · 0 citations) |
| Lower the gradient clipping threshold | Synthetic regression with varied clipping threshold · Error | Hurt | Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation (ICML 2024 · 0 citations) | |
| Use asymmetric parameterization instead of symmetric parameterization | Symmetric LRMS · relative error | Helped | Globally Q-linear Gauss-Newton Method for Overparameterized Non-convex Matrix Sensing (NeurIPS 2024 · 0 citations) |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 36 papers; from OpenAlex and the papers' affiliations).
- The Chinese University of Hong Kong · 3 papers
- Inria · 2 papers
- Pennsylvania State University · 2 papers
- Johns Hopkins University · 2 papers
- Apple · 2 papers
- Academy of Mathematics and Systems Science · 2 papers
- University of Washington · 2 papers
- Xi’an Jiaotong University · 2 papers
- Xidian University · 2 papers
Use it
Download BibTeX of 40 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Sparse regression with guarantees (94 papers)
- High-dimensional estimation theory (89 papers)
- Signal recovery and phase retrieval (66 papers)
- Sparse and robust PCA (66 papers)
Elsewhere in the topic
- Low-rank approximation theory (142 papers)
- Matrix completion and factorization (118 papers)
- Randomized sketching for matrices (96 papers)
- Structured low-rank learning (87 papers)
- Geometry of low-rank and SPD structure (71 papers)
- Tensor network decompositions (45 papers)
- Low-rank tensor completion (45 papers)
- Randomized tensor decomposition algorithms (43 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).