Improved Spectral-Norm Bounds for Clustering

Introduction

In the long-studied field of clustering, there has been substantial work [Das99, DS07, SK01, VW02, AM05, CR08b, KSV08, DHKM07, BV08] studying the problem of clustering data from mixture of distributions under the assumption that the means of the distributions are sufficiently far apart. Each of these works focuses on one particular type (or family) of distribution, and devise an algorithm that successfully clusters datasets that come from that particular type. Typically, they show that w.h.p. such datasets have certain nice properties, then use these properties in the construction of the clustering algorithm.

The recent work of Kumar and Kannan [KK10] takes the opposite approach. First, they define a separation condition, deterministic and thus not tied to any distribution, and show that any set of data points satisfying this condition can be successfully clustered. Having established that, they show that many previously studied clustering problems indeed satisfy (w.h.p) this separation condition. These clustering problems include Gaussian mixture-models, the Planted Partition model of McSherry [McS01] and the work of Ostrovsky et al [ORSS06]. In this aspect they aim to unify the existing body of work on clustering under separation assumptions, proving that one algorithm applies in multiple scenarios.We comment that, implicitly, Achlioptas and McSherry [AM05] follow a similar approach, yet they focus only on mixtures of Gaussians and log-concave distributions. Another deterministic condition for clustering was considered by [CO10], which generalized the Planted Partition Model of [McS01].

However, the attempt to unify multiple clustering works is only successful in part. First, Kumar and Kannan’s analysis is “wasteful” w.r.t the number of clusters $k$. Clearly, motivated by an underlying assumption that $k$ is constant, their separation bound has linear dependence in $k$ and their classification guarantee has quadratic dependence on $k$. As a result, Kumar and Kannan overshoot best known bounds for the Planted Partition Model and for mixture of Gaussians by a factor of $\sqrt{k}$. Similarly, the application to datasets considered by Ostrovsky et al only holds for constant $k$. Secondly, the analysis in Kumar-Kannan is far from simple – it relies on most points being “good”, and requires multiple iterations of Lloyd steps before converging to good centers. Our work addresses these issues.

Fix $i\in T_{r}$. We say a datapoint $A_{i}$ satisfies the Kumar-Kannan proximity condition if for any $s\neq r$, when projecting $A_{i}$ onto the line connecting $\mu_{r}$ and $\mu_{s}$, the projection of $A_{i}$ is closer to $\mu_{r}$ than to $\mu_{s}$ by an additive factor of $\Omega\left(k(\frac{1}{\sqrt{n_{r}}}+\frac{1}{\sqrt{n_{s}}})\|A-C\|\right)$.

Kumar and Kannan proved that if all but at most $\epsilon$-fraction of the data points satisfy the proximity condition, they can find a clustering which is correct on all but an $O(k^{2}\epsilon)$-fraction of the points. In particular, when $\epsilon=0$, their algorithm clusters all points correctly. Observe, the Kumar-Kannan proximity condition gives that the distance $\|\mu_{r}-\mu_{s}\|$ is also bigger than the above mentioned bound. The opposite also holds – one can show that if $\|\mu_{r}-\mu_{s}\|$ is greater than this bound then only few of the points do not satisfy the proximity condition.

In this work, the bulk of our analysis is based on the following quantitatively weaker version of the proximity condition, which we call center separation. Formally, we define $\Delta_{r}=\frac{1}{\sqrt{n_{r}}}\min\{\sqrt{k}\|A-C\|,\|A-C\|_{F}\}$ and we assume throughout the paper that for a large constantWe comment that throughout the paper, and much like Kumar and Kannan, we think of $c$ as a large constant ($c=100$ will do). However, our results also hold when $c=\omega(1)$, allowing for a $(1+o(1))$-approximation. We also comment that we think of $d\gg k$, so one should expect $\|A-C\|_{F}^{2}\geq k\|A-C\|^{2}$ to hold, thus the reader should think of $\Delta_{r}$ as dependent on $\sqrt{k}\|A-C\|$. Still, including the degenerate case, where $\|A-C\|_{F}^{2}<k\|A-C\|$, simplifies our analysis in Section 3. One final comment is that (much like all the work in this field) we assume $k$ is given, as part of the input, and not unknown. $c$ we have that the means of any two clusters $T_{r}$ and $T_{s}$ satisfy

Observe that this is a simpler version of the Kumar-Kannan proximity condition, scaled down by a factor of $\sqrt{k}$. Even though we show that (1) gives that only a few points do not satisfy the proximity condition, our analysis (for the most part) does not partition the dataset into good and bad points, based on satisfying or non-satisfying the proximity condition. Instead, our analysis relies on basic tools, such as the Markov inequality and the triangle inequality. In that sense one can view our work as “aligning” Kumar and Kannan’s work with the rest of clustering-under-center-separation literature – we show that the bulk of Kannan and Kumar’s analysis can be simplified to rely merely on center-separation.

Our results.

We improve upon the results of [KK10] along several axes. In addition to the weaker condition of Equation (1), we also weaken the Kumar-Kannan proximity condition by a factor of $k$, and still retrieve the target clustering, if all points satisfy the ($k$-weaker) proximity condition. Secondly, if at most $\epsilon n$ points do not satisfy the $k$-weaker proximity condition, we show that we can correctly classify all but a $(\epsilon+O(1/c^{4}))$-fraction of the points, improving over the bound of [KK10] of $O(k^{2}\epsilon)$. Note that our bound is meaningful even if $\epsilon$ is a constant whereas $k=\omega(1)$. Furthermore, we prove that the $k$-means cost of the clustering we output is a $(1+O(1/c))$-approximation of the $k$-means cost of the target clustering.

Once we have improved on the main theorem of Kumar and Kannan, we derive immediate improvements on its applications. In Section 3.1 we show our analysis subsumes the work of Ostrovsky et al [ORSS06], and applies also to non-constant $k$. Using the fact that Equation (1) “shaves off” a $\sqrt{k}$ factor from the separation condition of Kumar and Kannan, we obtain a separation condition of $\Omega(\sigma_{\max}\sqrt{k})$ for learning a mixture of Gaussians, and we also match the separation results of the Planted Partition model of McSherry [McS01]. These results are described in Section 5.

From an approximation-algorithms perspective, it is clear why the case of $k=\omega(1)$ is of interest, considering the ubiquity of $k$-partition problems in TCS (e.g., $k$-Median, Max $k$-coverage, Knapsack for $k$ items, maximizing social welfare in $k$-items auction – all trivially simple for constant $k$). In addition, we comment that in our setting only the case where $k=\omega(1)$ is of interest, since otherwise one can approximate the $k$-means cost using the PTAS of Kumar et al [KSS04], which doesn’t even require any separation assumptions. From a practical point of view, there is a variety of applications where $k$ is quite large. This includes problems such as clustering images by who is in them, clustering protein sequences by families of organisms, and problems such as deduplication where multiple databases are combined and entries corresponding to the same true entity are to be clustered together [CR02, MBHC95]. The challenges that arise from treating $k$ as a non-constant are detailed in the proofs overview (Section 1.4).

To formally detail our results, we first define some notations and discuss a few preliminary facts.

2 Notations and Preliminaries

The Frobenius norm of a $n\times m$ matrix $M$, denoted as $\|M\|_{F}$ is defined as $\|M\|_{F}=\sqrt{\sum_{i,j}M_{i,j}^{2}}$. The spectral norm of $M$ is defined as $\|M\|=\max_{x:\|x\|=1}\|Mx\|$. It is a well known fact that if the rank of $M$ is $t$, then $\|M\|_{F}^{2}\leq t\|M\|^{2}$. The Singular Value Decomposition (SVD) of $M$ is a decomposition of $M$ as $M=U\Sigma V^{T}$, where $U$ is a $n\times n$ unitary matrix, $V$ is a $m\times m$ unitary matrix, $\Sigma$ is a $n\times m$ diagonal matrix whose entries are nonnegative real numbers, and its diagonal entries satisfy $\sigma_{1}\geq\sigma_{2}\geq\ldots\geq\sigma_{\min\{m,n\}}$. The diagonal entries in $\Sigma$ are called the singular values of $M$, and the columns of $U$ and $V$, denoted $u_{i}$ and $v_{i}$ resp., are called the left- and right-singular vectors. As a convention, when referring to singular vectors, we mean the right-singular vectors. Observe that the Singular Value Decomposition allows us to write $M=\sum_{i=1}^{\textrm{rank}(\Sigma)}\sigma_{i}u_{i}v_{i}^{T}$. Projecting $M$ onto its top $t$ singular vectors means taking $\hat{M}=\sum_{i=1}^{t}\sigma_{i}u_{i}v_{i}^{T}$. It is a known fact that for any $t$, the $t$-dimensional subspace which best fits the rows of $M$, is obtained by projecting $M$ onto the subspace spanned by the top $t$ singular vectors (corresponding to the top $t$ singular values). Another way to phrase this result is by saying that $\hat{M}=\arg\min_{N:\textrm{rank}(N)=t}\{\|M-N\|_{F}\}$. For a proof, see [KV09]. The same matrix, $\hat{M}$, also minimizes the spectral norm of this difference, meaning $\hat{M}=\arg\min_{N:\textrm{rank}(N)=t}\{\|M-N\|\}$ (see [GVL96] for proof).

As previously defined, $\|A-C\|$ denotes the spectral norm of $A-C$. The target clustering, $\mathcal{T}$, is composed of $k$ clusters $T_{1},T_{2},\ldots,T_{k}$. Observe that we use $\mu$ as an operator, where for every set $X$, we have $\mu(X)=\tfrac{1}{|X|}\sum_{i\in X}A_{i}$. We abbreviate, and denote $\mu_{r}=\mu(T_{r})$. From this point on, we denote the projection of $A$ onto the subspace spanned by its top $k$-singular vectors as $\hat{A}$, and for any vector $v$, we denote $\hat{v}$ as the projection of $v$ onto this subspace. Throughout the paper, we abuse notation and use $i$ to iterate over the rows of $A$, whereas $r$ and $s$ are used to iterate over clusters (or submatrices). So $A_{i}$ represents the $i$th row of $A$ whereas $A_{r}$ represents the submatrix $[A_{i}]_{\{i\in T_{r}\}}$.

The analysis of our main theorem makes use of the following facts, from [McS01, KV09, KK10]. We advise the reader to go over the proofs, which are short, elegant, and provided in Appendix A. The first fact bounds the cost of assigning the points of $\hat{A}$ to their original centers.

\|\hat{A}-C\|_{F}^{2}\leq 8\min\{k\|A-C\|^{2},\|A-C\|_{F}^{2}\}\ \ \biggl{(}=8n_{r}\Delta_{r}^{2}\ \textrm{ for every }r\biggr{)}.

Next, we show that we can match each target center $\mu_{r}$ to a unique, relatively close, center $\nu_{r}$ that we get in Part I of the algorithm.

For every $\mu_{r}$ there exists a center $\nu_{s}$ s.t. $\|\mu_{r}-\nu_{s}\|\leq 6\Delta_{r}$, so we can match each $\mu_{r}$ to a unique $\nu_{r}$.

Finally, we exhibit the following fact, which is detailed in the analysis of [KK10].

Fix a target cluster $T_{r}$ and let $S_{r}$ be a set of points created by removing $\rho_{out}n_{r}$ points from $T_{r}$ and adding $\rho_{in}(s)n_{r}$ points from each cluster $s\neq r$, s.t. every added point $x$ satisfies $\|x-\mu_{s}\|\geq\tfrac{2}{3}\|x-\mu_{r}\|$. Assume $\rho_{out}<\tfrac{1}{4}$ and $\rho_{in}\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{s\neq r}\rho_{in}(s)<\tfrac{1}{4}$. Then

3 Formal Description of the Algorithm and Our Theorems

Having established notation, we now present our algorithm, in Figure 1. Our algorithm’s goal is three fold: (a) to find a partition that identifies with the target clustering on the majority of the points, (b) to have the $k$-means cost of this partition comparable with the target, and (c) output $k$ centers which are close to the true centers. It is partitioned into $3$ parts. Each part requires stronger assumptions, allowing us to prove stronger guarantees.

Assuming only the center separation of (1), then Part I gives a clustering which (a) is correct on at least $1-O(c^{-2})$ fraction of the points from each target cluster (Theorem 3.1), and (b) has $k$-means cost smaller than $(1+O(1/c))\|A-C\|_{F}^{2}$ (Theorem 3.2).

Assuming also that $\Delta_{r}=\frac{\sqrt{k}}{\sqrt{n_{r}}}\|A-C\|$, i.e. assuming the non-degenerate case where $\|A-C\|_{F}^{2}\geq k\|A-C\|^{2}$, then Part II finds centers that are $O(1/c)\frac{\|A-C\|}{\sqrt{n_{r}}}$ close to the true centers (Theorem 4.1). As a result (see Section 4.1), if $(1-\epsilon)n$ points satisfy the proximity condition (weakened by a $k$ factor,), then we misclassify no more than $(\epsilon+O(c^{-4}))n$ points.

Assuming all points satisfy the proximity condition (weakened by a $k$-factor), Part III finds exactly the target partition (Theorem 4.8).

4 Organization and Proofs Overview

Related work is detailed in Section 2. The analysis of Part I of our algorithms is in Section 3. Part I is enough for us to give a “one-line” proof in Section 3.1 showing how the work of Ostrovsky et al falls into our framework. The analysis of Part II of the algorithm is in Section 4. The improved guarantees we get by applying the algorithm to the Planted Partition model and to the Gaussian mixture model are discussed in Section 5. We conclude with an open problem in Section 6.

Proof outline for Section 3.

The first part of our analysis is an immediate application of Facts 1.1 and 1.2. Our assumption dictates that the distance between any two centers is big ($\geq c(\Delta_{r}+\Delta_{s})$). Part I of the algorithm assigns each projected point $\hat{A}_{i}$ to the nearest $\nu_{r}$ instead of the true center $\mu_{r}$ and Fact 1.2 assures that the distance $\|\mu_{r}-\nu_{r}\|$ is small ($<6\Delta_{r}$). Consider a misclassified point $A_{i}$, where $\|A_{i}-\mu_{r}\|<\|A_{i}-\mu_{s}\|$ yet $\|\hat{A}_{i}-\nu_{s}\|<\|\hat{A}_{i}-\nu_{r}\|$. The triangle inequality assures that $\hat{A}_{i}$ has a fairly big distance to its true center ($>(\tfrac{c}{2}-12)\Delta_{r}$). We deduce that each misclassified point contributes $\Omega(c^{2}\Delta_{r}^{2})$ to the $k$-means cost of assigning all projected points to their true centers. Fact 1.1 bounds this cost by $\|\hat{A}-C\|_{F}^{2}\leq 8n_{r}\Delta_{r}^{2}$, so the Markov inequality proves only a few points are misclassified. Additional application of the triangle inequality for misclassified points gives that the distance between the original point $A_{i}$ and a true center $\mu_{r}$ is comparable to the distance $\|A_{i}-\mu_{s}\|$, and so assigning $A_{i}$ to the cluster $s$ only increases the $k$-means cost by a small factor.

Proof outline for Section 4.

In the second part of our analysis we compare between the true clustering $\mathcal{T}$ and some proposed clustering $\mathcal{S}$, looking both at the number of misclassified points and at the distances between the matching centers $\|\mu_{r}-\theta_{r}\|$. As Kumar and Kannan show, the two measurements are related: Fact 1.3 shows how the distances between the means depend on the number of misclassified points, and the main lemma (Lemma 4.5) essentially shows the opposite direction. These two relations are how Kumar and Kannan show that Lloyd steps converge to good centers, yielding clusters with few misclassified points. They repeatedly apply (their version of) the main lemma, showing that with each step the distances to the true means decrease and so fewer of the good points are misclassified.

To improve on Kumar and Kannan analysis, we improve on the two above-mentioned relations. Lemma 4.5 is a simplification of a lemma from Kumar and Kannan, where instead of projecting into a $k$-dimensional space, we project only into a $4$-dimensional space, thus reducing dependency on $k$. However, the dependency of Fact 1.3 on $k$ is tightIn fact, Fact 1.3 is exactly why the case of $k=\omega(1)$ is hard – because the $L_{1}$ and $L_{2}$ norms of the vector $(\tfrac{1}{\sqrt{k}},\tfrac{1}{\sqrt{k}},\ldots,\tfrac{1}{\sqrt{k}})$ are not comparable for non-constant $k$.. So in Part II of the algorithm we devise sub-clusters $S_{r}$ s.t. $\rho_{in}(s)=\rho_{out}/k^{2}$. The crux in devising $S_{r}$ lies in Proposition 4.4 – we show that any misclassified projected point $i\in T_{s}\cap S_{r}$ is essentially misclassified by $\hat{\mu_{r}}$. And since (see [AM05]) $\|\mu_{r}-\hat{\mu_{r}}\|\leq\tfrac{1}{\sqrt{k}}\Delta_{r}$ (compared to the bound $\|\mu_{r}-\nu_{r}\|\leq 6\Delta_{r}$), we are able to give a good bound on $\rho_{in}(s)$.

Recall that we rely only on center separation rather than a large batch of points satisfying the Kumar-Kannan separation, and so we do not apply iterative Lloyd steps (unless all points are good). Instead, we apply the main lemma only once, w.r.t to the misclassified points in $T_{s}\cap S_{r}$, and deduce that the distances $\|\mu_{r}-\theta_{r}\|$ are small. In other words, Part II is a single step that retrieve centers whose distances to the original centers are $\sqrt{k}$-times better than the centers retrieved by Kumar and Kannan in numerous Lloyd iterations.

5 Acknowledgements

We would like to thanks Avrim Blum for multiple helpful discussions and suggestions. We thank Amit Kumar for clarifying a certain point in the original Kumar and Kannan paper. We thank the anonymous referees for their suggestions, and especially regarding a discussion about the result of Achlioptas and McSherry.

Related Work

There has been an extensive line of work on approximation algorithms for the $k$-means problem ([OR00, BHPI02, dlVKKR03, ES04, HPM04, KMN+02]). The current best guarantee is a $(9+\epsilon)$-approximation algorithm of [KMN+02] (with a much simpler analysis in [GT08]) if polynomial dependence on $k$ and the dimension $d$ is desired.For constant $k$, [KSS04] give a PTAS for the $k$-means problem. Another popular algorithm for $k$-means is the Lloyd’s heuristics ([Llo82]). This heuristics, combined with a careful seeding of centers, has been shown to have good performance if the data is well separated (see [ORSS06]), or to provide $O(\log(k))$-approximation in general [AV07]. The separation-based results of [ORSS06] were improved by [ABS10].

Part I of the Algorithm

In this section, we look only at Part I of our algorithm. Our approximation algorithm defines a clustering $\mathcal{Z}$, where $Z_{r}=\{i:\ \|\hat{A}_{i}-\nu_{r}\|\leq\|\hat{A}_{i}-\nu_{s}\|\textrm{ for every }s\}$. Our goal in this section is to show that $\mathcal{Z}$ is correct on all but a small constant fraction of the points, and furthermore, the $k$-means cost of $\mathcal{Z}$ is no more than $(1+O(1/c))$ times the $k$-means cost of the target clustering.

There exists a matching (given by Fact 1.2) between the target clustering $\mathcal{T}$ and the clustering $\mathcal{Z}=\{Z_{r}\}_{r}$ where $Z_{r}=\{i:\ \|\hat{A}_{i}-\nu_{r}\|\leq\|\hat{A}_{i}-\nu_{s}\|\textrm{ for every }s\}$ that satisfies the following properties:

For every cluster $T_{s_{0}}$ in the target clustering, no more than $O(1/c^{2})|T_{s_{0}}|$ points are misclassified.

For every cluster $Z_{r_{0}}$ in the clustering that the algorithm outputs, we add no more than $O(1/c^{2})|T_{r_{0}}|$ points from other clusters.

At most $O(1/c^{2})|T_{r_{2}}|$ points are misclassified overall, where $T_{r_{2}}$ is the second largest cluster.

Let us denote $T_{s\to r}$ as the set of points $\hat{A}_{i}$ that are assigned to $T_{s}$ in the target clustering, yet are closer to $\nu_{r}$ than to any other $\nu_{r}^{\prime}$. From triangle inequality we have that $\|\hat{A}_{i}-\mu_{s}\|\geq\|\hat{A}_{i}-\nu_{s}\|-\|\mu_{s}-\nu_{s}\|$. We know from Fact 1.2 that $\|\mu_{s}-\nu_{s}\|\leq 6\Delta_{s}$. Also, since $\hat{A_{i}}$ is closer to $\nu_{r}$ than to $\nu_{s}$, the triangle inequality gives that $2\|\hat{A}_{i}-\nu_{s}\|\geq\|\nu_{r}-\nu_{s}|$. So,

Thus, we can look at $\|\hat{A}-C\|_{F}^{2}$, and using Fact 1.1 we immediately have that for every fixed $r^{\prime}$

The proof of the theorem follows from fixing some $r_{0}$ or some $s_{0}$ and deducing:

Observe that for every $r\neq s$ we have that $\Delta_{r}+\Delta_{s}\geq\Delta_{r_{2}}$ (where $r_{2}$ is the cluster with the second largest number of points), so we have that

We now show that the $k$-means cost of $\mathcal{Z}$ is close to the $k$-means cost of $\mathcal{T}$. Observe that the $k$-means cost of $\mathcal{Z}$ is computed w.r.t the best center of each cluster (i.e., $\mu(Z_{r})$), and not w.r.t the centers $\nu_{r}$.

The $k$-means cost of $\mathcal{Z}$ is at most $(1+O(1/c))\|A-C\|_{F}^{2}$.

Given $\mathcal{Z}$, it is clear that the centers that minimize its $k$-means cost are $\mu(Z_{r})=\frac{1}{|Z_{r}|}\sum_{i\in Z_{r}}A_{i}$. Recall that the majority of points in each $Z_{r}$ belong to a unique $T_{r}$, and so, throughout this section, we assume that all points in $Z_{r}$ were assigned to $\mu_{r}$, and not to $\mu(Z_{r})$. (Clearly, this can only increase the cost.) We show that by assigning the points of $Z_{r}$ to $\mu_{r}$, our cost is at most $(1+O(1/c))\|A-C\|_{F}^{2}$, and so Theorem 3.2 follows. In fact, we show something stronger. We show that by assigning all the points in $Z_{r}$ to $\mu_{r}$, each point $A_{i}$ pays no more than $(1+O(1/c))\|A_{i}-C_{i}\|^{2}$. This is clearly true for all the points in $Z_{r}\cap T_{r}$. We show this also holds for the misclassified points.

Because $i\in T_{s\to r}$, it holds that $\|\hat{A}_{i}-\nu_{r}\|\leq\|\hat{A}_{i}-\nu_{s}\|$. Observe that for every $s$ we have that $\|A_{i}-\nu_{s}\|^{2}=\|A_{i}-\hat{A}_{i}\|^{2}+\|\hat{A}_{i}-\nu_{s}\|^{2}$, because $\hat{A}_{i}-\nu_{s}$ is the projection of $A_{i}-\nu_{s}$ onto the subspace spanned by the top $k$-singular vectors of $A$. Therefore, it is also true that $\|A_{i}-\nu_{r}\|\leq\|A_{i}-\nu_{s}\|$. Because of Fact 1.2, we have that $\|\mu_{r}-\nu_{r}\|\leq 6\Delta_{r}$ and $\|\mu_{s}-\nu_{s}\|\leq 6\Delta_{s}$, so we apply the triangle inequality and get

So all we need to do is to lower bound $\|A_{i}-\mu_{s}\|$. As noted, $\|A_{i}-\nu_{s}\|\geq\|\hat{A}_{i}-\nu_{s}\|$. Thus

and we have the bound $\|A_{i}-\mu_{r}\|\leq\left(1+\frac{24}{c}\right)\|A_{i}-\mu_{s}\|$, so $\|A_{i}-\mu_{r}\|^{2}\leq\left(1+\frac{49}{c}\right)\|A_{i}-\mu_{s}\|^{2}$. ∎

One straight-forward application of Theorem 3.2 is for the datasets considered by Ostrovsky et al [ORSS06], where the optimal $k$-means cost is an $\epsilon$-fraction of the optimal $(k-1)$-means cost. Ostrovsky et al proved that for such datasets a variant of the Lloyd method converges to a good solution in polynomial time. Kumar and Kannan have shown that datasets satisfying the ORSS-separation, also have the property that most points satisfy their proximity-condition. Their analysis is not immediate, and gives a $(1+O(\sqrt{k\epsilon}))$-approximation. Here, we provide a “one-line” proof that Part I of Algorithm $\sim$Cluster yields a $(1+O(\sqrt{\epsilon}))$-approximation, for any $k$.

Suppose we have a dataset satisfying the ORSS-separation condition, so any $(k-1)$-partition of the dataset have cost $\geq\frac{1}{\epsilon}\|A-C\|_{F}^{2}$. For any $r$ and any $s\neq r$, by assigning all the points in $T_{r}$ to the center $\mu_{s}$, we get some $(k-1)$-partition whose cost is exactly $\|A-C\|_{F}^{2}+n_{r}\|\mu_{r}-\mu_{s}\|^{2}$, so $\|\mu_{r}-\mu_{s}\|\geq\frac{\sqrt{\frac{1}{\epsilon}-1}}{\sqrt{n_{r}}}\|A-C\|_{F}$. Setting $c=O(1/\sqrt{\epsilon})$, Theorem 3.2 is immediate.

Part II of the Algorithm

In this section, our goal is to show that Part II of our algorithm gives centers that are very close to the target clusters. We should note that from this point on, we assume we are in the non-degenerate case, where $\|A-C\|_{F}^{2}\geq k\|A-C\|^{2}$. Therefore, $\Delta_{r}=\frac{\sqrt{k}}{\sqrt{n_{r}}}\|A-C\|$.

Recall, in Part II we define the sets $S_{r}=\{i:\|\hat{A}_{i}-\nu_{r}\|\leq\frac{1}{3}\|\hat{A}_{i}-\nu_{s}\|,\ \forall s\neq r\}$. Observe, these set do not define a partition of the dataset! There are some points that are not assigned to any $S_{r}$. However, we only use the centers of $S_{r}$. We prove the following theorem.

Denote $S_{r}=\{i:\|\hat{A}_{i}-\nu_{r}\|\leq\frac{1}{3}\|\hat{A}_{i}-\nu_{s}\|,\ \forall s\neq r\}$. Then for every $r$ it holds that $\|\mu(S_{r})-\mu_{r}\|=O(1/c)\ \frac{1}{\sqrt{n_{r}}}\|A-C\|=O(\tfrac{1}{c\sqrt{k}}\Delta_{r})$.

The proof of Theorem 4.1 is an immediate application of Fact 1.3 combined with the following two lemmas, that bound the number of misclassified points. Observe that for every point that belongs to $T_{s}$ yet is assigned to $S_{r}$ (for $s\neq r$) is also assigned to $Z_{r}$ in the clustering $\mathcal{Z}$ discussed in the previous section. Therefore, any misclassified point $i\in T_{s}\cap S_{r}$ satisfies that $\|A_{i}-\mu_{r}\|\leq(1+O(c^{-1}))\|A_{i}-\mu_{s}\|$ as the proof of Theorem 3.2 shows. So all conditions of Fact 1.3 hold.

Assume that for every $r$ we have that $\|\mu_{r}-\nu_{r}\|\leq 6\Delta_{r}$. Then at most $\frac{512}{c^{2}}n_{r}$ points of $T_{r}$ do not belong to $S_{r}$.

Redefine $T_{s\to r}$ as the set $T_{s}\cap S_{r}$. Assume that for every $r$ we have that $\|\mu_{r}-\nu_{r}\|\leq 6\Delta_{r}$. Then for every $r$ and every $s\neq r$ we have that $|T_{s\to r}|=\left(\frac{48^{2}}{c^{4}k^{2}}\right)n_{r}$.

First, we claim that if $i$ is such that $\|\hat{A}_{i}-\mu_{r}\|\leq\frac{c}{8}\Delta_{r}$, then it must be the case that $i\in S_{r}$.

This is a simple consequence of the triangle inequality, bounding $\|\hat{A}_{i}-\nu_{r}\|\leq\|\hat{A}_{i}-\mu_{r}\|+\|\mu_{r}-\nu_{r}\|\leq((c/8)+6)\Delta_{r}$. Yet, for every $s\neq r$, the triangle inequality gives that $\|\hat{A}_{i}-\nu_{s}\|\geq\|\mu_{r}-\mu_{s}\|-\|\hat{A}_{i}-\mu_{r}\|-\|\mu_{s}-\nu_{s}\|\geq(c-\frac{c}{8}-6)(\Delta_{r}+\Delta_{s})$. Assuming $c>48$, we have that $\|\hat{A}_{i}-\nu_{s}\|\geq 3\|\hat{A}_{i}-\nu_{r}\|$.

All that’s left is to show that the number of $i\in T_{r}$ s.t. $\|\hat{A}_{i}-\mu_{r}\|>\frac{c}{8}\Delta_{r}$ is small. This again follows from the Markov inequality: Since $\|\hat{A}-C\|_{F}^{2}\leq 8k\|A-C\|^{2}$, then the number of such points is at most $\frac{8k\|A-C\|^{2}}{(c^{2}/64)k\|A-C\|^{2}}n_{r}$. ∎

We now turn to proving Lemma 4.3. The general outline of the proof of Lemma 4.3 resembles to the outline of the proof of Lemma 4.2. Proposition 4.4 exhibit some property that every point in $T_{s\to r}$ must satisfy, and then we show that only few of the points in $T_{s}$ satisfy this property. Recall that $\hat{\mu_{r}}$ indicates the projection of $\mu_{r}$ onto the subspace spanned by the top $k$-singular vectors of $A$.

Fix $i\in T_{s}$ s.t. $\|\hat{A}_{i}-\hat{\mu}_{s}\|\leq 2\|\hat{A}_{i}-\hat{\mu}_{r}\|$. Then $\|\hat{A}_{i}-{\nu}_{s}\|<3\|\hat{A}_{i}-{\nu}_{r}\|$, so $i\notin S_{r}$.

First, for every $r$ we have that $\|\hat{\mu_{r}}-\nu_{r}\|\leq\|\mu_{r}-\nu_{r}\|\leq 6\Delta_{r}$, as $\hat{\mu_{r}}-\nu_{r}$ is a projection of $\mu_{r}-\nu_{r}$.

Let us fiddle with the triangle inequality, in order to obtain a lower bound on $\|\hat{A}_{i}-\nu_{r}\|$. We have that 3\|\hat{A}_{i}-\hat{\mu}_{r}\|\geq\|\hat{\mu}_{r}-\hat{\mu}_{s}\|\geq\|\mu_{r}-\mu_{s}\|-\bigl{(}\|\mu_{r}-\nu_{r}\|+\|\nu_{r}-\hat{\mu}_{r}\|\bigr{)}-\bigl{(}\|\mu_{s}-\nu_{s}\|+\|\nu_{s}-\hat{\mu}_{s}\|\bigr{)}\geq(c-12)(\Delta_{r}+\Delta_{s}), thus $\|\hat{A}_{i}-\nu_{r}\|\geq\left(\frac{c-12}{3}-6\right)(\Delta_{r}+\Delta_{s})$.

Assume for the sake of contradiction that $\|\hat{A}_{i}-{\nu}_{s}\|\geq 3\|\hat{A}_{i}-{\nu}_{r}\|$, and let us show this yields an upper bound on $\|\hat{A}_{i}-\nu_{r}\|$, which contradicts our lower bound. We have that

It follows that $12(\Delta_{r}+\Delta_{s})\geq\|\hat{A}_{i}-\nu_{r}\|\geq\left(\frac{c-12}{3}-6\right)(\Delta_{r}+\Delta_{s})$. Contradiction ($c>60$). ∎

Proposition 4.4, shows that in order to bound $|T_{s\to r}|$ it suffices to bound the number of points in $T_{s}$ satisfying $\|\hat{A}_{i}-\hat{\mu}_{s}\|\geq 2\|\hat{A}_{i}-\hat{\mu}_{r}\|$. The major tool in providing this bound is the following technical lemma. This lemma is a variation on the work of [KK10], on which we improve on the dependency on $k$ and simplify the proof.

Let $\mathcal{V}$ be the subspace spanned by the following $4$ vectors: $\{\mu_{r},\mu_{s},\zeta_{r},\zeta_{s}\}$. Denote $P_{\cal V}$ as the projection onto $\mathcal{V}$. We denote $v_{i}=P_{\cal V}(A_{i})$, and observe that $P_{\cal V}(\mu_{r})=\mu_{r}$, and the same goes for $\mu_{s}$, $\zeta_{r}$ and $\zeta_{s}$. Observe also that, as a projection, $\|P_{\cal V}(A-C)\|\leq\|A-C\|$ (alternatively, $\|P_{\cal V}\|=1$).

The proof follows from upper- and lower-bounding the term $\|v_{i}-\zeta_{s}\|^{2}-\|v_{i}-\zeta_{r}\|^{2}$. We’ve just shown a lower bound, as we have that

The triangle inequality gives that $\|v_{i}-\zeta_{s}\|\leq\|v_{i}-\mu_{s}\|+\alpha(\Delta_{r}+\Delta_{s})$, and that $\|v_{i}-\zeta_{r}\|\geq\|v_{i}-\mu_{r}\|-\alpha(\Delta_{r}+\Delta_{s})$, so we have the upper bound of

Comparing the upper and the lower bound, we have that for any $i\in X$ the distance $\|v_{i}-\mu_{r}\|\geq\frac{\beta}{4\alpha}\frac{(c-\alpha)^{2}(\Delta_{r}+\Delta_{s})^{2}}{\Delta_{r}+\Delta_{s}}$. As $X\subset T_{s}$, the Markov inequality concludes the proof

Thus, every $i\in T_{s\to r}$ satisfies the conditions of Lemma 4.5 with $\zeta_{r}=\hat{\mu}_{r},\zeta_{s}=\hat{\mu}_{s}$, and $\beta=1/3$. We deduce the $|T_{s\to r}|\leq\alpha^{2}~{}\frac{256\cdot 9}{c^{4}k}\min\{n_{r},n_{s}\}$, where $\alpha$ is the bound s.t. for every $r$, $\|\mu_{r}-\hat{\mu}_{r}\|\leq\alpha\frac{\sqrt{k}}{\sqrt{n_{r}}}\|A-C\|$. Since $\alpha\leq\frac{1}{\sqrt{k}}$, we conclude the proof.

The fact that $\alpha$ is small was proven by Achlioptas and McSherry (Theorem $1$ of [AM05]). Denote $u_{r}$ as the indicator vector of $T_{r}$. Since rank$(C)\leq k$, we get

As an interesting corollary, Theorem 4.1 dictates that for every $r$ we have that $\|\mu_{r}-\theta_{r}\|=O(1/c)\|\mu_{r}-\hat{\mu}_{r}\|$.

Part II of our algorithm returns centers $\theta_{1},\ldots,\theta_{k}$ which are $O(\frac{1}{c\sqrt{n_{r}}})\|A-C\|$ close to the true centers. Suppose we use these centers to cluster the points: $\Theta_{s}=\{i:\ \forall s^{\prime},\ \|A_{i}-\theta_{s}\|\leq\|A_{i}-\theta_{s^{\prime}}\|\}$. It is evident that this clustering correctly classifies the majority of the points. It correctly classifies any point $i\in T_{s}$ with $\|A_{i}-\mu_{r}\|-\|A_{i}-\mu_{s}\|=\Omega(\frac{1}{c\sqrt{n_{r}}})\|A-C\|$ for every $r\neq s$, and the analysis of Theorem 3.1 shows that at most $O(c^{-2})$-fraction of the points do not satisfy this condition. In order to have a direct comparison with the Kumar-Kannan analysis, we now bound the number of misclassified points w.r.t the fraction of points satisfying the Kumar-Kannan proximity condition.

Denote $gap_{r,s}=(\frac{1}{\sqrt{n_{r}}}+\frac{1}{\sqrt{n_{s}}})\|A-C\|$. Call a point $i\in T_{s}$ $\gamma$-good, if for every $r\neq s$ we have that the projection of $A_{i}$ onto the line connecting $\mu_{r}$ and $\mu_{s}$, denoted $\bar{A}_{i}$, satisfies that $\|\bar{A}_{i}-\mu_{r}\|-\|\bar{A}_{i}-\mu_{s}\|\geq\gamma\ gap_{r,s}$; otherwise we say the point is $\gamma$-bad.

If the number of $\gamma$-bad points is $\epsilon n$, then (a) the clustering $\{\Theta_{1},\ldots,\Theta_{k}\}$ misclassifies no more than $\left(\epsilon+\frac{O(1)}{\gamma^{2}c^{4}}\right)n$ points, and (b) $\epsilon<O\left((c-\tfrac{\gamma}{\sqrt{k}})^{-2}\right)$, assuming $\gamma<c{\sqrt{k}}$.

Clearly, all $\epsilon n$ bad points may be misclassified. In addition, for every $r$ and $s\neq r$, Lemma 4.5 (setting $\zeta_{r}=\theta_{r}$, $\zeta_{s}=\theta_{s}$, $\alpha=1/c\sqrt{k}$ and $\beta=\Omega(\gamma/(c\sqrt{k}))$) proves that no more than $O(\gamma^{-2}c^{-2}k^{-1})n_{s}$ good points can be misclassified. Summing $\sum_{s\neq r}\tfrac{1}{k}n_{s}\leq n$, we conclude (a).

The proof of (b) is similar to the proof of Theorem 3.1. We look at the $k$-means cost of $\|\hat{A}-C\|_{F}^{2}$. We show that all $\gamma$-bad points contribute a large amount to this cost.

Take $A_{i}$ to be a $\gamma$-bad point from $T_{s}$. Projecting it down to the line connecting $\mu_{r}$ and $\mu_{s}$, we denote the projection as $\bar{A}_{i}$. Clearly, $\|\mu_{r}-\mu_{s}\|=\|\mu_{r}-\bar{A}_{i}\|+\|\bar{A}_{i}-\mu_{s}\|\geq c\sqrt{k}gap_{r,s}$ whereas $\|\mu_{r}-\bar{A}_{i}\|-\|\bar{A}_{i}-\mu_{s}\|\leq\gamma gap_{r,s}$. It follows that $\|\hat{A}_{i}-\mu_{s}\|\geq\|\bar{A}_{i}-\mu_{s}\|\geq\tfrac{1}{2}(c\sqrt{k}-\gamma)gap_{r,s}\geq\frac{c\sqrt{k}-\gamma}{2\sqrt{n_{s}}}\|A-C\|$. Again, the Markov inequality gives that

so from each cluster, only a fraction of $32\left(\frac{\sqrt{k}}{c\sqrt{k}-\gamma}\right)^{2}$ of the points can be bad. ∎

Observe that Corollary 4.7 allows for multiple scaled versions of the proximity condition, based on the magnitude of $\gamma$. In particular, setting $\gamma=1$ we get a proximity condition whose bound is independent of $k$, and still our clustering misclassifies only a small fraction of the points – at most $O(c^{-2})$ fraction of all points might be misclassified because they are $1$-bad, and no more than a $O(c^{-4})$-fraction of $1$-good points may be misclassified. In addition, if there are no $1$-bad points we show the following theorem. The proof (omitted) merely follows the Kumar-Kannan proof, plugging in the better bounds, provided by Lemma 4.5.

Assume all data points are $1$-good. That is, for every point $A_{i}$ that belongs to the target cluster $T_{c(i)}$ and every $s\neq c(i)$, by projecting $A_{i}$ onto the line connecting $\mu_{c(i)}$ with $\mu_{s}$ we have that the projected point $\bar{A}_{i}$ satisfies $\|\bar{A}_{i}-\mu_{c(i)}\|-\|\bar{A}_{i}-\mu_{s}\|=\Omega\left((\frac{1}{\sqrt{n_{c(i)}}}+\frac{1}{\sqrt{n_{s}}})\right)\|A-C\|$, whereas $\|\mu_{c(i)}-\mu_{s}\|=\Omega\left(\sqrt{k}(\frac{1}{\sqrt{n_{c(i)}}}+\frac{1}{\sqrt{n_{s}}})\right)\|A-C\|$. Then the Lloyd method, starting with $\theta_{1},\ldots,\theta_{k}$, converges to the true centers.

Applications

For a mixture of $k$ Gaussians, we quote the suitable results without proof, as the proof is identical to the proof in [KK10]. We are given a mixture of $k$ Gaussians, $F_{1},\ldots,F_{k}$, where the standard deviation of each distribution in any direction is at most $\sigma_{r}$, and the weight of each distribution is $w_{r}$. We denote $\sigma_{\max}=\max_{r}\{\sigma_{r}\}$ and $w_{\min}=\min_{r}\{w_{r}\}$.

Suppose we are given a set of $n\gg\frac{d}{w_{\min}}$ samples from a mixture of $k$ Gaussians, such that for every $r\neq s$ it holds that $\|\mu_{r}-\mu_{s}\|\geq c\sigma_{\max}\sqrt{\frac{k}{w_{\min}}}~{}\emph{poly}\log\left(\frac{d}{w_{\min}}\right)$. Then w.h.p. these points satisfy the proximity condition.

Suppose we are given a set of $n\gg\frac{d}{w_{\min}}$ samples from a mixture of $k$ Gaussians, such that for every $r\neq s$ it holds that

Then there exists an algorithm that w.h.p. correctly classifies all points.

Therefore, if for any $r$ and $r^{\prime}$, both $\sigma_{r}\approx\sigma_{r^{\prime}}$ and $w_{r}\approx w_{r^{\prime}}$, then both [AM05] and Theorem 5.2 give roughly the same bound. If for any $r$ and $r^{\prime}$ we have that $\sigma_{r}\approx\sigma_{r^{\prime}}$, yet $w_{\min}\ll\frac{1}{k}$, then Theorem 5.2 provides a better bound. If for any $r$ and $r^{\prime}$ we have that $w_{r}\approx w_{r^{\prime}}$, yet the directional standard deviations of the distributions vary, then the bound of [AM05], in which the distance between any two cluster centers depends only the parameters of these two distributions, is the better bound. If both the standard deviations and the weights vary significantly between the different distributions, then better bound is determined on a case by case basis.

McSherry’s Planted Partition Model.

In the Planted Partition Model [McS01, AK94, AKS98] our instance is a random $n$-vertex graph generated by using an implicit partition of the $n$ points into $k$ clusters. There exists an unknown $k\times k$ matrix of probabilities $P$, and for every pair of vertices $u,v$ there exists an edge connecting $u$ and $v$ w.p. $P_{rs}$ (assuming $u$ belongs to cluster $r$ and $v$ to cluster $s$). The goal here is to recover the partition of the points (thus – recover $P$). Viewing this graph as a $n\times n$ matrix, each row is taken from a special distribution $F_{r}$ over $\{0,1\}^{n}$ – where each coordinate $j$ is an independent Bernoulli r.v. with mean $P_{r,C(j)}$, denoting $C(j)$ as the cluster $j$ belongs to. Thus, the mean of this distribution, $\mu_{r}$, is a vector with its $j$-coordinate set to $P_{r,C(j)}$. Denote $w_{\min}=\min_{r}\{\frac{n_{r}}{n}\}$ and $\sigma_{\max}=\max_{r,s}\sqrt{P_{rs}}$. The result of [McS01] is that if for every $r\neq s$

then it is possible to retrieve the partition of the vertices w.p. at least $1-\delta$.

Kumar and Kannan were not able to match the distance bounds of McSherry, and required centers to be $\sqrt{k}$ factor greater then the bound of (2). Here we match the bound of McSherry exactly. Following the proof in Kumar-Kannan (with few changes), we prove:

Assuming that $\sigma_{\max}\geq\frac{3\log(n)}{n}$ and that the planted partition model satisfies equation 2 for every $r\neq s$, then w.p. at least $1-\delta$, every point satisfies the proximity condition.

We follow the proof of Kumar-Kannan, making the suitable changes. McSherry (Theorem 10 of [McS01]) showed that w.h.p. $\|A-C\|\leq 4\sigma_{\max}\sqrt{n}$. So our goal is to show that, w.h.p., all points are $\sqrt{k}$-good. I.e., denoting $u$ as a unit-length vector connecting $\mu_{r}$ and $\mu_{s}$, we show that w.h.p. that for every $i\in T_{r}$ we have

Observe $u=\frac{\mu_{s}-\mu_{r}}{\|\mu_{s}-\mu_{r}\|}$, and due to the special structure of the means in this model, we have that $(\mu_{r}-\mu_{s})_{j}=P_{rt}-P_{st}$ where $j\in T_{t}$. It follows that

Observe, $A_{ij}$ are i.i.d -$1$ random variables with mean $P_{rt}$, so we expect their sum to deviate from its expectation by no more than a few standard deviations. Indeed, Kumar and Kannan prove that w.h.p. it holds that for every $t$ we have

where $B$ is some sufficiently large constant. This allows us to deduce that

where the last inequality is simply the power-mean inequality. ∎

An Open Problem

References

Appendix A Some Basic Lemmas

\|\hat{A}-C\|_{F}^{2}\leq 8\min\{k\|A-C\|^{2},\|A-C\|_{F}^{2}\}\ \ \biggl{(}=8n_{r}\Delta_{r}^{2}\ \textrm{ for every }r\biggr{)}.

where the first inequality holds because rank$(\hat{A}-C)\leq 2k$, and the last inequality follows from the fact that $\hat{A}=\arg\min_{N:\textrm{rank}(N)=k}\{\|A-N\|\}$. For the same reason, $\|\hat{A}-C\|_{F}\leq\|A-\hat{A}\|_{F}+\|A-C\|_{F}\leq 2\|A-C\|_{F}$. ∎

For every $\mu_{r}$ there exists a center $\nu_{s}$ s.t. $\|\mu_{r}-\nu_{s}\|\leq 6\Delta_{r}$, so we can match each $\mu_{r}$ to a unique $\nu_{r}$.

Observe that by taking $\hat{A}-\hat{C}$, we project $A-C$ to a $k$-dimensional subspace, so we have that $\|\hat{A}-\hat{C}\|_{F}^{2}\leq k\|\hat{A}-\hat{C}\|^{2}\leq k\|A-C\|^{2}$. Similarly, $\|\hat{A}-\hat{C}\|_{F}^{2}\leq\|A-C\|_{F}^{2}$.

Assume for the sake of contradiction that $\exists r$ s.t. $\|\mu_{r}-\nu_{s}\|>6\Delta_{r}$ for all $s$. Since $\|\hat{A}-\hat{C}\|_{F}^{2}\leq n_{r}\Delta_{r}^{2}$, then our $10$-approximation algorithm yields a clustering of cost $\leq 10n_{r}\Delta_{r}^{2}$. In contrast, as each $\hat{A}_{i}$ is assigned to some $\nu_{c(i)}$, the contribution of only the points in $T_{r}$ to the $k$-means cost of the clustering is more than

where the first inequality follows from the fact that $(a-b)^{2}\geq\frac{1}{2}a^{2}-b^{2}$. ∎

Now, in order to prove Fact 1.3 (also cited below as Fact A.4), we need the following Fact.

Fix any cluster $T_{r}$ and a subset $X\subset T_{r}$. Then

Let $u_{X}$ be the indicator vector of $X$. Then

and the fact that $|X|\ \|\mu(X)-\mu_{r}\|=|T_{r}\setminus X|\ \|\mu(T_{r}\setminus X)-\mu_{r}\|$ is simply because $\mu_{r}=\frac{|X|}{|T_{r}|}\mu(X)+\frac{|T_{r}\setminus X|}{|T_{r}|}\mu(T_{r}\setminus X)$. ∎

Fix a target cluster $T_{r}$ and let $S_{r}$ be a set of points created by removing $\rho_{out}n_{r}$ points from $T_{r}$ and adding $\rho_{in}(s)n_{r}$ points from each cluster $s\neq r$, s.t. every added point $x$ satisfies $\|x-\mu_{s}\|\geq\tfrac{2}{3}\|x-\mu_{r}\|$. Assume $\rho_{out}<\tfrac{1}{4}$ and $\rho_{in}\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{s\neq r}\rho_{in}(s)<\tfrac{1}{4}$. Then