Scalable and robust PCA approach with random column/row sampling

摘要

This paper develops and analyzes a randomized design for robust Principal Component Analysis (PCA). In the proposed randomized method, a data sketch is constructed using random row sampling followed by random column sampling. The proposed randomized approach is 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 for the randomized approach is derived. It is shown that the correct subspace can be recovered with computational and sample complexity that are almost independent of the size of the data. The results of the mathematical analysis are confirmed through numerical simulations using both synthetic and real data.