Title :
Principal Component Pursuit with reduced linear measurements
Author :
Ganesh, Arvind ; Min, Kerui ; Wright, John ; Ma, Yi
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Illinois at Urbana-Champaign, Urbana, IL, USA
Abstract :
In this paper, we study the problem of decomposing a superposition of a low-rank matrix and a sparse matrix when a relatively few linear measurements are available. This problem arises in many data processing tasks such as aligning multiple images or rectifying regular texture, where the goal is to recover a low-rank matrix with a large fraction of corrupted entries in the presence of nonlinear domain transformation. We consider a natural convex heuristic to this problem which is a variant to the recently proposed Principal Component Pursuit. We prove that under suitable conditions, this convex program guarantees to recover the correct low-rank and sparse components despite reduced measurements. Our analysis covers both random and deterministic measurement models.
Keywords :
data handling; principal component analysis; sparse matrices; task analysis; data processing tasks; low-rank matrix; nonlinear domain transformation; principal component pursuit; reduced linear measurements; sparse matrix; Information theory; Linear matrix inequalities; Manganese; Matrix decomposition; Numerical models; 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.6283063