Analysis of Robust PCA via Local Incoherence

Huishuai Zhang, Yi Zhou, Yingbin LiangNeurIPS 2015 · OpenReview

Introduction

This paper refines the analysis of Robust Principal Component Analysis (RPCA) by moving beyond "global" averages to a "local" perspective. The authors prove that the success of matrix decomposition depends heavily on local incoherence. This means specific entries in a low-rank matrix can tolerate much higher corruption levels than others, depending entirely on how they align with the matrix's underlying structure.

The Problem: Moving Beyond Global Averages

Robust PCA is the task of taking a data matrix $M$ and decomposing it into a low-rank part $L$ (the signal) and a sparse part $S$ (the noise or outliers). The standard tool for this is Principal Component Pursuit (PCP), a convex optimization technique.

Previously, researchers assumed that errors in $S$ were spread uniformly across the matrix. However, in the real world, some data points are naturally more sensitive or prone to corruption than others. Existing theory relied on "global incoherence"—a worst-case metric that evaluates the entire matrix based on its most sensitive part. This paper addresses the gap between this pessimistic global theory and the reality of non-uniform error distributions, asking: Can we guarantee recovery if some parts of the matrix are heavily corrupted while others remain clean?

Methodology: A New Analytical Framework

The authors utilize the standard PCP algorithm, which minimizes a combination of the nuclear norm (to encourage low rank) and the $l_1$ norm (to encourage sparsity). The mathematical novelty lies in their analytical framework:

  1. Local Incoherence Parameters: They define a parameter $\mu_{ij}$ for every single entry $(i, j)$ based on how the low-rank matrix's singular vectors align with the canonical basis at that specific coordinate.
  2. Non-Uniform Bernoulli Sampling: Instead of assuming a single probability of error for the whole matrix, they allow each entry to have its own distinct corruption probability $\rho_{ij}$.
  3. New Weighted Norm: To prove their theorems, they introduce a new weighted norm $\| \cdot \|_{w(\infty)}$ that incorporates local structural information. This allows them to use a "golfing scheme" (a construction technique for dual certificates) tailored specifically to non-uniform distributions.

Key Insights: Not All Entries Are Created Equal

  • Robustness is Spatially Varying: Entries that are "more incoherent" (less aligned with specific rows or columns) are naturally more robust and can survive much higher error rates.
  • The "Bottleneck" Myth: Traditional theory suggests that if one part of a matrix is highly "coherent" (structured), the whole recovery might fail. This paper shows that as long as errors are distributed "intelligently" (avoiding the most sensitive spots), the total number of errors tolerated can be much higher than previously thought.
  • Cluster Size Matters: In clustering contexts, larger clusters are more robust to noise than smaller clusters because larger blocks in the matrix contribute to lower local incoherence.
  • The Necessity of $\mu_1$: While previous work on Matrix Completion suggested that one specific incoherence parameter ($\mu_1$) wasn't vital, this paper provides evidence that for Robust PCA, $\mu_1$ is essential for characterizing robustness.

Experimental Results: Adaptive vs. Uniform Noise

The authors validate their theory using synthetic datasets common in high-dimensional probability research: Bernoulli, Gaussian, and Cluster models.

They provide theoretical guarantees showing that PCP successfully recovers $L$ and $S$ as long as the "cleanliness" of an entry ($1 - \rho_{ij}$) is proportional to its local incoherence $\mu_{ij}$. To test this, they compared a "Uniform" error model (same probability everywhere) to an "Adaptive" error model (more errors placed in highly incoherent, robust areas).

Failure frequency vs. Error percentage for uniform and adaptive error models.

As shown above, the "Adaptive" model can tolerate significantly higher total error percentages—often 10% to 20% higher—while still achieving perfect recovery. There is a clear phase transition gap in performance between the two approaches across all tested matrix models.

Maximum tolerable error percentage across varying matrix ranks.

Furthermore, when evaluating the maximum tolerable error percentage against the rank of the matrix, the adaptive error distribution consistently outperforms the uniform distribution, confirming that the variance in local incoherence dictates how much noise a matrix can handle.

Limitations and Future Work

While the authors note the results can be extended to rectangular matrices, the primary proofs and experiments focus on square $n \times n$ matrices and assume the rank $r$ is relatively small compared to $n$.

Crucially, the authors suggest that their findings could lead to a "Weighted PCP" algorithm. If practitioners know which parts of their data are likely to be noisier, they could weight the optimization problem to improve recovery—a highly promising direction for future practical applications in fields like computer vision and bioinformatics.

Summary updated

Abstract

We investigate the robust PCA problem of decomposing an observed matrix into the sum of a low-rank and a sparse error matrices via convex programming Principal Component Pursuit (PCP). In contrast to previous studies that assume the support of the error matrix is generated by uniform Bernoulli sampling, we allow non-uniform sampling, i.e., entries of the low-rank matrix are corrupted by errors with unequal probabilities. We characterize conditions on error corruption of each individual entry based on the local incoherence of the low-rank matrix, under which correct matrix decomposition by PCP is guaranteed. Such a refined analysis of robust PCA captures how robust each entry of the low rank matrix combats error corruption. In order to deal with non-uniform error corruption, our technical proof introduces a new weighted norm and develops/exploits the concentration properties that such a norm satisfies.
BibTeX
@inproceedings{zhang2015analysis,
  author = {Huishuai Zhang and Yi Zhou and Yingbin Liang},
  title = {{Analysis of Robust PCA via Local Incoherence}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=H1WaR_Z_Wr},
}
Figure