# Matrix Completion via Residual Spectral Matching

arXiv: https://arxiv.org/abs/2412.10005 · HTML: https://mlsanity.com/paper/2412.10005/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 73 references that are in the map.
- First posted on arXiv 13 Dec 2024.

## Builds on (most cited first, 22 of 22)

- [Bridging Language and Items for Retrieval and Recommendation: Benchmarking LLMs as Semantic Encoders](https://mlsanity.com/paper/2403.03952/) (2024)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Inference and Uncertainty Quantification for Noisy Matrix Completion](https://mlsanity.com/paper/1906.04159/) (2019)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [Causal Inference with Noisy and Missing Covariates via Matrix Factorization](https://mlsanity.com/paper/1806.00811/) (2018)
- [Matrix Completion via Max-Norm Constrained Optimization](https://mlsanity.com/paper/1303.0341/) (2013)
- [ROP: Matrix recovery via rank-one projections](https://mlsanity.com/paper/1310.5791/) (2013)
- [Statistical Inferences of Linear Forms for Noisy Matrix Completion](https://mlsanity.com/paper/1909.00116/) (2019)
- [Matrix completion with data-dependent missingness probabilities](https://mlsanity.com/paper/2106.02290/) (2021)
- [ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching](https://mlsanity.com/paper/1911.03804/) (2019)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Conformalized matrix completion](https://mlsanity.com/paper/2305.10637/) (2023)
- [Algebraic Variety Models for High-Rank Matrix Completion](https://mlsanity.com/paper/1703.09631/) (2017)
- [Matrix Completion When Missing Is Not at Random and Its Applications in Causal Panel Data Models](https://mlsanity.com/paper/2308.02364/) (2023)
- [A Survey on Matrix Completion: Perspective of Signal Processing](https://mlsanity.com/paper/1901.10885/) (2019)
- [Dynamic matrix recovery from incomplete observations under an exact low-rank constraint](https://mlsanity.com/paper/1610.09420/) (2016)
- [Dynamic Matrix Recovery](https://mlsanity.com/paper/2305.10524/) (2023)
- [Online Policy Learning and Inference by Matrix Completion](https://mlsanity.com/paper/2404.17398/) (2024)
- [Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information](https://mlsanity.com/paper/2403.14899/) (2024)

## Abstract (arXiv)

Noisy matrix completion has attracted significant attention due to its applications in recommendation systems, signal processing and image restoration. Most existing works rely on (weighted) least squares methods under various low-rank constraints. However, minimizing the sum of squared residuals is not always efficient, as it may ignore the potential structural information in the residuals. In this study, we propose a novel residual spectral matching criterion that incorporates not only the numerical but also locational information of residuals. This criterion is the first in noisy matrix completion to adopt the perspective of low-rank perturbation of random matrices and exploit the spectral properties of sparse random matrices. We derive optimal statistical properties by analyzing the spectral properties of sparse random matrices and bounding the effects of low-rank perturbations and partial observations. Additionally, we propose algorithms that efficiently approximate solutions by constructing easily computable pseudo-gradients. The iterative process of the proposed algorithms ensures convergence at a rate consistent with the optimal statistical error bound. Our method and algorithms demonstrate improved numerical performance in both simulated and real data examples, particularly in environments with high noise levels.