Research map / Learning theory and algorithms / Matrix and tensor methods
Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting
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 the first high-accuracy nearly-linear-time algorithm for semi-random low-rank matrix completion (with noise), using short-flat decomposition iterations whose per-step adaptive reweighting is solved via flow/matching-based Frank-Wolfe.
Problem
Matrix completion from entries revealed with probability at least p in a semi-random (adversarially boosted) model, where prior nearly-linear-time methods lack high-accuracy recovery and noise tolerance.
Approach
Replace the single global reweighting of prior work with an iterative method whose each step only needs constant-factor relative progress, found by solving an adaptive reweighting subproblem (Frank-Wolfe over a bipartite matching polytope with smooth-max flatness objective) using fast flow-based graph algorithms; heavy rows/columns are dropped and later recovered.
Key results
- Achieves exact recovery in nearly-linear time O(mQ) with Q = poly(r, µ, log(d/ε)) in the noiseless semi-random setting, versus polynomial dependence on 1/ε and condition number in prior work.
- Extends to noisy observations with error ||M-M*||_inf <= Q(Δ + ε||M*||_inf), a first for semi-random matrix completion.
- Sample complexity p = poly(r,µ,log d)/d with rank factor r^6 in Ban et al. versus poly(r) here.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use flow-based adaptive reweighting and local progress steps instead of a single global reweighting | Semi-random matrix completion · Semi-random matrix completion | accuracy dependence: poly(1/ϵ) -> polylogarithmic dependence on 1/ϵ | Helped |
| Use flow-based adaptive reweighting | Semi-random matrix completion · Semi-random matrix completion | condition number dependence | Helped |
| Extend the method to noisy observations with an elementwise noise guarantee | Semi-random matrix completion · Noisy semi-random matrix completion | elementwise error bound | Helped |
Limitations
- Sample complexity and runtime polynomial in r (around r^6 in prior work; poly(r) here) limit practicality
- Analysis requires non-adaptive semi-random adversary; adaptive adversaries are an open problem
- Error guarantee uses entrywise noise norm rather than Frobenius norm
Experimental setup
Metrics: entrywise l-infinity error runtime sample complexity
Baselines: Ban et al. 2019 semi-random matrix completion SDP-based nuclear norm minimization
Builds on: short-flat decomposition (Jain/Kelner et al. sparse regression framework) Kelner et al. 2023 standard matrix completion Ban et al. 2019 semi-random matrix completion
Closest papers by meaning
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.90)
- Matrix Completion with Model-free Weighting (ICML 2021 · similarity 0.89)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.88)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.87)
- Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.87)
- A Pairwise Pseudo-likelihood Approach for Matrix Completion with Informative Missingness (NeurIPS 2024 · similarity 0.87)
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.