Debiasing and a local analysis for population clustering using
  semidefinite programming
Shuheng Zhou
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 analyze computational efficient algorithms proposed by the same author, to
partition data into two groups approximately according to their population of
origin given a small sample. This work is motivated by the application of
clustering individuals according to their population of origin using $p$
markers, when the divergence between any two of the populations is small. We
build 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. Here we use $\Delta^2 :=p \gamma$ to denote the $\ell_2^2$
distance between two centers (mean vectors), namely, $\mu^{(1)}$, $\mu^{(2)}$
$\in$ $\mathbb{R}^p$. The goal is to 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, \Delta^2\}$
is lower bounded by a constant. Importantly, we prove that the
misclassification error decays exponentially with respect to the SNR $s^2$.
This result was introduced earlier without a full proof. We therefore present
the full proof in the present work. Finally, for balanced partitions, we
consider a variant of the SDP1, and show that the new estimator has a superb
debiasing property. This is novel to the best of our knowledge.