One-Bit Clustering for Two Component Sub-Gaussian Mixture Models
This work addresses the problem of clustering under extreme memory constraints (one bit per entry) for statisticians and machine learning practitioners, providing theoretical guarantees that match unquantized performance up to logarithmic factors.
The paper proposes the first one-bit clustering method for two-component sub-Gaussian mixture models, achieving exponential decay in misclassification rate with signal-to-noise ratio comparable to unquantized settings, and exact recovery under a separation condition exceeding the optimal threshold by only a logarithmic factor.
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 \log\log 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.