# Randomized Robust Subspace Recovery for High Dimensional Data Matrices

arXiv: https://arxiv.org/abs/1505.05901 · HTML: https://mlsanity.com/paper/1505.05901/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2015.

## Built on by (most cited first, 2 of 2)

- [A Robust Autoencoder Ensemble-Based Approach for Anomaly Detection in Text](https://mlsanity.com/paper/2405.13031/) (2024)
- [Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity](https://mlsanity.com/paper/2202.04020/) (2022)

## Abstract (arXiv)

This paper explores and analyzes two randomized designs for robust Principal Component Analysis (PCA) 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 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.