Analysis of randomized robust PCA for high dimensional data

Robust Principal Component Analysis (PCA) (or robust subspace recovery) is a particularly important problem in unsupervised learning pertaining to a broad range of applications. In this paper, we analyze a randomized robust subspace recovery algorithm to show that its complexity is independent of the size of the data matrix. Exploiting the intrinsic low-dimensional geometry of the low rank matrix, the big data matrix is first turned to smaller size compressed data. This is accomplished by selecting a small random subset of the columns of the given data matrix, which is then projected into a random low-dimensional subspace. In the next step, a convex robust PCA algorithm is applied to the compressed data to learn the columns subspace of the low rank matrix. We derive new sufficient conditions, which show that the number of linear observations and the complexity of the randomized algorithm do not depend on the size of the given data.