Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes

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.