Improved Spectral-Norm Bounds for Clustering

Understand

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.