# Matrix Completion in Almost-Verification Time

arXiv: https://arxiv.org/abs/2308.03661 · HTML: https://mlsanity.com/paper/2308.03661/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 48 references that are in the map.
- First posted on arXiv 7 Aug 2023.

## Builds on (most cited first, 18 of 18)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [Solving SDP Faster: A Robust IPM Framework and Efficient Implementation](https://mlsanity.com/paper/2101.08208/) (2021)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [When Are Nonconvex Problems Not Scary?](https://mlsanity.com/paper/1510.06096/) (2015)
- [Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems](https://mlsanity.com/paper/1411.1134/) (2014)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [Fast matrix completion without the condition number](https://mlsanity.com/paper/1407.4070/) (2014)
- [Fast Exact Matrix Completion with Finite Samples](https://mlsanity.com/paper/1411.1087/) (2014)
- [Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent](https://mlsanity.com/paper/1605.08370/) (2016)
- [Nearly-optimal Robust Matrix Completion](https://mlsanity.com/paper/1606.07315/) (2016)
- [Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow](https://mlsanity.com/paper/1803.01233/) (2018)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Partial Matrix Completion](https://mlsanity.com/paper/2208.12063/) (2022)

## Built on by (most cited first, 4 of 4)

- [Weighted Low-rank Approximation via Stochastic Gradient Descent on Manifolds](https://mlsanity.com/paper/2502.14174/) (2025)
- [Adaptive Stochastic Gradient Descents on Manifolds with an Application on Weighted Low-Rank Approximation](https://mlsanity.com/paper/2503.11833/) (2025)
- [Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming](https://mlsanity.com/paper/2509.16915/) (2025)
- [Efficient Tensor Completion Algorithms for Highly Oscillatory Operators](https://mlsanity.com/paper/2510.17734/) (2025)

## Abstract (arXiv)

We give a new framework for solving the fundamental problem of low-rank matrix completion, i.e., approximating a rank-r matrix M ∈ ℝm × n (where m ≥ n) from random observations. First, we provide an algorithm which completes M on 99% of rows and columns under no further assumptions on M from ≈ mr samples and using ≈ mr2 time. Then, assuming the row and column spans of M satisfy additional regularity properties, we show how to boost this partial completion guarantee to a full matrix completion algorithm by aggregating solutions to regression problems involving the observations. In the well-studied setting where M has incoherent row and column spans, our algorithms complete M to high precision from mr2+o(1) observations in mr3 + o(1) time (omitting logarithmic factors in problem parameters), improving upon the prior state-of-the-art [JN15] which used ≈ mr5 samples and ≈ mr7 time. Under an assumption on the row and column spans of M we introduce (which is satisfied by random subspaces with high probability), our sample complexity improves to an almost information-theoretically optimal mr1 + o(1), and our runtime improves to mr2 + o(1). Our runtimes have the appealing property of matching the best known runtime to verify that a rank-r decomposition UV^top agrees with the sampled observations. We also provide robust variants of our algorithms that, given random observations from M + N with |N|F ≤ Delta, complete M to Frobenius norm distance ≈ r1.5Delta in the same runtimes as the noiseless setting. Prior noisy matrix completion algorithms [CP10] only guaranteed a distance of ≈ √nDelta.