# Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 25 references that are in the map.
- First posted on arXiv 9 Sep 2022.

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

- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Algorithmic Foundations for the Diffraction Limit](https://mlsanity.com/paper/2004.07659/) (2020)
- [On Statistical Learning of Simplices: Unmixing Problem Revisited](https://mlsanity.com/paper/1810.07845/) (2018)
- [A Fourier analytique approach to Gaussian mixture learning](https://mlsanity.com/paper/2004.05813/) (2020)

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

- [Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes](https://mlsanity.com/paper/2506.10101/) (2025)
- [Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts](https://mlsanity.com/paper/2410.20250/) (2024)
- [Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations](https://mlsanity.com/paper/2506.06613/) (2025)
- [Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis](https://mlsanity.com/paper/2609.25576/) (2026)

## Abstract (arXiv)

In this paper, we find a sample complexity bound for learning a simplex from noisy samples. Assume a dataset of size n is given which includes i.i.d. samples drawn from a uniform distribution over an unknown simplex in ℝK, where samples are assumed to be corrupted by a multi-variate additive Gaussian noise of an arbitrary magnitude. We prove the existence of an algorithm that with high probability outputs a simplex having a ℓ2 distance of at most varepsilon from the true simplex (for any varepsilon>0). Also, we theoretically show that in order to achieve this bound, it is sufficient to have n≥left(K2/varepsilon2right)eOmegaleft(K/SNR2right) samples, where SNR stands for the signal-to-noise ratio. This result solves an important open problem and shows as long as SNR≥Omegaleft(K1/2right), the sample complexity of the noisy regime has the same order to that of the noiseless case. Our proofs are a combination of the so-called sample compression technique in citepashtiani2018nearly, mathematical tools from high-dimensional geometry, and Fourier analysis. In particular, we have proposed a general Fourier-based technique for recovery of a more general class of distribution families from additive Gaussian noise, which can be further used in a variety of other related problems.