# Optimal Clustering in Anisotropic Gaussian Mixture Models

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 14 Jan 2021.

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

- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Efficient Clustering for Stretched Mixtures: Landscape and Optimality](https://mlsanity.com/paper/2003.09960/) (2020)

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

- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolation](https://mlsanity.com/paper/2111.07041/) (2021)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)
- [VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates](https://mlsanity.com/paper/2402.18805/) (2024)

## Abstract (arXiv)

We study the clustering task under anisotropic Gaussian Mixture Models where the covariance matrices from different clusters are unknown and are not necessarily the identical matrix. We characterize the dependence of signal-to-noise ratios on the cluster centers and covariance matrices and obtain the minimax lower bound for the clustering problem. In addition, we propose a computationally feasible procedure and prove it achieves the optimal rate within a few iterations. The proposed procedure is a hard EM type algorithm, and it can also be seen as a variant of the Lloyd's algorithm that is adjusted to the anisotropic covariance matrices.