Improved Spectral-Norm Bounds for Clustering
  Aiming to unify known results about clustering mixtures of distributions
under separation conditions, Kumar and Kannan[2010] introduced a deterministic
condition for clustering datasets. They showed that this single deterministic
condition encompasses many previously studied clustering assumptions. More
specifically, their proximity condition requires that in the target
$k$-clustering, the projection of a point $x$ onto the line joining its cluster
center $\mu$ and some other center $\mu'$, is a large additive factor closer to
$\mu$ than to $\mu'$. This additive factor can be roughly described as $k$
times the spectral norm of the matrix representing the differences between the
given (known) dataset and the means of the (unknown) target clustering.
Clearly, the proximity condition implies center separation -- the distance
between any two centers must be as large as the above mentioned bound.
  In this paper we improve upon the work of Kumar and Kannan along several
axes. First, we weaken the center separation bound by a factor of $\sqrt{k}$,
and secondly we weaken the proximity condition by a factor of $k$. Using these
weaker bounds we still achieve the same guarantees when all points satisfy the
proximity condition. We also achieve better guarantees when only
$(1-\epsilon)$-fraction of the points satisfy the weaker proximity condition.
The bulk of our analysis relies only on center separation under which one can
produce a clustering which (i) has low error, (ii) has low $k$-means cost, and
(iii) has centers very close to the target centers.
  Our improved separation condition allows us to match the results of the
Planted Partition Model of McSherry[2001], improve upon the results of
Ostrovsky et al[2006], and improve separation results for mixture of Gaussian
models in a particular setting.
