  $k$-means clustering is a fundamental problem in various disciplines. This
problem is nonconvex, and standard algorithms are only guaranteed to find a
local optimum. Leveraging the structure of local solutions characterized in
[1], we propose a general algorithmic framework for escaping undesirable local
solutions and recovering the global solution (or the ground truth). This
framework consists of alternating between the following two steps iteratively:
(i) detect mis-specified clusters in a local solution and (ii) improve the
current local solution by non-local operations. We discuss implementation of
these steps, and elucidate how the proposed framework unifies variants of
$k$-means algorithm in literature from a geometric perspective. In addition, we
introduce two natural extensions of the proposed framework, where the initial
number of clusters is misspecified. We provide theoretical justification for
our approach, which is corroborated with extensive experiments.
