# Robust Matrix Completion with Heavy-tailed Noise arXiv: https://arxiv.org/abs/2206.04276 · HTML: https://mlsanity.com/paper/2206.04276/ ## Key facts - Cited by 4 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 87 references that are in the map. - First posted on arXiv 9 Jun 2022. ## Builds on (most cited first, 30 of 34) - [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015) - [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018) - [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020) - [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015) - [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014) - [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018) - [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015) - [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017) - [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017) - [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019) - [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013) - [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) - [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014) - [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013) - [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017) - [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019) - [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020) - [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013) - [Statistical consistency and asymptotic normality for high-dimensional robust M-estimators](https://mlsanity.com/paper/1501.00312/) (2015) - [A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery](https://mlsanity.com/paper/1603.08315/) (2016) - [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020) - [Can parametric statistical methods be trusted for fMRI based group studies?](https://mlsanity.com/paper/1511.01863/) (2015) - [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021) - [Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries](https://mlsanity.com/paper/1605.07129/) (2016) - [Statistical Inferences of Linear Forms for Noisy Matrix Completion](https://mlsanity.com/paper/1909.00116/) (2019) - [Fast matrix completion without the condition number](https://mlsanity.com/paper/1407.4070/) (2014) - [Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent](https://mlsanity.com/paper/1605.08370/) (2016) - [Nonconvex Matrix Factorization from Rank-One Measurements](https://mlsanity.com/paper/1802.06286/) (2018) - [Matrix Completion with Noisy Entries and Outliers](https://mlsanity.com/paper/1503.00214/) (2015) ## Built on by (most cited first, 4 of 4) - [Robust High-dimensional Tuning Free Multiple Testing](https://mlsanity.com/paper/2211.11959/) (2022) - [Towards Reliable Recommender Systems for Rating Data](https://mlsanity.com/paper/2412.20802/) (2024) - [RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees](https://mlsanity.com/paper/2505.12919/) (2025) - [Transformed ℓ1 Regularizations for Robust Principal Component Analysis: Toward a Fine-Grained Understanding](https://mlsanity.com/paper/2510.03624/) (2025) ## Abstract (arXiv) This paper studies low-rank matrix completion in the presence of heavy-tailed and possibly asymmetric noise, where we aim to estimate an underlying low-rank matrix given a set of highly incomplete noisy entries. Though the matrix completion problem has attracted much attention in the past decade, there is still lack of theoretical understanding when the observations are contaminated by heavy-tailed noises. Prior theory falls short of explaining the empirical results and is unable to capture the optimal dependence of the estimation error on the noise level. In this paper, we adopt an adaptive Huber loss to accommodate heavy-tailed noise, which is robust against large and possibly asymmetric errors when the parameter in the loss function is carefully designed to balance the Huberization biases and robustness to outliers. Then, we propose an efficient nonconvex algorithm via a balanced low-rank Burer-Monteiro matrix factorization and gradient decent with robust spectral initialization. We prove that under merely bounded second moment condition on the error distributions, rather than the sub-Gaussian assumption, the Euclidean error of the iterates generated by the proposed algorithm decrease geometrically fast until achieving a minimax-optimal statistical estimation error, which has the same order as that in the sub-Gaussian case. The key technique behind this significant advancement is a powerful leave-one-out analysis framework. The theoretical results are corroborated by our simulation studies.