# A Fourier Approach to Mixture Learning

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

## Key facts

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

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

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [Tight bounds for learning a mixture of two gaussians](https://mlsanity.com/paper/1404.4997/) (2014)
- [Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models](https://mlsanity.com/paper/2012.07774/) (2020)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments](https://mlsanity.com/paper/1912.07629/) (2019)
- [The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures](https://mlsanity.com/paper/1311.2891/) (2013)
- [Algorithmic Foundations for the Diffraction Limit](https://mlsanity.com/paper/2004.07659/) (2020)
- [Super-Resolution Off the Grid](https://mlsanity.com/paper/1509.07943/) (2015)
- [A Fourier analytique approach to Gaussian mixture learning](https://mlsanity.com/paper/2004.05813/) (2020)

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

- [Learning Mixtures of Gaussians with Censored Data](https://mlsanity.com/paper/2305.04127/) (2023)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models](https://mlsanity.com/paper/2404.12613/) (2024)
- [Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations](https://mlsanity.com/paper/2506.06613/) (2025)
- [Pair Correlation Factor and the Sample Complexity of Gaussian Mixtures](https://mlsanity.com/paper/2508.03633/) (2025)

## Abstract (arXiv)

We revisit the problem of learning mixtures of spherical Gaussians. Given samples from mixture frac1ksumj=1kN(μj, Id), the goal is to estimate the means μ1, μ2, ldots, μk ∈ ℝd up to a small error. The hardness of this learning problem can be measured by the separation Delta defined as the minimum distance between all pairs of means. Regev and Vijayaraghavan (2017) showed that with Delta = Omega(√log k) separation, the means can be learned using poly(k, d) samples, whereas super-polynomially many samples are required if Delta = o(√log k) and d = Omega(log k). This leaves open the low-dimensional regime where d = o(log k). In this work, we give an algorithm that efficiently learns the means in d = O(log k/loglog k) dimensions under separation d/√log k (modulo doubly logarithmic factors). This separation is strictly smaller than √log k, and is also shown to be necessary. Along with the results of Regev and Vijayaraghavan (2017), our work almost pins down the critical separation threshold at which efficient parameter learning becomes possible for spherical Gaussian mixtures. More generally, our algorithm runs in time poly(k)· f(d, Delta, ε), and is thus fixed-parameter tractable in parameters d, Delta and ε. Our approach is based on estimating the Fourier transform of the mixture at carefully chosen frequencies, and both the algorithm and its analysis are simple and elementary. Our positive results can be easily extended to learning mixtures of non-Gaussian distributions, under a mild condition on the Fourier spectrum of the distribution.