# Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 11 Jun 2025.

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

- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Using SVD for Topic Modeling](https://mlsanity.com/paper/1704.07016/) (2017)
- [On Statistical Learning of Simplices: Unmixing Problem Revisited](https://mlsanity.com/paper/1810.07845/) (2018)
- [Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes](https://mlsanity.com/paper/2209.05953/) (2022)
- [Successive Projection Algorithm Robust to Outliers](https://mlsanity.com/paper/1908.04109/) (2019)
- [Improved Algorithm and Bounds for Successive Projection](https://mlsanity.com/paper/2403.11013/) (2024)

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

- [Robustness of Minimum-Volume Nonnegative Matrix Factorization under an Expanded Sufficiently Scattered Condition](https://mlsanity.com/paper/2511.04291/) (2025)
- [Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis](https://mlsanity.com/paper/2609.25576/) (2026)

## Abstract (arXiv)

In this paper, we establish sample complexity bounds for learning high-dimensional simplices in ℝK from noisy data. Specifically, we consider n i.i.d. samples uniformly drawn from an unknown simplex in ℝK, each corrupted by additive Gaussian noise of unknown variance. We prove an algorithm exists that, with high probability, outputs a simplex within ℓ2 or total variation (TV) distance at most varepsilon from the true simplex, provided n ≥ (K2/varepsilon2) eO(K/SNR2), where SNR is the signal-to-noise ratio. Extending our prior work~citepsaberi2023sample, we derive new information-theoretic lower bounds, showing that simplex estimation within TV distance varepsilon requires at least n ≥ Omega(K3 σ2/varepsilon2 + K/varepsilon) samples, where σ2 denotes the noise variance. In the noiseless scenario, our lower bound n ≥ Omega(K/varepsilon) matches known upper bounds up to constant factors. We resolve an open question by demonstrating that when SNR ≥ Omega(K1/2), noisy-case complexity aligns with the noiseless case. Our analysis leverages sample compression techniques (Ashtiani et al., 2018) and introduces a novel Fourier-based method for recovering distributions from noisy observations, potentially applicable beyond simplex learning.