# Probabilistic methods for approximate archetypal analysis

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 12 Aug 2021.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [Fast and Guaranteed Tensor Decomposition via Sketching](https://mlsanity.com/paper/1506.04448/) (2015)
- [Fast and Robust Archetypal Analysis for Representation Learning](https://mlsanity.com/paper/1405.6472/) (2014)
- [Non-negative Matrix Factorization via Archetypal Analysis](https://mlsanity.com/paper/1705.02994/) (2017)
- [Randomized Nonnegative Matrix Factorization](https://mlsanity.com/paper/1711.02037/) (2017)
- [Consistency of archetypal analysis](https://mlsanity.com/paper/2010.08148/) (2020)

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

- [A Survey on Archetypal Analysis](https://mlsanity.com/paper/2504.12392/) (2025)
- [Archetypal Analysis++: Rethinking the Initialization Strategy](https://mlsanity.com/paper/2301.13748/) (2023)
- [Archetypal Analysis for Binary Data](https://mlsanity.com/paper/2502.04172/) (2025)
- [Wasserstein Archetypal Analysis](https://mlsanity.com/paper/2210.14298/) (2022)

## Abstract (arXiv)

Archetypal analysis is an unsupervised learning method for exploratory data analysis. One major challenge that limits the applicability of archetypal analysis in practice is the inherent computational complexity of the existing algorithms. In this paper, we provide a novel approximation approach to partially address this issue. Utilizing probabilistic ideas from high-dimensional geometry, we introduce two preprocessing techniques to reduce the dimension and representation cardinality of the data, respectively. We prove that provided the data is approximately embedded in a low-dimensional linear subspace and the convex hull of the corresponding representations is well approximated by a polytope with a few vertices, our method can effectively reduce the scaling of archetypal analysis. Moreover, the solution of the reduced problem is near-optimal in terms of prediction errors. Our approach can be combined with other acceleration techniques to further mitigate the intrinsic complexity of archetypal analysis. We demonstrate the usefulness of our results by applying our method to summarize several moderately large-scale datasets.