mlsanityData to 7 Oct 2026

Fast matrix completion without the condition number

arXiv 1407.4070 ↗First posted 15 Jul 2014cs.LG cs.DS stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

We give the first algorithm for Matrix Completion whose running time and sample complexity is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix in the running time. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jul 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 3; 2023: 4; 2024: 3; 2025: 2; 2026: 1.

17 papers.

Sort:

  1. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  2. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  3. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  4. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  5. 2021Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Ratescited by 10
  6. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  7. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  8. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
  9. 2023Matrix Completion in Almost-Verification Timecited by 4
  10. 2021Riemannian Perspective on Matrix Factorizationcited by 3
  11. 2021Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descentcited by 3
  12. 2024Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffscited by 2
5 more
  1. 2026Low-Rank Adaptation Redux for Large Modelscited by 2
  2. 2023Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensingcited by 1
  3. 2024Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functionscited by 1
  4. 2024Efficient Federated Low Rank Matrix Completioncited by 0
  5. 2025Fast exact recovery of noisy matrix from few entries: the infinity norm approachcited by 0