Analysis Of Randomized Robust Pca For High Dimensional Data

Keywords

Big Data; Low Rank Matrix; Matrix Decomposition; Outlier Detection; Randomized Algorithm; Subspace Learning

Abstract

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.

Publication Date

12-30-2015

Publication Title

2015 IEEE Signal Processing and Signal Processing Education Workshop, SP/SPE 2015

Number of Pages

25-30

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/DSP-SPE.2015.7369522

Socpus ID

84964067983 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84964067983

This document is currently not available here.

Share

COinS