Title :
Compressive principal component pursuit
Author :
Wright, John ; Ganesh, Arvind ; Min, Kerui ; Ma, Yi
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 compressive sensing of superpositions of structured signals.
Keywords :
compressed sensing; principal component analysis; compressed sensing; compressive principal component pursuit; compressive sensing; hyperspectral images; linear measurements; low-rank superposition; natural convex heuristic; polylogarithmic factor; sparse components; sparse terms; structured high-dimensional signals; structured signal superpositions; target matrix; transformation invariant low-rank recovery; videos; Compressed sensing; Image coding; Manganese; Matrix decomposition; Q measurement; Robustness; Sparse matrices;
Conference_Titel :
Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on
Conference_Location :
Cambridge, MA
Print_ISBN :
978-1-4673-2580-6
Electronic_ISBN :
2157-8095
DOI :
10.1109/ISIT.2012.6283062