Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation
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 faster, robust alternating minimization for weighted low rank approximation by replacing exact regressions with a sketch-preconditioned high-accuracy weighted multiple-response regression solver, cutting runtime from ||W||_0 k^2 to ||W||_0 k.
Problem
Weighted low rank approximation: find rank-k X, Y minimizing ||W∘(M−XY^T)||_F, where prior alternating minimization needs exact regressions each iteration (slow and non-robust to approximate solves).
Approach
A high-accuracy weighted multiple-response regression solver (SRHT sketch as preconditioner plus gradient-style refinement, converting forward to backward error) combined with a robustness analysis showing alternating minimization still converges when each update is only approximately computed in spectral norm.
Key results
- Runtime improved from O((||W||_0 k^2 + n k^3) log(1/eps)) to Õ((||W||_0 k + n k^3) log(1/eps)) for weighted low rank approximation.
- Recovery guarantee ||M~ - M*|| ≤ O(alpha^{-1} k tau)||W∘N|| + eps in O(log(1/eps)) iterations with random initialization.
- For noisy matrix completion with Boolean W, runtime becomes Õ(n k^{3+o(1)} log(1/eps)) versus Õ(n k^{4+o(1)} log(1/eps)) for prior work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace exact alternating updates with fast approximate updates using a high-accuracy regression solver | Weighted low rank approximation · Weighted low rank approximation | runtime: O((\|W\|_0 k^2+nk^3)\log(1/\epsilon)) -> \widetilde O((\|W\|_0\cdot k+nk^3)\log(1/\epsilon)) | Helped |
| Use the proposed algorithm instead of prior exact alternating minimization | Weighted low rank approximation with dense weights and k=O(\sqrt n) · Weighted low rank approximation with dense weights and k=O(\sqrt n) | runtime: O(n^3\log(1/\epsilon)) -> \widetilde O(n^{2.5}\log(1/\epsilon)) | Helped |
Limitations
- Requires incoherence, spectral-gap and boundedness assumptions on the ground truth and weights.
- Initialization with SVD would cost O(n^3) and dominate runtime; analysis uses random initialization.
- Theoretical paper with no empirical experiments.
Experimental setup
Metrics: spectral norm error bound running time
Baselines: exact alternating minimization for weighted low rank approximation fast alternating minimization for noiseless matrix completion
Builds on: alternating minimization for weighted low rank approximation (Razenshteyn et al. SRHT subspace embedding OSNAP sketching
Closest papers by meaning
- Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.94)
- Recovery guarantee of weighted low-rank approximation via alternating minimization (ICML 2016 · similarity 0.94)
- Regularized Weighted Low Rank Approximation (NeurIPS 2019 · similarity 0.91)
- Additive Error Guarantees for Weighted Low Rank Approximation (ICML 2021 · similarity 0.90)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.87)
- Reweighted Solutions for Weighted Low Rank Approximation (ICML 2024 · similarity 0.86)
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.