Experimental recovery regions for robust PCA

The principle of Robust Principal Component Analysis (RPCA) is to additively resolve a matrix into a low-rank and a sparse component. The question that arises in the application of this principle to experimental data is, "when is this resolution an identification of the actual low-rank and sparse components of the data?" We report several experimental findings: (1) while successful recoveries can only be expected when the low-rank component is of low fractional rank and the sparse component is of low fractional sparsity, the subset of matrices that successfully recover is significantly larger than the subset of matrices that satisfy the currently established sufficient conditions; (2) where recovery is unsuccessful, the returned matrices tend to be near half-rank and half-sparsity, suggesting a cross validation principle; (3) the demarcation between the region of consistent recovery and consistent failure is narrow, indicating a phase change in recoverability; and (4) recovery is relatively invariant to matrix distributions, thus synthetic matrices can closely predict recoverability of real matrices. We demonstrate these findings with a variety of synthetic matrices that are faithful to matrices appearing in practice. Furthermore, we apply and verify these results on real-world matrices. HighlightsReport empirical recovery regions of Robust PCA in rank-sparsity plane.Present a cross validation principle for identifying a successful decomposition.Demonstrate applicability of the found bounds to real world problems.