We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine based on the sum-of-squares method that finds a low-dimensional separation-preserving projection of the input data. Our method provides a non-spherical analog of the classical dimension reduction based on singular value decomposition that, among several other applications, forms a key component of the celebrated spherical clustering algorithm of Vempala and Wang (2004). As applications, we obtain an algorithm to (1) cluster an arbitrary total-variation separated mixture of $k$ centered (i.e., zero-mean) Gaussians with $n\geq \mathrm{poly}(d) f(w_{\min}^{-1})$ samples and $\mathrm{poly}(n)$ time, and (2) cluster an arbitrary total-variation separated mixture of $k$ Gaussians with identical but arbitrary unknown covariance with $n \geq d^{O(\log w_{\min}^{-1})} f(w_{\min}^{-1})$ samples and $n^{O(\log w_{\min}^{-1})}$ time. Here, $w_{\min}$ is the minimum mixing weight of the input mixture, and $f$ does not depend on the dimension $d$. Our algorithms naturally extend to tolerate a dimension-independent fraction of arbitrary outliers. Before this work, the techniques in the state-of-the-art non-spherical clustering algorithms needed $d^{O(k)} f(w_{\min}^{-1})$ samples and time for clustering such mixtures. Our results may come as a surprise in the context of the $d^{\Omega(k)}$ statistical query and sum-of-squares lower bounds (Diakonikolas et al. (2017, 2024)) for clustering non-spherical Gaussian mixtures. While these results are usually thought to rule out $d^{o(k)}$ cost algorithms for the problem, our results show that the lower bounds can, in fact, be circumvented for a remarkably general class of Gaussian mixtures.

We consider the task of fitting low-dimensional embeddings to high-dimensional data. In particular, we study the \(k\)-Euclidean Metric Violation problem (\(k-\textsf{EMV}\)), where the input is \(D \in \mathbb{R}_{\geqslant 0}^{\binom{n}{2}}\) and the goal is to find the closest vector \(X \in \mathbb{M}_k\), where \(\mathbb{M}_k \subset \mathbb{R}_{\geqslant 0}^{\binom{n}{2}}\) is the set of all \(k\)-dimensional Euclidean metrics on \(n\) points, and closeness is formulated as the following optimization problem, where \(\|\cdot\|\) is the entry-wise \(\ell_2\) norm: \(\mathsf{OPT}_{\textsf{EMV}} = \min_{X \in \mathbb{M}_k} \|D - X\|_2^2\). Cayton and Dasgupta [CD06] showed that this problem is NP-Hard, even when \(k = 1\). Dhamdhere [Dha04] obtained a \(O(\log(n))\)-approximation for \(1-\textsf{EMV}\) and leaves finding a PTAS for it as an open question (reiterated recently by Lee [Lee25]). Although \(k-\textsf{EMV}\) has been studied in the statistics community for over 70 years, under the name “multi-dimensional scaling,” there are no known efficient approximation algorithms for \(k \gt 1\), to the best of our knowledge.

STOC ’25, Prague, Czechia