Research map / Learning theory and algorithms / Matrix and tensor methods
Low-rank approximation theory
Analyzes error and perturbation bounds for SVD and low-rank estimation of matrices.
142 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Matrix and tensor methods, keyword cluster “matrices · matrix completion · rank matrix”
State History Tried Checklist 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.
26 papers in 2023–24 and 31 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 15.0% to 16.7%.
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 · Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula (NeurIPS 2016 · 125 citations)
- 2017 · Revisiting the Variable Projection Method for Separable Nonlinear Least Squares Problems (CVPR 2017 · 43 citations)
- 2018 · Spectral Filtering for General Linear Dynamical Systems (NeurIPS 2018 · 17 citations)
- 2019 · Variance Reduction for Matrix Games (NeurIPS 2019 · 25 citations)
- 2020 · Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks (NeurIPS 2020 · 8 citations)
- 2021 · Adaptive Rank Estimate in Robust Principal Component Analysis (CVPR 2021 · 7 citations)
- 2022 · The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation? (NeurIPS 2022 · 7 citations)
- 2023 · Efficient Robust Principal Component Analysis via Block Krylov Iteration and CUR Decomposition (CVPR 2023 · 10 citations)
- 2024 · Adaptive Sampling for Efficient Softmax Approximation (NeurIPS 2024 · 4 citations)
- 2025 · Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery (ICML 2025 · 1 citation)
- 2026 · An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale (ICML 2026 · 0 citations)
Earliest papers here
- Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula (NeurIPS 2016 · 125 citations)
- Sub-sampled Newton Methods with Non-uniform Sampling (NeurIPS 2016 · 82 citations)
- Scalable Algorithms for Tractable Schatten Quasi-Norm Minimization (AAAI 2016 · 37 citations)
What has been tried
115 papers here report 793 measured changes (a component added, removed or swapped, compared with a baseline): helped 71%, no clear effect 7%, hurt 16%, mixed 5%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| increase overparameterization d | Robust matrix sensing · convergence rate | Hurt | Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery (ICML 2025 · 1 citation) | |
| use a full unconstrained Θ matrix and Riemannian gradient instead of diagonal Θ and Euclidean gradient | Commonsense reasoning average, rank 4 · accuracy | 71.62 -> 72.45 | Helped | PoLAR: Polar-Decomposed Low-Rank Adapter Representation (NeurIPS 2025 · 1 citation) |
| Use whitening, Xi^{-1/2} A Sigma^{-1/2}, in place of the proposed Bayes-AMP preprocessing, Xi^{-1} A Sigma^{-1} | At least one of Xi, Sigma is not a multiple of the identity · weak recovery threshold | Hurt | Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods (NeurIPS 2024 · 1 citation) | |
| Use the identity matrix instead of the Adam preconditioner | MNIST DnCNN · stability | Hurt | The Expected Loss of Preconditioned Langevin Dynamics Reveals the Hessian Rank (AAAI 2024 · 0 citations) |
What reviewers will expect
Datasets and baselines named in the 22 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Datasets
- CIFAR-10 · 3 of 22 papers
- SNAP Facebook Page-Page network · 2 of 22 papers
- GLUE · 2 of 22 papers
Baselines
- Nystrom method · 2 of 22 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 57 papers; from OpenAlex and the papers' affiliations).
- Carnegie Mellon University · 6 papers
- University of California, Berkeley · 4 papers
- University of Wisconsin - Madison · 3 papers
- Nanyang Technological University · 2 papers
- Hong Kong University of Science and Technology · 2 papers
- Adobe · 2 papers
- Amazon · 2 papers
- Korea Advanced Institute of Science and Technology · 2 papers
- Google · 2 papers
- École Polytechnique · 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
- 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)
Elsewhere in the topic
- Nonconvex low-rank and sparse optimization (112 papers)
- 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)
- 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).