Low-degree Lower bounds for clustering in moderate dimension

Alexandra Carpentier, Nicolas Verzelen

We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in ${\mathbb{R}}^d$. Specifically, we investigate the requisite…