# Robust Principal Component Analysis: A Median of Means Approach

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 72 references that are in the map.
- First posted on arXiv 5 Feb 2021.

## Builds on (most cited first, 15 of 15)

- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering](https://mlsanity.com/paper/1610.04794/) (2016)
- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery](https://mlsanity.com/paper/1711.09492/) (2017)
- [When OT meets MoM: Robust estimation of Wasserstein Distance](https://mlsanity.com/paper/2006.10325/) (2020)
- [Lecture Notes: Selected topics on robust statistical learning theory](https://mlsanity.com/paper/1908.10761/) (2019)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Robust PCA via Nonconvex Rank Approximation](https://mlsanity.com/paper/1511.05261/) (2015)
- [Regularization, sparse recovery, and median-of-means tournaments](https://mlsanity.com/paper/1701.04112/) (2017)
- [Excess risk bounds in robust empirical risk minimization](https://mlsanity.com/paper/1910.07485/) (2019)
- [Exactly Robust Kernel Principal Component Analysis](https://mlsanity.com/paper/1802.10558/) (2018)
- [K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Means](https://mlsanity.com/paper/2002.03899/) (2020)
- [Principal Ellipsoid Analysis (PEA): Efficient non-linear dimension reduction & clustering](https://mlsanity.com/paper/2008.07110/) (2020)
- [Kernel k-Means, By All Means: Algorithms and Strong Consistency](https://mlsanity.com/paper/2011.06461/) (2020)
- [Angular Embedding: A New Angular Robust Principal Component Analysis](https://mlsanity.com/paper/2011.11013/) (2020)

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

- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [Mean-Shift PCA by Knockoff Mean](https://mlsanity.com/paper/2605.25460/) (2026)

## Abstract (arXiv)

Principal Component Analysis (PCA) is a fundamental tool for data visualization, denoising, and dimensionality reduction. It is widely popular in Statistics, Machine Learning, Computer Vision, and related fields. However, PCA is well-known to fall prey to outliers and often fails to detect the true underlying low-dimensional structure within the dataset. Following the Median of Means (MoM) philosophy, recent supervised learning methods have shown great success in dealing with outlying observations without much compromise to their large sample theoretical properties. This paper proposes a PCA procedure based on the MoM principle. Called the Median of Means Principal Component Analysis (MoMPCA), the proposed method is not only computationally appealing but also achieves optimal convergence rates under minimal assumptions. In particular, we explore the non-asymptotic error bounds of the obtained solution via the aid of the Rademacher complexities while granting absolutely no assumption on the outlying observations. The derived concentration results are not dependent on the dimension because the analysis is conducted in a separable Hilbert space, and the results only depend on the fourth moment of the underlying distribution in the corresponding norm. The proposal's efficacy is also thoroughly showcased through simulations and real data applications.