Research map / Learning theory and algorithms / Matrix and tensor methods
RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees
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.
Proposes RGNMR, a factorization-based robust matrix completion method combining Gauss-Newton linearization with iterative removal of suspected outlier entries, plus a binary-search estimator for the number of corrupted entries, with linear-convergence guarantees.
Problem
Recovering a low-rank matrix from a subset of observed entries where some observed entries are arbitrarily corrupted outliers; existing methods need many observations, fail under overparameterized rank, and fail for mildly ill-conditioned matrices.
Approach
Alternates a Gauss-Newton (linearized least-squares) factor update on non-suspected entries with re-estimation of outliers as the largest residuals, and uses a binary search on the number of corrupted entries (k) by checking whether the outlier set converges; theory uses a row/column-thresholded outlier removal and a norm-constrained update.
Key results
- RGNMR succeeds with fewer observed entries than AOP, RMC, RPCA-GD, RRMC, HUB and HOAT on 3200x400 rank-5 matrices at 5% corruption, and is unaffected by overparameterized input rank or condition number up to 2 in the reported settings.
- Theorem 1 gives exact recovery with linear convergence under corruption rate alpha < 1/(c r mu kappa), improving the corruption requirement of factorization-based methods by a factor of about sqrt(r).
- Binary-search estimate of the corrupted-entry count gives RGNMR-BS performance similar to RGNMR given the true k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Gauss–Newton linearization with iterative removal of suspected outliers | RGNMR versus existing RMC methods · Uniformly sampled synthetic RMC; few observed entries | relative RMSE | Helped |
| Use Gauss–Newton linearization with iterative removal of suspected outliers | RGNMR versus existing RMC methods · Synthetic RMC with overparameterized input rank | relative RMSE | Helped |
| Use Gauss–Newton linearization with iterative removal of suspected outliers | RGNMR versus existing RMC methods · Synthetic RMC with varying condition number | relative RMSE | Helped |
| Use RGNMR rather than GNMR, which does not remove suspected outliers | GNMR · Synthetic RMC with a small fraction of corrupted entries | relative RMSE | Helped |
| Use RGNMR instead of RMC or AOP | RMC and AOP · Synthetic RMC, oversampling ratio 8 | failure probability | Helped |
| Use RMC or AOP instead of RGNMR | RGNMR · Synthetic RMC, oversampling ratio 12 | failure probability | Hurt |
| Use RGNMR instead of most competing methods | Other RMC methods · Synthetic RMC with power-law sampling | relative RMSE | Helped |
| Use RGNMR instead of other RMC methods | Other RMC methods · Synthetic RMC with diagonal-band sampling | relative RMSE | Helped |
| Use RGNMR instead of most competing methods | Other RMC methods · Synthetic RMC with additive noise and outliers | relative RMSE | Helped |
| Estimate the corruption count by binary search and use the resulting upper bound | RGNMR-BS versus RGNMR given the true corruption count · Synthetic RMC | relative RMSE | No clear effect |
| Use RGNMR instead of competing methods | Other RMC methods · Hall video background extraction, 5% sampled entries | background extraction quality | Helped |
| Use RGNMR instead of methods requiring only a gradient descent step | RGNMR · Runtime | runtime | Hurt |
Surprising findings
- GNMR without outlier handling fails completely even with a small fraction of corrupted entries, so the outlier-removal step is essential.
- Methods like AOP and RMC can tolerate more corruption than RGNMR when the oversampling ratio is high (12).
Limitations
- Theoretical analysis depends on condition number for alpha and sample complexity, and does not cover overparameterization, though empirics show independence.
- Runtime is higher than gradient-based RMC methods because each step solves a large linear system; quadratic scaling in n.
- Theorems require knowledge of mu and alpha, and sigma_1/sigma_r for step size delta; initialization analysis requires more stringent conditions than the main theorem.
Experimental setup
Datasets: synthetic low-rank matrices Hall video background extraction data
Benchmarks: synthetic matrices (3200x400, 1000x1000, 500x500) Hall video background extraction
Metrics: relative RMSE failure probability (rel-RMSE > 1e-3) runtime
Baselines: AOP RMC RPCA-GD RRMC HUB HOAT GNMR
Builds on: GNMR Procrustes-based balanced factorization spectral initialization for matrix completion
Closest papers by meaning
- Nearly Optimal Robust Matrix Completion (ICML 2017 · similarity 0.94)
- A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples (ICML 2021 · similarity 0.92)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.90)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.89)
- Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.89)
- Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery (ICML 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.