Dense Error Correction for Low-Rank Matrices via Principal Component Pursuit

2010/01/14 by Arvind Ganesh, Ganesh, Arvind, John Wright +7 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1001.2362

openalex publication_date 2010/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of recovering a low-rank matrix when some of its entries, whose locations are not known a priori, are corrupted by errors of arbitrarily large magnitude. It has recently been shown that this problem can be solved efficiently and effectively by a convex program named Principal Component Pursuit (PCP), provided that the fraction of corrupted entries and the rank of the matrix are both sufficiently small. In this paper, we extend that result to show that the same convex program, with a slightly improved weighting parameter, exactly recovers the low-rank matrix even if "almost all" of its entries are arbitrarily corrupted, provided the signs of the errors are random. We corroborate our result with simulations on randomly generated matrices and errors.

Citations

• The Approximation of One Matrix by Another of Lower Rank

Cited by

• Advanced Dimensionality Reduction for Imaging Mass Spectrometry of Human Eye Tissue through Low-Rank Modeling with Sparse and Dense Residuals

Related

• Stable Principal Component Pursuit
• Non-convex Robust PCA
• Principal Component Pursuit with Reduced Linear Measurements
• Robust Principal Component Analysis with Non-Sparse Errors
• Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery