# Efficient Clustering for Stretched Mixtures: Landscape and Optimality

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2020.

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

- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Optimal Clustering in Anisotropic Gaussian Mixture Models](https://mlsanity.com/paper/2101.05402/) (2021)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolation](https://mlsanity.com/paper/2111.07041/) (2021)
- [Clustering Structure of Microstructure Measures](https://mlsanity.com/paper/2107.02283/) (2021)
- [Clustering Large Data Sets with Incremental Estimation of Low-density Separating Hyperplanes](https://mlsanity.com/paper/2108.03442/) (2021)

## Abstract (arXiv)

This paper considers a canonical clustering problem where one receives unlabeled samples drawn from a balanced mixture of two elliptical distributions and aims for a classifier to estimate the labels. Many popular methods including PCA and k-means require individual components of the mixture to be somewhat spherical, and perform poorly when they are stretched. To overcome this issue, we propose a non-convex program seeking for an affine transform to turn the data into a one-dimensional point cloud concentrating around -1 and 1, after which clustering becomes easy. Our theoretical contributions are two-fold: (1) we show that the non-convex loss function exhibits desirable geometric properties when the sample size exceeds some constant multiple of the dimension, and (2) we leverage this to prove that an efficient first-order algorithm achieves near-optimal statistical precision without good initialization. We also propose a general methodology for clustering with flexible choices of feature transforms and loss objectives.