Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm

Abstract--Robust PCA, the problem of PCA in the presence of outliers has been extensively investigated in the last few years. Here we focus on Robust PCA in the outlier model where each column of the data matrix is either an inlier or an outlier. Most of the existing methods for this model assumes either the knowledge of the dimension of the lower dimensional subspace or the fraction of outliers in the system. However in many applications knowledge of these parameters is not available. Motivated by this we propose a parameter free outlier identification method for robust PCA which a) does not require the knowledge of outlier fraction, b) does not require the knowledge of the dimension of the underlying subspace, c) is computationally simple and fast d) can handle structured and unstructured outliers. Further, analytical guarantees are derived for outlier identification and the performance of the algorithm is compared with the existing state of the art methods in both real and synthetic data for various outlier structures. Principal Component Analysis (PCA) [1] is a very widely used technique in data analysis and dimensionality reduction. Singular Value Decomposition (SVD) of the data matrix M [2] is known to be very sensitive to extreme corruptions in the data [3], [4], [5] and hence robustifying the PCA process becomes a necessity. Robust PCA is typically an ill posed problem and it is of significant importance in a wide variety of fields like computer vision, machine learning, survey data analysis and so on. Of the numerous approaches to robust PCA over the years [8], [9], one way to model extreme corruptions in the given data matrix M, is using the following decomposition [10], [11], [12], [3]: M L S, where S encapsulates all the corruptions and is assumed to be sparse and L is low rank.