Low-Rank Matrix Recovery With Simultaneous Presence of Outliers and Sparse Corruption

• Published in: IEEE journal of selected topics in signal processing 2018-12, Vol.12 (6), p.1170-1181
• Main Authors: Rahmani, Mostafa, Atia, George K.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; big data; Corruption; Data models; Data points; data sketching; Mathematical analysis; Matrix decomposition; outlier detection; Outliers (statistics); Principal component analysis; Principal components analysis; randomization; Robust PCA; Robustness; Signal processing algorithms; sparse corruption; sparse matrix; Sparse representation; subspace learning; Unsupervised learning
• ISSN: 1932-4553; 1941-0484
• DOI: 10.1109/JSTSP.2018.2876604

We study a data model in which the data matrix D ∈ R N1 ×N2 can be expressed as D = L + S + C, where L is a low-rank matrix, S is an elementwise sparse matrix, and C is a matrix whose nonzero columns are outlying data points. To date, robust principal component analysis (PCA) algorithms have solely considered models with either S or C, but not both. As such, existing algorithms cannot account for simultaneous elementwise and columnwise corruptions. In this paper, a new robust PCA algorithm that is robust to simultaneous types of corruption is proposed. Our approach hinges on the sparse approximation of a sparsely corrupted column so that the sparse expansion of a column with respect to the other data points is used to distinguish a sparsely corrupted inlier column from an outlying data point. We also develop a randomized design that provides a scalable implementation of the proposed approach. The core ideaof sparse approximation is analyzed analytically where we show that the underlying ℓ 1 -norm minimization can obtain the representation of an inlier in presence of sparse corruptions.