Matrix Completion in Almost-Verification Time

We give a new framework for solving the fundamental problem of low-rank matrix completion, i. e. , approximating a rank- r matrix $\mathbf{M} \in \mathbb{R}^{m \times n}$ (where $m \geq 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 $\approx m r$ samples and using $\approx m r^{2}$ 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 $m r^{2+o(1)}$ observations in $m r^{3+o(1)}$ time (omitting logarithmic factors in problem parameters), improving upon the prior state-of-the-art [JN15] which used $\approx m r^{5}$ samples and $\approx m r^{7}$ 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 $m r^{1+o(1)}$, and our runtime improves to $m r^{2+o(1)}$. Our runtimes have the appealing property of matching the best known runtime to verify that a rankr decomposition $\mathrm{UV}^{\top}$ agrees with the sampled observations. We also provide robust variants of our algorithms that, given random observations from $\mathrm{M}+\mathrm{N}$ with $\|\mathrm{N}\|_{\mathrm{F}} \leq \Delta$, complete M to Frobenius norm distance $\approx r^{1. 5} \Delta$ in the same runtimes as the noiseless setting. Prior noisy matrix completion algorithms [CP10] only guaranteed a distance of $\approx \sqrt{n} \Delta$.

Authors

• Jonathan A. Kelner
• Jerry Li 0001
• Allen Liu
• Aaron Sidford
• Kevin Tian

Keywords

• Computer science
• Runtime
• Approximation algorithms
• Complexity theory
• Noise measurement
• Matrix decomposition
• Optimization
• Matrix Completion
• Regression Problem
• Frobenius Norm
• Complete Algorithm
• Factorization
• Singular Value
• Normal Operation
• Singular Value Decomposition
• Empirical Estimates
• Additional Assumptions
• Line Of Work
• Submatrix
• Observation Error
• Polynomial-time Algorithm
• Nonzero Entries
• Representative Subset
• R-factor
• Semidefinite Programming
• Sparse Vector
• Distillation Column
• Structural Assumptions
• Noiseless Case
• Polylogarithmic
• Hard Examples
• Proof Of Proposition
• Distancing Measures
• Collaborative Filtering
• Column Vector
• Nuclear Norm
• Regression Residuals
• stochastic optimization