Compressive Principal Component Pursuit

Abstract

We consider the problem of recovering a target matrix that is a superposition of low-rank and sparse components, from a small set of linear measurements. This problem arises in compressed sensing of structured high-dimensional signals such as videos and hyperspectral images, as well as in the analysis of transformation invariant low-rank recovery. We analyze the performance of the natural convex heuristic for solving this problem, under the assumption that measurements are chosen uniformly at random. We prove that this heuristic exactly recovers low-rank and sparse terms, provided the number of observations exceeds the number of intrinsic degrees of freedom of the component signals by a polylogarithmic factor. Our analysis introduces several ideas that may be of independent interest for the more general problem of compressed sensing and decomposing superpositions of multiple structured signals.

30 pages, 1 figure, preliminary version submitted to ISIT'12

References in corpus (2)

• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• Robust Matrix Decomposition with Outliers

Cited by in corpus (9)

• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Sharp MSE Bounds for Proximal Denoising
• Time Series Forecasting via Learning Convolutionally Low-Rank Models
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Novel Factorization Strategies for Higher Order Tensors: Implications for Compression and Recovery of Multi-linear Data
• A Counterexample for the Validity of Using Nuclear Norm as a Convex Surrogate of Rank
• Principal Component Pursuit with Reduced Linear Measurements
• Low-Rank Modeling and Its Applications in Image Analysis
• Recursive Sparse Recovery in Large but Structured Noise - Part 2