  In this paper, we consider the problem of partitioning a small data sample of
size $n$ drawn from a mixture of $2$ sub-gaussian distributions. In particular,
we design and analyze two computational efficient algorithms to partition data
into two groups approximately according to their population of origin given a
small sample in a recent paper (Zhou 2023a). Our work is motivated by the
application of clustering individuals according to their population of origin
using markers, when the divergence between any two of the populations is small.
Moreover, we are interested in the case that individual features are of low
average quality $\gamma$, and we want to use as few of them as possible to
correctly partition the sample. Here we use $p \gamma$ to denote the $\ell_2^2$
distance between two population centers (mean vectors), namely, $\mu^{(1)}$,
$\mu^{(2)}$ $\in$ ${\mathbb R}^p$. We allow a full range of tradeoffs between
$n, p, \gamma$ in the sense that partial recovery (success rate $< 100\%$) is
feasible once the signal to noise ratio $s^2 := \min\{np \gamma^2, p \gamma\}$
is lower bounded by a constant. Our work builds upon the semidefinite
relaxation of an integer quadratic program that is formulated essentially as
finding the maximum cut on a graph, where edge weights in the cut represent
dissimilarity scores between two nodes based on their $p$ features in Zhou
(2023a). More importantly, we prove that the misclassification error decays
exponentially with respect to the SNR $s^2$ in the present paper. The
significance of such an exponentially decaying error bound is: when $s^2
=\Omega(\log n)$, perfect recovery of the cluster structure is accomplished.
This result was introduced in Zhou (2023a) without a proof. We therefore
present the full proof in the present work.
