Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA

2023/05/04 by Ilias Diakonikolas, Daniel M. Kane, Diakonikolas, Ilias +5
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Blind Source Separation Techniques #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2305.02544

Abstract

We study principal component analysis (PCA), where given a dataset in ℝ^d from a distribution, the task is to find a unit vector v that approximately maximizes the variance of the distribution after being projected along v. Despite being a classical task, standard estimators fail drastically if the data contains even a small fraction of outliers, motivating the problem of robust PCA. Recent work has developed computationally-efficient algorithms for robust PCA that either take super-linear time or have sub-optimal error guarantees. Our main contribution is to develop a nearly-linear time algorithm for robust PCA with near-optimal error guarantees. We also develop a single-pass streaming algorithm for robust PCA with memory usage nearly-linear in the dimension.

Related

• Robust Streaming PCA
• Thresholding based Efficient Outlier Robust PCA
• Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint
• Robust PCA in High-dimension: A Deterministic Approach
• Pseudo-Bayesian Robust PCA: Algorithms and Analyses