Research map / Learning theory and algorithms / Matrix and tensor methods
Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
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.
Gives a robust analysis of alternating minimization for low-rank matrix completion that tolerates approximate (sketch-preconditioned) regression solves, achieving Õ(|Ω|k) runtime with the sample complexity of prior exact AltMin analyses.
Problem
Low-rank matrix completion via alternating minimization is usually run with approximate updates in practice, but existing theory assumes exact updates; theory also yields slow runtimes of O(|Ω|k^2) per iteration.
Approach
Develops an inductive analytical framework for alternating minimization that tolerates errors from approximate regression solves, using a perturbation theory for row-incoherence (via leverage scores) and sketching-based preconditioned solvers that exploit the sparsity of observed entries to reach Õ(|Ω|k) time.
Key results
- Algorithm samples |Ω| = O(κ^4 μ^2 n k^4.5 log n log(k||M||_F/ε)) entries and runs in Õ(|Ω|k) time, improving the per-iteration cost of prior alternating minimization from O(|Ω|k^2).
- Per-iteration sketch-preconditioned regression solver runs in Õ(|Ω|k + nk^3) time, with error dependence log(1/ε).
- Claims the first alternating-minimization algorithm with nearly linear verification-time runtime while preserving the sample complexity of prior exact analyses.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sketching-based regression solvers with robust alternating minimization instead of exact alternating updates | Alternating minimization for low-rank matrix completion · Low-rank matrix completion | runtime: O(|\Omega| k^2) -> \widetilde O(|\Omega| k) | Helped |
| Use approximate regression updates while preserving the alternating-minimization sample complexity | Robust alternating minimization for low-rank matrix completion · Low-rank matrix completion | sample complexity | No clear effect |
Limitations
- Sample complexity is not improved over prior exact-update analyses (k^4.5 and κ^4 dependence), so it lags the best known rates.
- No empirical experiments are reported to validate practical performance.
- Assumes noiseless ground truth with incoherent, rank-k matrices and independent entry sampling.
Experimental setup
Baselines: Jain et al. 2013 alternating minimization Gamarnik et al. nearly linear time matrix completion Gradient descent matrix completion
Builds on: Jain, Netrapalli, and Sanghavi alternating minimization sketch-and-precondition regression Gu-Song-type sample complexity improvements for alternating minimization
Closest papers by meaning
- Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation (ICLR 2025 · similarity 0.94)
- Recovery guarantee of weighted low-rank approximation via alternating minimization (ICML 2016 · similarity 0.91)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.90)
- Nearly Optimal Robust Matrix Completion (ICML 2017 · similarity 0.90)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.89)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · 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.