# One-Bit Clustering for Two Component Sub-Gaussian Mixture Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 32 references that are in the map.
- First posted on arXiv 20 Jun 2026.

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

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [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)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterations](https://mlsanity.com/paper/1908.10935/) (2019)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Cutoff for exact recovery of Gaussian mixture models](https://mlsanity.com/paper/2001.01194/) (2020)
- [High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization](https://mlsanity.com/paper/2202.13157/) (2022)
- [The Generalized Lasso for Sub-gaussian Measurements with Dithered Quantization](https://mlsanity.com/paper/1807.06976/) (2018)
- [Mean Estimation from One-Bit Measurements](https://mlsanity.com/paper/1901.03403/) (2019)
- [Robust Mean Estimation under Quantization](https://mlsanity.com/paper/2601.07074/) (2026)
- [A Parameter-Free Two-Bit Covariance Estimator with Improved Operator Norm Error Rate](https://mlsanity.com/paper/2308.16059/) (2023)

## Abstract (arXiv)

Clustering is a fundamental problem in statistics and machine learning. We propose the first one-bit clustering method for two-component sub-Gaussian mixture models. The method uses only one bit per entry of each sample obtained via a dithered quantizer. Under a mild non-spikiness condition on the cluster centers, we show that a variant of Lloyd's algorithm achieves a misclassification rate that decays exponentially with a signal-to-noise ratio comparable to that in the unquantized setting. This result further implies exact recovery under an explicit separation condition, which exceeds the optimal threshold for unquantized data by only a logarithmic factor. When the dimension p is sufficiently large, the non-spikiness condition can be enforced by applying a random rotation using a Haar distributed matrix prior to quantization. In particular, it holds with high probability when p gtrsim 1 for partial recovery and p gtrsim log n loglog n for exact recovery, where n is the sample size. We also establish a minimax lower bound, showing that the misclassification rate and separation condition exhibit sharp constants in general. Numerical results are provided to corroborate the theory and demonstrate the efficacy of the proposed method.