Randomized Robust Subspace Recovery And Outlier Detection For High Dimensional Data Matrices

Keywords

Big data; Column/row sampling; Low rank matrix; Outlier detection; Random embedding; Randomized algorithm; Robust PCA; Sketching; Subspace learning

Abstract

This paper explores and analyzes two randomized designs for robust principal component analysis employing low-dimensional data sketching. In one design, a data sketch is constructed using random column sampling followed by low-dimensional embedding, while in the other, sketching is based on random column and row sampling. Both designs are shown to bring about substantial savings in complexity and memory requirements for robust subspace learning over conventional approaches that use the full scale data. A characterization of the sample and computational complexity of both designs is derived in the context of two distinct outlier models, namely, sparse and independent outlier models. The proposed randomized approach can provably recover the correct subspace with computational and sample complexity which depend only weakly on the size of the data (only through the coherence parameters). The results of the mathematical analysis are confirmed through numerical simulations using both synthetic and real data.

Publication Date

3-15-2017

Publication Title

IEEE Transactions on Signal Processing

Volume

65

Issue

6

Number of Pages

1580-1594

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/TSP.2016.2645515

Socpus ID

85014938454 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS