mlsanityData to 7 Oct 2026

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

arXiv 2302.11068 ↗First posted 21 Feb 2023cs.LG cs.DS math.OCcited by 31

Not on the map. Why?

Abstract (arXiv)

Given a matrix M∈ ℝm× n, the low rank matrix completion problem asks us to find a rank-k approximation of M as UV^top for U∈ ℝm× k and V∈ ℝn× k by only observing a few entries specified by a set of entries Omegasubseteq [m]× [n]. In particular, we examine an approach that is widely used in practice -- the alternating minimization framework. Jain, Netrapalli, and Sanghavi [JNS13] showed that if M has incoherent rows and columns, then alternating minimization provably recovers the matrix M by observing a nearly linear in n number of entries. While the sample complexity has been subsequently improved [GLZ17], alternating minimization steps are required to be computed exactly. This hinders the development of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed approximately in favor of efficiency. In this paper, we take a major step towards a more efficient and error-robust alternating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate a moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time widetilde O(|Omega| k), which is nearly linear in the time to verify the solution while preserving the sample complexity. This improves upon all prior known alternating minimization approaches which require widetilde O(|Omega| k2) time.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). Builds on 25 of its 61 references that are in the map. First posted on arXiv 21 Feb 2023.

Builds on

25 of 61 references.

References · 25

  1. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
  2. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  3. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  4. 2017Relative Error Tensor Low Rank Approximationcited by 45
  5. 2019Low-Rank Matrix Completion: A Contemporary Surveycited by 43
  6. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  7. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  8. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  9. 2014Optimal CUR Matrix Decompositionscited by 29
  10. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  11. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  12. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
13 more
  1. 2016Recovery guarantee of weighted low-rank approximation via alternating minimizationcited by 20
  2. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  3. 2022Faster Matrix Multiplication via Asymmetric Hashingcited by 19
  4. 2022Semi-Random Sparse Recovery in Nearly-Linear Timecited by 18
  5. 2014Fast matrix completion without the condition numbercited by 17
  6. 2022Dynamic Tensor Product Regressioncited by 17
  7. 2014Fast Exact Matrix Completion with Finite Samplescited by 15
  8. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  9. 2016Nearly-optimal Robust Matrix Completioncited by 13
  10. 2018Towards a Zero-One Law for Column Subset Selectioncited by 12
  11. 2020Average Case Column Subset Selection for Entrywise ℓ1-Norm Losscited by 12
  12. 2014Computational Limits for Matrix Completioncited by 9
  13. 2017Matrix Completion from O(n) Samples in Linear Timecited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 14; 2024: 6; 2025: 9; 2026: 2.

31 papers.

Sort:

By area:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  2. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  3. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  4. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  5. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  6. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  7. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  8. 2023A Unified Scheme of ResNet and Softmaxcited by 12
  9. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  10. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  11. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  12. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
19 more
  1. 2023Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?cited by 8
  2. 2025AbsTopK: Rethinking Sparse Autoencoders For Bidirectional Featurescited by 8
  3. 2023Fast and Efficient Matching Algorithm with Deadline Instancescited by 7
  4. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  5. 2025Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretrainingcited by 6
  6. 2024How to Inverting the Leverage Score Distribution?cited by 5
  7. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  8. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  9. 2024Inverting the Leverage Score Gradient: An Efficient Approximate Newton Methodcited by 3
  10. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  11. 2024In-depth Analysis of Low-rank Matrix Factorisation in a Federated Settingcited by 2
  12. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  13. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  14. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  15. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
  16. 2026CoreFlow: Low-Rank Matrix Generative Modelscited by 1
  17. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  18. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  19. 2025Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programmingcited by 0