Research map / Learning theory and algorithms / Matrix and tensor methods
Fast exact recovery of noisy matrix from few entries: the infinity norm approach
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows exact matrix recovery from few noisy entries via truncated SVD with rounding, in the infinity norm, removing prior condition-number and singular-gap assumptions; introduces an infinity-norm Davis-Kahan-Wedin-type perturbation bound proven by contour integration.
Problem
Exact recovery of a low-rank matrix from a random subset of noisy entries, under only the basic assumptions (low rank, incoherence, sufficient sampling), without condition-number or singular-value-gap assumptions.
Approach
A simple algorithm (rescale sampled matrix, truncated SVD with a data-driven cutoff at a large singular-value gap, then round entries to the precision grid) is analyzed with a new infinity-norm perturbation theorem for low-rank approximations, proven via a combinatorial contour-integral argument, so no condition-number or gap assumption is needed.
Key results
- Theorem shows the rescaled truncated SVD with cutoff recovers every entry within absolute error epsilon_0/3 w.p. 1-O(1/N), under sampling density p >= C(1/m+1/n) max{log^4 N, r^3K^2/eps_0^2 (1+mu_0^2/log^2 N)} log^6 N and sigma_1 >= 100 r K sqrt(r_max N/p).
- Removes both the condition-number assumption (Abbe et al.) and the singular-value-gap assumption (Bhardwaj and Vu) required by prior infinity-norm approaches.
- Complexity is essentially one truncated SVD, O(|Omega| r) = O(pmnr) FLOPs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Remove the condition-number and singular-value-gap assumptions used by earlier spectral approaches | Noisy matrix completion with AR2 · Noisy matrix completion | exact recovery under the stated low-rank, incoherence, and sampling assumptions | Helped |
Surprising findings
- The paper argues the gap and condition-number assumptions of prior work pull in opposite directions, suggesting neither is needed.
Limitations
- Requires a sufficiently large leading singular value (large signal assumption) and known upper bounds on rank and noise/entry scales.
- Sampling density grows quadratically with 1/epsilon_0 and carries large polylogarithmic factors (log^6 N or more).
- Theoretical paper with no experiments; the practical performance is not evaluated.
Experimental setup
Datasets: Yale face database (illustrative singular value spectrum only)
Metrics: infinity-norm error bound sample density requirement
Baselines: nuclear norm minimization alternating projections (Jain et al.) OptSpace (Keshavan et al.) Approximate-and-Round (Bhardwaj and Vu) Abbe et al. low-rank approximation
Builds on: Approximate-and-Round (Bhardwaj and Vu) Abbe et al. infinity-norm low-rank approximation Davis-Kahan-Wedin theorem Keshavan-Montanari-Oh
Closest papers by meaning
- Generalization Bounds for Inductive Matrix Completion in Low-Noise Settings (AAAI 2023 · similarity 0.90)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.89)
- Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.88)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.88)
- Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.88)
- A Pairwise Pseudo-likelihood Approach for Matrix Completion with Informative Missingness (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.