Fast and Provable Nonconvex Robust Matrix Completion
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918500472193024 |
|---|---|
| author | Fu, Yichen Wang, Tianming Wei, Ke |
| author_facet | Fu, Yichen Wang, Tianming Wei, Ke |
| contents | We study the robust matrix completion (RMC) problem subject to both sparse outliers and stochastic noise. A non-convex method termed Accelerated Robust Matrix Completion (ARMC) is proposed, which accelerates a prior non-convex approach by incorporating an explicit subspace projection step into the low-rank update, leading to significantly improved computational efficiency. Through a delicate analysis based on the leave-one-out technique, the entrywise linear convergence guarantee of ARMC has been established. Notably, the derived bounds for sample complexity and outlier sparsity improve upon existing guarantees of the convex relaxation approach that also accounts for both sparse outliers and stochastic noise. Moreover, numerical experiments on synthetic and real data show that ARMC is superior to existing non-convex RMC methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_07355 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fast and Provable Nonconvex Robust Matrix Completion Fu, Yichen Wang, Tianming Wei, Ke Information Theory 15A83, 49N30, 68Q25, 90C26 We study the robust matrix completion (RMC) problem subject to both sparse outliers and stochastic noise. A non-convex method termed Accelerated Robust Matrix Completion (ARMC) is proposed, which accelerates a prior non-convex approach by incorporating an explicit subspace projection step into the low-rank update, leading to significantly improved computational efficiency. Through a delicate analysis based on the leave-one-out technique, the entrywise linear convergence guarantee of ARMC has been established. Notably, the derived bounds for sample complexity and outlier sparsity improve upon existing guarantees of the convex relaxation approach that also accounts for both sparse outliers and stochastic noise. Moreover, numerical experiments on synthetic and real data show that ARMC is superior to existing non-convex RMC methods. |
| title | Fast and Provable Nonconvex Robust Matrix Completion |
| topic | Information Theory 15A83, 49N30, 68Q25, 90C26 |
| url | https://arxiv.org/abs/2601.07355 |