Clustering with Spectral Norm and the k-means Algorithm

Introduction

Clustering is in general a hard problem. But, there has been a lot of research (see Section 3 for references) on proving that if we have data points generated by a mixture of $k$ probability distributions, then one can cluster the data points into the $k$ clusters, one corresponding to each component, provided the means of the different components are well-separated. There are different notions of well-separated, but mainly, the (best known) results can be qualitatively stated as:

These results generally make heavy use of the generative model and particular properties of the distributions (Indeed, many of them specialize to Gaussians or independent Bernoulli trials). In this paper, we make no assumptions on the generative model of the data. We are still able to derive essentially the same result (loosely stated for now as):

“If the projection of any data point onto the line joining its cluster center to any other cluster center is $\Omega(k)$ times standard deviations closer to its own center than the other center (we call this the “proximity condition”), then we can cluster correctly in polynomial time.”

First, if the $n$ points to be clustered form the rows of an $n\times d$ matrix $A$ and $C$ is the corresponding matrix of cluster centers (so each row of $C$ is one of $k$ vectors, namely the centers of $k$ clusters) then note that the maximum directional variance (no probabilities here, the variance is just the average squared distance from the center) of the data in any direction is just

where $||A-C||$ is the spectral norm. So, spectral norm scaled by $1/\sqrt{n}$ will play the role of standard deviation in the above assertion. To our knowledge, this is the first result proving that clustering can be done in polynomial time in a general situation with only deterministic assumptions. It settles an open question raised in [KV09].

We will show that in the generative models studied, our proximity condition is satisfied and so we are able to derive all known results for generative models as corollaries of our theorem (with one qualification: whereas our separation is in terms of the whole data variance, often, in the case of Gaussians, one can make do with separations depending only on individual densities’ variances – see Section 3.)

Besides Gaussians, the planted partition model (defined later) has also been studied; both these distributions have very “thin tails” and a lot of independence, so one can appeal to concentration results. In section 6.3, we give a clustering algorithm for a mixture of general densities for which we only assume bounds on the variance (and no further concentration). Based on our algorithm, we show how to classify all but an $\varepsilon$ fraction of points in this model. Section 3 has references to recent work dealing with distributions which may not even have variance, but these results are only for the special class of product densities, with additional constraints.

One crucial technical result we prove (Theorem 5.5) may be of independent interest. It shows that the good old $k-$means algorithm [Llo82] converges to the “true centers” even in the presence of spurious points provided the initial (estimated) centers are close enough to the corresponding actual centers and all but an $\varepsilon$ fraction of the points satisfy the proximity condition. Convergence (or lack of it) of the $k-$means algorithm is again well-studied ([ORSS06, AV06, Das03, HPS05]). The result of [ORSS06] (one of the few to formulate sufficient conditions for the $k-$means algorithm to provably work) assumes the condition that the optimal clustering with $k$ centers is substantially better than that with fewer centers and shows that one iteration of $k-$means yields a near-optimal solution. We show in section 6.4 that their condition implies proximity for all but an $\varepsilon$ fraction of the points. This allows us to prove that our algorithm, which is again based on the $k-$means algorithm, gives a PTAS.

The proof of Theorem 5.5 is based on Theorem 5.4 which shows that if current centers are close to the true centers, then misclassified points (whose nearest current center is not the one closest to the true center) are far away from true centers and so there cannot be too many of them. This is based on a clean geometric argument shown pictorially in Figure 2. Our main theorem in addition allows for an $\varepsilon$ fraction of “spurious” points which do not satisfy the proximity condition. Such errors have often proved difficult to account for.

As indicated, all results on generative models assume a lower bound on the inter-center separation in terms of the spectral norm. In section 7, we describe a construction (when data is from a generative model – a mixture of distributions) which boosts the ratio of inter-center separation to spectral norm. The construction is the following: we pick two sets of samples $A_{1},A_{2},\ldots A_{n}$ and $B_{1},B_{2},\ldots B_{n}$ independently from the mixture. We define new points $X_{1},X_{2},\ldots X_{n}$, where $X_{i}$ is defined as $(A_{i}^{\prime}\cdot B_{1}^{\prime},A_{i}^{\prime}\cdot B_{2}^{\prime},\ldots A_{i}^{\prime}\cdot B_{n}^{\prime})$, where ′ denotes that we have subtracted the mean (of the mixture.) Using this, we are able to reduce the dependence of inter-center separation on the minimum weight of a component in the mixture that all models generally need. This technique of boosting is likely to have other applications.

Preliminaries and the Main Theorem

For a matrix $A$, we shall use $||A||$ to denote its spectral norm. For a vector $v$, we use $|v|$ to denote its length. We are given $n$ points in $\Re^{d}$ which are divided into $k$ clusters – ${T_{1}},{T_{2}},\ldots,{T_{k}}$. Let $\mu_{r}$ denote the mean of cluster ${T_{r}}$ and $n_{r}$ denote $|T_{r}|$. Let $A$ be the $n\times d$ matrix with rows corresponding to the points. Let $C$ be the $n\times d$ matrix where $C_{i}=\mu_{r}$, for all $i\in{T_{r}}$. We shall use $A_{i}$ to denote the $i^{th}$ row of $A$. Let

We say a point $A_{i}\in T_{r}$ satisfies the proximity condition if for any $s\not=r$, the projection of $A_{i}$ onto the $\mu_{r}$ to $\mu_{s}$ line is at least $\Delta_{rs}$ closer to $\mu_{r}$ than to $\mu_{s}$. We let $G$ (for good) be the set of points satisfying the proximity condition.

Note that the proximity condition implies that the distance between $\mu_{r}$ and $\mu_{s}$ must be at least $\Delta_{rs}$. We are now ready to state the theorem.

If $|G|\geq(1-\varepsilon)\cdot n$, then we can correctly classify all but $O(k^{2}\varepsilon\cdot n)$ points in polynomial time. In particular, if $\varepsilon=0$, all points are classified correctly.

Often, when applying this theorem to learning a mixture of distributions, $A$ will correspond to a set of $n$ independent samples from the mixture. We will denote the corresponding distributions by $F_{1},\ldots,F_{k}$, and their relative weights by $w_{1},\ldots,w_{k}$. Often, $\sigma_{r}$ will denote the maximum variance along any direction of the distribution $F_{r}$, and $\sigma$ will denote $\max_{r}\sigma_{r}$. We denote the minimum mixing weight of a distribution as $w_{\min}$.

Previous Work

Learning mixture of distributions is one of the central problems in machine learning. There is vast amount of literature on learning mixture of Gaussian distributions. One of the most popular methods for this is the well known EM algorithm which maximizes the log likelihood function [DLR77]. However, there are few results which demonstrate that it converges to the optima solution. Dasgupta [Das99] introduced the problem of learning distributions under suitable separation conditions, i.e., we assume that the distance between the means of the distributions in the mixture is large, and the goal is to recover the original clustering of points (perhaps with some error).

We first summarize known results for learning mixtures of Gaussian distributions under separation conditions. We ignore logarithmic factors in separation condition. We also ignore the minimum number of samples required by the various algorithms – they are often bounded by a polynomial in the dimension and the mixing weights. Let $\sigma_{r}$ be the maximum variance of the Gaussian $F_{r}$ in any direction. Dasgupta [Das99] gave an algorithm based on random projection to learn mixture of Gaussians provided mixing weights of all distributions are about the same, and $|\mu_{i}-\mu_{j}|$ is $\Omega((\sigma_{i}+\sigma_{j})\cdot\sqrt{n}).$ Dasgupta and Schulman [DS07] gave an EM based algorithm provided $|\mu_{i}-\mu_{j}|$ is $\Omega((\sigma_{i}+\sigma_{j})\cdot n^{\frac{1}{4}}).$ Arora and Kannan [AK01] also gave a learning algorithm with similar separation conditions. Vempala and Wang [VW04] were the first to demonstrate the effectiveness of spectral techniques. For spherical Gaussians, their algorithm worked with a much weaker separation condition of $\Omega((\sigma_{i}+\sigma_{j})\cdot k^{\frac{1}{4}})$ between $\mu_{i}$ and $\mu_{j}$. Achlioptas and McSherry [AM05] extended this to arbitrary Gaussians with separation between $\mu_{i}$ and $\mu_{j}$ being at least ${{\widetilde{\Omega}}\left(\left(k+\frac{1}{\sqrt{\min(w_{i},w_{j}})}\right)\cdot(\sigma_{i}+\sigma_{j})\right)}.$ Kannan et. al. [KSV08] also gave an algorithm for arbitrary Gaussians with the corresponding separation being $\Omega\left(\frac{k^{\frac{3}{2}}}{w_{\min}^{2}}\cdot(\sigma_{i}+\sigma_{j})\right)$. Recently, Brubaker and Vempala [BV08] gave a learning algorithm where the separation only depends on the variance perpendicular to a hyperplane separating two Gaussians (the so called “parallel pancakes problem”).

Much less is known about learning mixtures of heavy tailed distributions. Most of the known results assume that each distribution is a product distribution, i.e., projection along co-ordinate axes are independent. Often, they also assume some slope condition on the line joining any two means. These slope conditions typically say that the unit vector along such lines does not lie almost entirely along very few coordinates. Such a condition is necessay because if the only difference between two distributions were a single coordinate, then one would require much stronger separation conditions. Dasgupta et. al. [DHKS05] considered the problem of learning product distributions of heavy tailed distributions when each component distribution satisfied the following mild condition : $P[|X-\mu|\geq\alpha R]\leq\frac{1}{2\alpha}$. Here $R$ is the half-radius of the distribution (these distributions can have unbounded variance). Their algorithm could classify at least $(1-\varepsilon)$ fraction of the points provided the distance between any two means is at least $\Omega\left(\frac{\sigma\cdot k^{\frac{5}{2}}}{\varepsilon^{2}}\right)$. Here $R$ is the maximum half-radius of the distributions along any coordinate. Under even milder assumptions on the distributions and a slope condition, they could correctly classify all but $\varepsilon$ fraction of the points provided the corresponding separation was $\Omega\left(\sigma\cdot\sqrt{\frac{k}{\varepsilon}}\right)$. Their algorithm, however, requires exponential (in $d$ and $k$) amount of time. This problem was resolved by Chaudhuri and Rao [CR08]. Dasgupta et. al. [DHKM07] considered the problem of classifying samples from a mixture of arbitrary distributions with bounded variance in any direction. They showed that if the separation between the means is $\Omega\left(\sigma k\right)$ and a suitable slope condition holds, then all the samples can be correctly classified. Their paper also gives a general method for bounding the spectral norm of a matrix when the rows are independent (and some additional conditions hold). We will mention this condition formally in Section 6 and make heavy use of it.

Finally, we discuss the planted partition model [McS01]. In this model, an instance consists of a set of $n$ points, and there is an implicit partition of these $n$ points into $k$ groups. Further, there is an (unknown) $k\times k$ matrix of prababilities $P$. We are given a graph $G$ on these $n$ points, where an edge between two vertices from groups $i$ and $j$ is present with probability $P_{ij}$. The goal is to recover the actual partition of the points (and hence, an approximation to the matrix $P$ as well). We can think of this as a special case of learning mixture of $k$ distributions, where the distribution $F_{r}$ corresponding to the $r^{th}$ part is as follows : $F_{r}$ is a distribution over $\{0,1\}^{n}$, one coordinate corresponding to each vertex. The coordinate corresponding to vertex $u$ is set to 1 with probability $P_{ij}$, where $j$ denotes the group to which $u$ belongs. Note that the mean of $F_{r}$, $\mu_{r}$, is equal to the vector $(P_{r\psi(u)})_{u\in V}$, where $\psi(u)$ denotes the group to which the vertex $u$ belongs. McSherry[McS01] showed that if the following separation condition is satisfied, then one can recover the actual partition of the vertex set with probability at least $1-\delta$ – for all $r,s$, $r\neq s$

where $c$ is a large constant, $w_{\min}$ is such that every group has size at least $w_{\min}\cdot n$, and $\sigma^{2}$ denotes $\max_{i,j}P_{ij}$.

There is a rich body of work on the $k$-means problem and heuristic algorithms for this problem (see for example [KSS10, ORSS06] and references therein). One of the most widely used algorithms for this problem was given by Lloyd [Llo82]. In this algorithm, we start with an arbitrary set of $k$ candidate centers. Each point is assigned to the closest candidate center – this clusters the points into $k$ clusters. For each cluster, we update the candidate center to the mean of the points in the cluster. This gives a new set of $k$ candidate centers. This process is repeated till we get a local optimum. This algorithm may take superpolynomial time to converge [AV06]. However, there is a growing body of work on proving that this algorithm gives a good clustering in polynomial time if the initial choice of centers is good [AV07, ADK09, ORSS06]. Ostrovsky et. al. [ORSS06] showed that a modification of the Lloyd’s algorithm gives a PTAS for the $k$-means problem if there is a sufficiently large separation between the means. Our result also fits in this general theme – the $k$-means algorithm on a choice of centers obtained from a simple spectral algorithm classifies the point correctly.

Our Contributions

Our main contribution is to show that a set of points satisfying a deterministic proximity condition (based on spectral norm) can be correctly classified (Theorem 2.2). The algorithm is described in Figure 1. It has two main steps – first find an initial set of centers based on SVD, and then run the standard $k$-means algorithm with these initial centers as seeds. In Section 5, we show that after each iteration of the $k$-means algorithm, the set of centers come exponentially close to the true centers. Although both steps of our algorithm – SVD and the $k$-means algorithm – have been well studied, ours is the first result which shows that combining the two leads to a provably good algorithm. In Section 6, we give several applications of Theorem 2.2. We have the following results for learning mixture of distriutions (we ignore poly-logarithmic factors in the discussion below) :

Arbitrary Gaussian Distributions with separation $\Omega\left(\frac{\sigma k}{\sqrt{w_{\min}}}\right)$ : as mentioned above, this matches known results [AM05, KSV08] except for the fact that the separation condition between two distributions depends on the maximum standard deviation (as compared to standard deviations of these distributions only).

Planted distribution model with separation $\Omega\left(\frac{k\sigma}{\sqrt{w_{\min}}}\right)$ : this matches the result of McSherry [McS01] except for a $\sqrt{k}$ factor which we can also remove with a more careful analysis.

Distributions with bounded variance along any direction : we can classify all but an $\varepsilon$ fraction of points if the separation between means is at least $\Omega\left(\frac{k\sigma}{\sqrt{\varepsilon}}\right)$. Although results are known for classifying (all but a small fraction) points from mixtures of distributions with unbounded variance [DHKS05, CR08], such results work for product distributions only.

PTAS using the $k$-means algorithm : We show that the separation condition of Ostrovsky et. al. [ORSS06] is stronger than the proximity condition. Using this fact, we are also able to give a PTAS based on the $k$-means algorithm.

Further, ours is the first algorithm which applies to all of the above settings. In Section 7, we give a general technique for working with weaker separation conditions (for learning mixture of distributions). Under certain technical conditions described in Section 7, we give a construction which increases the spectral norm of $A-C$ at a much faster rate than the increase in inter-mean distance as we increase the number of samples. As applications of this technique, we have the following results :

Arbitrary Gaussians with separation $\Omega\left(\sigma k\cdot\log\frac{d}{w_{\min}}\right)$ : this is the first result for arbitrary Gaussians where the separation depends only logarithmically on the minimum mixture weight.

Power-law distributions with sufficiently large (but constant) exponent $\gamma$ (defined in equation (13)) : We prove that we can learn all but $\varepsilon$ fraction of samples provided the separation between means is $\Omega\left(\sigma k\cdot\left(\log\frac{d}{w_{\min}}+\frac{1}{\varepsilon^{\frac{1}{\gamma}}}\right)\right)$. For large values of $\gamma$, it significantly reduces the dependence on $\varepsilon$.

We expect this technique to have more applications.

Proof of Theorem 2.2

Our algorithm for correctly classifying the points will run in several iterations. At the beginning of each iteration, it will have a set of $k$ candidate points. By a Lloyd like step, it will replace these points by another set of $k$ points. This process will go on for polynomial number of steps.

The iterative procedure is described in Figure 1. In the first step, we can use any constant factor approximation algorithm for the $k$-means problem. Note that the algorithm is same as Lloyd’s algorithm, but we start with a special set of initial points as described in the algorithm. We now prove that after the first step (the base case), the estimated centers are close to the actual ones – this case follows from [KV09], but we prove it below for sake of completeness.

(Base Case) After the first step of the algorithm above,

Proof. Suppose, for sake of contradiction, that there exists an $r$ such that all the centers $\nu_{1},\ldots,\nu_{k}$ are at least $\frac{20\sqrt{k}\cdot||A-C||}{\sqrt{n_{r}}}$ distance away from $\mu_{r}$. Consider the points in ${T_{r}}$. Suppose $A_{i}\in{T_{r}}$ is assigned to the center $\nu_{c(i)}$ in this solution. The assignment cost for these points in this optimal $k$-means solution is

where inequality (2) follows from the fact that for any two numbers $a,b$, $(a-b)^{2}\geq\frac{a^{2}}{2}-b^{2}$; and inequality (3) follows from the fact that $||{\hat{A}}-C||_{F}^{2}\leq 5k\cdot||A-C||^{2}.$ But this is a contradiction, because one feasible solution to the $k$-means problem is to assign points in ${\hat{A}}_{i},i\in{T_{s}}$ to $\mu_{s}$ for $s=1,\ldots,k$ – the cost of this solution is $||{\hat{A}}-C||_{F}^{2}\leq 5k||A-C||^{2}.$

Observe that the lemma above implies that there is a unique center $\nu_{r}$ associated with each $\mu_{r}$. We now prove a useful lemma which states that removing small number of points from a cluster ${T_{r}}$ can move the mean of the remaining points by only a small distance.

Let $X$ be a subset of ${T_{r}}$. Let $m(X)$ denote the mean of the points in $X$. Then

Proof. Let $u$ be unit vector along $m(X)-\mu_{r}$. Now,

But, $|(A-C)\cdot u|\leq||A-C||$. This proves the lemma.

Let $Y\subseteq{T_{s}}$ such that $|{T_{s}}-Y|\leq\delta\cdot n_{s}$, where $\delta<\frac{1}{2}$. Let $m(Y)$ denote the mean of the points in $Y$. Then

Proof. Let $X$ denote ${T_{s}}-Y$. We know that $\mu_{s}\cdot|{T_{s}}|=|X|\cdot m(X)+|Y|\cdot m(Y).$ So we get

where the inequality above follows from Lemma 5.2. The result now follows because $|Y|\geq\frac{n_{s}}{2}.$

Now we show that if the estimated centers are close to the actual centers, then one iteration of the second step in the algorithm will reduce this separation by at least half.

$\nu_{1},\nu_{2},\ldots\nu_{k}$ denote the current centers at the beginning of an iteration in the second step of the algorithm, where $\nu_{r}$ is the current center closest to $\mu_{r}$.

$S_{r}$ denotes the set of points $A_{i}$ for which the closest current center is $\nu_{r}$.

$\eta_{r}$ denotes the mean of points in $S_{r}$; so $\eta_{r}$ are the new centers. Let $\delta_{r}=|\mu_{r}-\nu_{r}|$.

The theorem below shows that the set of misclassified points (which really belong to $T_{r}$, but have $\nu_{s},s\neq r$, as the closest current center) are not too many in number. The proof first shows that any misclassified point must be far away from $\mu_{r}$ and since the sum of squared distances from $\mu_{r}$ for all points in $T_{r}$ is bounded, there cannot be too many.

Assume that $\delta_{r}+\delta_{s}\leq\Delta_{rs}/16$ for all $r\not=s$. Then,

Further, for any $W\subseteq T_{r}\cap S_{s}$,

Proof. Let $\bar{v}$ denote the projection of vector $v$ to the affine space $V$ spanned by $\mu_{1},\ldots\mu_{k},\nu_{1},\ldots,\nu_{k}$ and $\eta_{1},\eta_{2},\ldots\eta_{k}$. Assume $A_{i}\in T_{r}\cap S_{s}\cap G$. Splitting $\bar{A}_{i}$ into its projection along the line $\mu_{r}$ to $\mu_{s}$ and the component orthogonal to it, we can write

where $u$ is orthogonal to $\mu_{r}-\mu_{s}$. Since $\bar{A}_{i}$ is closer to $\nu_{s}$ than to $\nu_{r}$, we have

We have $u\cdot(\nu_{s}-\nu_{r})=u\cdot((\nu_{s}-\mu_{s})-(\nu_{r}-\mu_{r}))$ since $u$ is orthogonal to $\mu_{r}-\mu_{s}$. The last quantity is at most $|u|\delta$, where $\delta=\delta_{r}+\delta_{s}$. Substituting this we get

where the last inequality follows from the fact that $\lambda\geq\frac{\Delta_{rs}}{2|\mu_{r}-\mu_{s}|}$ (proximity condition) and the assumption that $\delta\leq\Delta_{rs}/16$. Therefore, we have

If we take a basis $u_{1},u_{2},\ldots u_{p}$ of $V$, we see that $\sum_{i\in T_{r}}|\bar{A}_{i}-C_{i}|^{2}=\sum_{t=1}^{p}\sum_{i\in T_{r}}|(\bar{A}_{i}-C_{i})\cdot u_{t}|^{2}=\sum_{t=1}^{p}||A-C||^{2}\leq 3k||A-C||^{2}$, which proves the first statement of the theorem.

For the second statement, we can write $m(W)$ as

where, $u$ is orthogonal to $\mu_{r}-\mu_{s}$. Since $m(W)$ is the average of points in $S_{s}$, we get (arguing as for (6)):

If $\lambda\leq 1/4$, then clearly, $|m(W)-\mu_{s}|\leq 4|m(W)-\mu_{r}|$. If $\lambda>1/4$, then we have $|u|\geq\frac{\lambda}{10\delta}|\mu_{r}-\mu_{s}|^{2}\geq\frac{1}{2}\cdot\left(\lambda+\frac{1}{2}\right)\cdot|\mu_{r}-\mu_{s}|$ because $\frac{|\mu_{r}-\mu_{s}|}{\delta}\geq 16$. This again yields $|m(W)-\mu_{s}|\leq 4|u|\leq 4|m(W)-\mu_{r}|$. Now, by Lemma 5.2, we have $|m(W)-\mu_{r}|\leq\frac{||A-C||}{\sqrt{|W|}}$, so the second statement in the theorem.

We are now ready to prove the main theorem of this section which will directly imply Theorem 2.2. This shows that $k-$means converges if the starting centers are close enough to the corresponding true centers. To gain intuition, it is best to look at the case $\varepsilon=0$, when all points satisfy the proximity condition. Then the theorem says that if $|\nu_{s}-\mu_{s}|\leq\frac{\gamma||A-C||}{\sqrt{n_{s}}}$ for all $s$, then $|\eta_{s}-\mu_{s}|\leq\frac{\gamma||A-C||}{2\sqrt{n_{s}}}$, thus halving the upper bound of the distance to $\mu_{s}$ in each iteration.

for all $s$ and a parameter $\gamma\leq ck/50$, then

Proof. Let $n_{rs},\mu_{rs}$ denote the number and mean respectively of $T_{r}\cap S_{s}\cap G$ and $n^{\prime}_{rs},\mu^{\prime}_{rs}$ of $(T_{r}\setminus G)\cap S_{s}$. Similarly, define $n_{ss}$ and $\mu_{ss}$ as the size and mean of the points in ${T_{s}}\cap S_{s}$. We get

where the first one is from Corollary 5.3 (it is easy to check from the first statement of Theorem 5.4 that $n_{ss}\geq n_{s}/2$) and the last two are from the second statement in Theorem 5.4.

Now using the fact that length is a convex function, we have

since $|S_{s}|-n_{ss}=\sum_{r\neq s}n_{rs}+\sum_{s}n_{rs}^{\prime}$. Let us look at each of the terms above. Note that $n_{rs}\leq\frac{24ck||A-C||^{2}\max(\delta_{r},\delta_{s})^{2}}{\Delta_{rs}^{2}|\mu_{r}-\mu_{s}|^{2}}$ (using Theorem 5.4). So

Also, note that $\sum_{r}n_{rs}^{\prime}\leq\varepsilon n$. So we get $\sum_{r}\frac{\sqrt{n_{rs}^{\prime}}}{n_{s}}\leq\frac{\sqrt{k\varepsilon n}}{n_{s}}.$ Assuming $c$ to be large enough constant proves the theorem.

Now we can easily finish the proof of Theorem 2.2. Observe that after the base case in the algorithm, the statement of Theorem 5.5 holds with $\gamma=20\sqrt{k}$. So after enough number of iterations of the second step in our algorithm, $\gamma$ will become very small and so we will get

for all $s$. Now substituting this is Theorem 5.4, we get

Summing over all pairs $r,s$ implies Theorem 2.2.

Applications

We now give applications of Theorem 2.2 to various settings. One of the main technical steps here would be to bound the spectral norm of a random $n\times d$ matrix $Y$ whose rows are chosen independently. We use the following result from [DHKM07]. Let $D$ denote the matrix $E[Y^{T}Y]$. Also assume that $n\geq d$.

In this section, we show that McSherry’s result [McS01] can be derived as a corollary of our main theorem. Consider an instance of the planted distribution model which satisfies the conditon (1). We would like to show that with high probability, the points satisfy the proximity condition. Fix a point $A_{i}\in{T_{r}}$. We will show that the probability that it does not satisfy this condition is at most $\frac{\delta}{n}$. Using union bound, it will then follow that the proximity condition is satisfied with probability at least $1-\delta$.

Let $s\neq r$. Let $v$ denote the unit vector along $\mu_{r}-\mu_{s}$. Let $L_{rs}$ denote the line joining $\mu_{r}$ and $\mu_{s}$, and $\hat{A_{i}}$ be the projection of $A_{i}$ on $L_{rs}$. The following result shows that the distance between $\hat{A_{i}}$ and $\mu_{r}$ is small with high probability.

Assume $\sigma\geq\frac{3\log n}{n},$ where $\sigma=\max_{i,j}\sqrt{P_{ij}}$. With probability at least $1-\frac{\delta}{n\cdot k}$,

Proof. For a vector $A_{i}$, we use $A_{ij}$ to denote the coordinate of $A_{i}$ at position $j$. Define $\mu_{rj}$ similarly. First observe that $|{\hat{A_{i}}}-\mu_{r}|=|v\cdot(A_{i}-\mu_{r})|$. The coordinates of $v$ corresponding to points belonging to a particular cluster are same – let $v^{t}$ denote this value for cluster ${T_{t}}$. So we get

where $n_{t}$ denotes the size of cluster ${T_{t}}$. The last inequality above follows from the fact that $|v|=1$. So, $1\geq\sum_{j\in{T_{t}}}v_{j}^{2}=(v^{t})^{2}\cdot n_{t}$. Now, if $A_{i}$ does not satisfy the condition of the lemma, then there must be some $t$ for which

Now note that $A_{ij}$, $j\in{T_{r}}$ are i.i.d. -$1$ random variables with mean $P_{rt}$. Now we use the following version of Chernoff bound : let $X_{1},\ldots,X_{l}$ be i.i.d. 0–1 random variables, each with mean $p$. Then

For us, $\eta=\frac{c\sigma}{P_{rt}\sqrt{n_{t}}}\cdot\left(\log\left(\frac{n}{\delta}\right)+\frac{1}{\sqrt{w_{\min}}}\right).$ If $\eta\leq 2e-1$, the probability of this event is at most

Now, assume $\eta>2e-1$. In this case the probability of this event is at most

where we have assumed that $\sigma\geq\frac{3\log n}{n}$ (we need this assumption anyway to use Wigner’s theorem for bounding $||A-C||$).

with probability at least $1-\frac{\delta}{nk}$. Here, we have used the fact that $||A-C||\leq c^{\prime}\cdot\sigma\sqrt{n}$ with high probability (Wigner’s theorem). Now, using union bound, we get that all the points satisfy the proximity condition with probability at least $1-\delta$.

Remark : Here we have used $C$ as the matrix whose rows are the actual means $\mu_{r}$. But while applying Theorem 2.2, $C$ should represent the means of the samples in $A$ belonging to a particular cluster. The error incurred here can be made very small and will not affect the results. So we shall assume that $\mu_{r}$ is the actual mean of points in $T_{r}$. Similar comments apply in other applications described next.

2 Learning Mixture of Gaussians

We are given a mixture of $k$ Gaussians $F_{1},\ldots,F_{k}$ in $d$ dimensions. Let the mixture weights of these distributions be $w_{1},\ldots,w_{k}$ and $\mu_{1},\ldots,\mu_{k}$ denote their means respectively.

for all $r,s,r\neq s$. Here $\sigma_{\max}$ is the maximum variance in any direction of any of the distributions $F_{r}$.

3 Learning Mixture of Distributions with Bounded Variance

We consider a mixture of distributions $F_{1},\ldots,F_{k}$ with weights $w_{1},\ldots,w_{k}$. Let $\sigma$ be an upper bound on the variance along any direction of a point sampled from one of these distributions. In other words,

for all distributions $F_{r}$ and each unit vector $v$.

for all $r,s,r\neq s$. Here $\varepsilon$ is assumed to be less than $w_{\min}$.

Proof. The algorithm is described in Figure 3. We now prove that this algorithm has the desired properties. Let $A$ denote the $n\times d$ matrix of points and $C$ be the corresponding matrix of means. We first bound the spectral norm of $A-C$. The bound obtained is quite high, but is probably tight.

The above lemma allows us to bound the distance between $\mu_{r}$ and the nearest mean obtained in Step 1 of the algorithm. The proof proceeds along the same lines as that of Lemma 5.1.

Proof. Suppose the statement of the lemma is false for $\mu_{r}$. At most $kd^{2}\log d$, which is much less than $|T_{r}|$, points are assigned to a center which is removed in Step 2. The remaining points in $T_{r}$ are assigned to centers which are not removed. So, arguing as in the proof of Lemma 5.1, the clustering cost in step 1 for points in $T_{r}$ is at least

where the last inequality follows from Lemma 6.5. But, as in the proof of Lemma 5.1, this is a contradiction.

Note that in the lemma above, $\nu_{r}$ may not be unique for different means $\mu_{r}$. Call a point $A_{i}\in T_{r}$ bad if $|A_{i}-\mu_{r}|\geq\frac{\sigma\sqrt{n}}{2}$. Call a point $A_{i}\in T_{r}$ nice if $|A_{i}-\mu_{r}|\leq\frac{\sigma\sqrt{n}}{2\sqrt{d}}$

The number of bad points is at most $d\cdot\log d$ with high probability. The number of points which are not nice is at most $d^{2}\log d$ with high probability. The number of nice points that are removed is at most $4kd^{2}\log d$.

Proof. Arguing as in the proof of Lemma 6.5, the probability that $|A_{i}-C_{i}|\geq\sigma\cdot\sqrt{n}$ is at most $\frac{d}{n}$. So the expected number of bad points is at most $d$. The first statement in the lemma now follows from Chernoff bound. The second statement is proved similarly. At most $kd^{2}\log d$ points are removed in Step 1. Now suppose $A_{i}$ is nice. Then Lemma 6.6 implies that it will not be removed in Step 3 (using Lemma 6.5 and the fact that $n$ is large enough).

With high probability the following event happens : suppose $\nu_{r}$ does not get removed in Step 2. Then there is a mean $\mu_{r}$ such that $|\mu_{r}-\nu_{r}|\leq\frac{2\sigma\sqrt{n}}{\sqrt{d}}.$

Proof. Since $\nu_{r}$ is not removed, it has at least one nice point $A_{i}$ assigned to it (otherwise it will have at most $d^{2}\log d$ points assigned to it and it will be removed). The distance of $A_{i}$ to the nearest mean $\mu_{s}$ is at most $\frac{\sigma\sqrt{n}}{2\sqrt{d}}$, and Lemma 6.6 implies that there is a center $\nu_{s}$ which is not removed and for which $|\mu_{s}-\nu_{s}|\leq\frac{\sigma\sqrt{n}}{2\sqrt{d}}$. So, $|\nu_{s}-A_{i}|\leq\frac{\sigma\sqrt{n}}{\sqrt{d}}$. Since $\nu_{r}$ is the closest center to $A_{i}$, $|\nu_{r}-A_{i}|\leq\frac{\sigma\sqrt{n}}{\sqrt{d}}$ as well. Now, $|\nu_{r}-\mu_{s}|\leq|\nu_{r}-A_{i}|+|A_{i}-\mu_{s}|$ and the result follows.

Let $A^{\prime}$ be the set of points which are remaining after the third step of our algorithm. We now define a new clustering $T_{1}^{\prime},\ldots,T_{k}^{\prime}$ of points in $A^{\prime}$. This clustering will be very close to the actual clustering $T_{1},\ldots,T_{k}$ and so it will be enough to correctly cluster a large fraction of the points according to this new clustering. We define

Let $\mu_{r}^{\prime}$ be the mean of $T_{r}^{\prime}$ and $C^{\prime}$ be the corresponding matrix of means.

Proof. We first prove the second statement. The points in $T_{r}^{\prime}$ contain all the points in $T_{r}$ except for at most $5kd^{2}\log d$ points (Lemma 6.7). First consider the points in $T_{r}-T_{r}^{\prime}$ which are not bad. Since all these points are at distance less than $\sigma\sqrt{n}$ from $\mu_{r}$, the removal of these points shifts the mean by at most $\frac{5\sigma k\sqrt{n}d^{2}\log d}{|T_{r}|}\leq\frac{\sigma kd^{2}\log d}{\varepsilon\sqrt{n}}$. Now $T_{r}^{\prime}$ may contain some bad points as well. First observe that any such bad point must be at most $\frac{3\sigma\sqrt{n}}{\sqrt{d}}$ away from $\mu_{r}$. Indeed, the reason why we retained this bad point in Steps 2 and 3 is because it is at distance at most $\frac{\sigma\sqrt{n}}{\sqrt{d}}$ from $\nu_{r}$ from some $r$. So combined with Corollary 6.8, this statement is true. So these bad points can again shift the mean by a similar amount. This proves the second part of the lemma.

We are now ready to prove the main theorem. We would like to recover the clustering $C^{\prime}$ (since $C$ and $C^{\prime}$ agree on all but the bad points). We argue that at least $(1-\varepsilon)$ fraction of the points satisfy the proximity condition. Indeed, it is easy to check that at least $(1-\varepsilon)$ fraction of the points $A_{i}$ are at distance at most $\frac{4\sigma\sqrt{d}}{\sqrt{\varepsilon}}$ from the corresponding mean $\mu_{r}$ and satisfy the proximity condition. Since the distance between $\mu_{s}$ and $\mu_{s}^{\prime}$ is very small (dependent inversely on $n$), and $A_{i}$ is only $\frac{4\sigma\sqrt{d}}{\sqrt{\varepsilon}}$ far from $\mu_{r}$, it will satisfy the proximity condition for $A^{\prime},C^{\prime}$ as well (provided $n$ is large enough).

4 Sufficient conditions for convergence of k−limit-from𝑘k-means

As mentioned in Section 3, Ostrovsky et. al. [ORSS06] provided the first sufficient conditions under which they prove effectiveness of (a suitable variant of) the $k-$means algorithm. Here, we show that their conditions are (much) stronger than the proximity condition. We first describe their conditions. Let $\Delta_{k}$ be the optimal cost of the $k$-means problem (i.e., sum of distance squared of each point to nearest center) with $k$ centers. They require:

The condition above implies the proximity condition for all but $\varepsilon$ fraction of the points.

Proof. Suppose the above condition is true. One way of getting a solution with $k-1$ centers is to remove a center $\mu_{r}$ and move all points in $T_{r}$ to the nearest other center $\mu_{s}$. Now, their condition implies

If some $\varepsilon$ fraction of $T_{r}$ do not satisfy the proximity condition, then the distance squared of each such point to $\mu_{r}$ is at least the distance squared along the line $\mu_{r}$ to $\mu_{s}$ which is at least $(1/4)|\mu_{r}-\mu_{s}|^{2}$ which is at least $\Omega(||A-C||_{F}^{2}/n_{r}\epsilon)$. So even the assignment cost of such points exceeds $||A-C||_{F}^{2}$, the total cost, a contradiction. This proves the claim.

We now show that our algorithm gives a PTAS for the $k-$means problem.

Let $T_{1},\ldots,T_{k}$ be the optimal clustering and $\mu_{1},\ldots,\mu_{k}$ be the corresponding means. As before, $n_{r}$ denotes the size of $T_{r}$. Let $G$ be the set of points which satisfy the proximity condition (the good points). The above claim shows that $|G|\geq(1-\varepsilon)n$. For simplicity, assume that exactly $\varepsilon$ fraction of the points do not satisfy the proximity condition.

Let $S_{1},\ldots,S_{r}$ be the clustering output by our algorithm. Let $\mu_{r}^{\prime}$ be the mean of $S_{r}$. First observe that Theorem 5.5 implies that when our algorithm stops,

for some constant $c$. For a point $A_{i}$, let $\alpha(A_{i})$ the square of its distance to the closest mean among $\mu_{1},\ldots,\mu_{k}$. Define $\alpha^{\prime}(A_{i})$ for the solution output by our algorithm similarly.

If $A_{i}\notin G$, then $\alpha^{\prime}(A_{i})\leq(1+O(\varepsilon))\cdot\alpha(A_{i}).$

Proof. Suppose $A_{i}\in T_{r}$, and it does not satisfy the proximity condition for the pair $\mu_{r},\mu_{s}$. Then it is easy to see that $\alpha(A_{i})\geq\left(|\mu_{r}-\mu_{s}|/2-\Delta_{rs}\right)^{2}\geq\frac{|\mu_{r}-\mu_{s}|^{2}}{4}\geq\frac{||A-C||^{2}}{4n_{r}\varepsilon}$. Let $\mu_{t}$ be the closest mean to $A_{i}$. Then

where the second last inequality follows from equation (7). Note that the constant in $O(\varepsilon)$ above contains terms involving $k$ and $w_{\min}$.

If $A_{i}\in G$, but is mis-classified by our algorithm, then $\alpha^{\prime}(A_{i})\leq(1+O(\varepsilon))\cdot\alpha(A_{i}).$

Proof. Suppose $A_{i}\in G\cap T_{r}\cap S_{s}$. We use the machinery developed in the proof of Theorem 5.4. Define $\lambda,u$ as in the proof of this theorem. Clearly, $\alpha^{\prime}(A_{i})\leq\alpha(A_{i})+2|\mu_{r}-\mu_{s}|^{2}$ (here we have also used equation (7)). But note that $\alpha(A_{i})\geq|u|^{2}$. Now, $|u|\geq\frac{\Delta_{rs}|\mu_{r}-\mu_{s}|}{64\delta}=\Omega\left(\frac{|\mu_{r}-\mu_{s}|}{\sqrt{\varepsilon}}\right)$ (again using equation (7)). This implies the result.

where $\beta$ is a large constant in terms of $k,\frac{1}{w_{\min}},c$. Summing this over all points in $T_{r}\cap S_{r}$, we get

where the last inequality follows from (7) assuming $\beta$ is large enough. But now, the proof of Claim 6.11, implies that $\sum_{A_{i}\notin G}\alpha(A_{i})\geq\frac{||A-C||^{2}}{4}.$ So we are done.

Now summing over all $r$ in Claim 6.13 and using Claims 6.11, 6.12 implies that our algorithm is also a PTAS.

Boosting

Recall that the proximity condition requires that the distance between the means be polynomially dependent on $\frac{1}{w_{\min}}$ – this could be quite poor when one of the clusters is considerably smaller that the others. In this section, we try to overcome this obstacle for a special class of distributions.

Let $F_{1},\ldots,F_{k}$ be a mixture of distributions in $d$ dimensions. Let $A$ be the $n\times d$ matrix of samples from the distribution and $C$ be the corresponding matrix of centers. Let $D_{\min}$ denote $\min_{r,s,r\neq s}|\mu_{r}-\mu_{s}|$. Then the key property that we desire from the mixture of distributions is as follows. The following conditions should be satisfied with high probability :

where $\alpha$ is a small enough constant (something like 0.1 will suffice).

where $v$ is the unit vector joining $\mu_{r}$ and $\mu_{s}$. This condition is essentially saying that the average variance of points in $T_{r}$ along $v$ is bounded by $\frac{|\mu_{r}-\mu_{s}|}{\sqrt{4}}$.

The number of samples $n$ will be a polynomial in $\frac{d}{w_{\min}}$. Recall that $D_{\min}$ denotes $\min_{r,s,r\neq s}|\mu_{r}\mu_{s}|$. To simplify the presentation, we assume that $|\mu_{r}-\mu_{s}|\leq D_{\min}\cdot\left(\frac{d}{w_{\min}}\right)^{\beta}$ for a constant $\beta$ for all pairs $r,s$. We will later show how to get rid of this assumption. We now sample two sets of $n$ points from this distribtion – call these $A$ and $B$. Assume that both $A$ and $B$ satisfy the condtions (9) and (10). For all $r$, we assume that the mean of $A_{i},i\in T_{r}$ is $\mu_{r}$ and $T_{r}\cap A$ has size $w_{r}\cdot n$. We assume the same for the points in $B$. The error caused by removing this assumption will not change our results. Let $\mu$ denote the overall mean of the points in $A$ (or $B$). Note that $\mu=\sum_{r}w_{r}\mu_{r}$. We translate the points so that the overall mean is 0. In other words, define a translation $f$ as $f(x)=x-\mu$. Let $A_{i}^{\prime}$ denote $f(A_{i})$. Define $B_{i}^{\prime}$ similarly. We now define a set $X$ of $n$ points in $n$ dimensions. The point $X_{i}$ is defined as

The correspondence between $X_{i}$ and $A_{i}$ naturally defines a partitioning of $X$ into $k$ clusters. Let $S_{r},r=1,\ldots,k,$ denote these clusters. The mean $\theta_{r}$ of $S_{r}$ is

where $C_{r}^{\prime}=C_{r}-\mu$. Let $Z$ denote the matrix of means of $X$, i.e., $Z_{i}=\theta_{r}$ if $X_{i}\in S_{r}$. We now show that this process amplifies the distance between the means $\theta_{r}$ by a much bigger factor than $\frac{||X-Z||}{\sqrt{n}}$.

Proof. First observe that $(\mu_{r}-\mu_{s})\cdot(\mu_{r}-\mu_{s})=(\mu_{r}-\mu)\cdot(\mu_{r}-\mu_{s})-(\mu_{s}-\mu)\cdot(\mu_{r}-\mu_{s})$. So at least one of $|(\mu_{r}-\mu)\cdot(\mu_{r}-\mu_{s})|,|(\mu_{s}-\mu)\cdot(\mu_{r}-\mu_{s})|$ must be at least $\frac{|\mu_{r}-\mu_{s}|^{2}}{2}$. Assume without loss of generality that this is so for $|(\mu_{r}-\mu)\cdot(\mu_{r}-\mu_{s})|$. Now consider the coordinates $i$ of $\theta_{r}-\theta_{s}$ corresponding to $S_{r}$. Such a coordinate will have value $(\mu_{r}-\mu_{s})\cdot B_{i}^{\prime}$. Therefore,

where the last inequality follows from (10). This proves the lemma.

Proof. We can write $Y^{T}Y$ as $\sum_{i}Y_{i}^{T}Y_{i}$. Let $v$ be any unit vector. Then $v^{T}E[Y^{T}Y]v=\sum_{i}E|Y_{i}\cdot v|^{2}$. For a fixed $i$, where $A_{i}\in T_{r}$,

where the last inequality follows from the fact that expectation of $Y_{j}$ is $\mu$ and $Y_{j},Y_{j}^{\prime}$ are independent if $j\neq j^{\prime}$. Rest of the argument is as in Claim 7.3.

The above two claims combined with Fact 6.1 imply the lemma.

Now we pick $n$ to be at least $\left(\frac{d}{w_{\min}}\right)^{8(\beta+1)}$. Assuming $\alpha<0.1$, this implies (using the above two lemmas) that for all $r,s$, $r\neq s$,

We now run the first step of the algorithm Cluster on $X$. We claim that the clustering obtained after the first step has very few classification errors. Let $\phi_{r},r=1,\ldots,k$ be the $k$ centers output by the first step of the algorithm Cluster. Lemma 5.1 implies that for each center $\theta_{r}$, there exists a center $\phi_{r}$ satisfying

Order the centers $\phi_{r}$ such that $\phi_{r}$ is closest to $\theta_{r}$ – equation (11) implies that the closest estimated centers to different $\theta_{r}$ are distinct. It also follows that for $r\neq s$

The number of points in $S_{r}$ which are not assigned to $\phi_{r}$ after the first step of the algorithm is at most $\left(\frac{w_{\min}}{d}\right)^{2\beta}\cdot n$.

Proof. We use the notation in Step 1 of algorithm Cluster. Suppose the statement of the lemma is not true. Then, in the $k$-means solution, at least $\left(\frac{w_{\min}}{d}\right)^{2\beta}\cdot n$ points in ${\hat{X}}_{i},i\in S_{r}$ are assigned to a center at least $\frac{1}{2}\cdot\frac{||X-Z||}{\sqrt{n}}\cdot\left(\frac{d}{w_{\min}}\right)^{4\beta}$ distance away (using equation 12). But then the square of $k$-means clustering cost is much larger that $k\cdot||X-Z||^{2}$.

Now, we use the clustering given by the centers $\phi_{r}$ to partition the original set of points $A$ – thus we have a clsutering of these points where the number of mis-classified points from any cluster $T_{r}$ is at most $\left(\frac{w_{\min}}{d}\right)^{2\beta}\cdot n$. Let $S_{r}$ denote this clustering, where $S_{r}$ corresponds to $T_{r}$. Let $\nu_{r}$ denote the center of $S_{r}$. We now argue that $|\nu_{r}-\mu_{r}|$ is very small.

For every $s$, $|\nu_{s}-\mu_{s}|\leq\frac{||A-C||}{\sqrt{n}}.$

Proof. We use arguments similar to proof of Theorem 5.5. Let $n_{rs},\mu_{rs}$ denote the number and mean respectively of $T_{r}\cap S_{s}$. Similarly, define $n_{ss}$ and $\mu_{ss}$ as the size and mean of the points in ${T_{s}}\cap S_{s}$. We know that

Now, proceeding as in the proof of Theorem 5.5, we get

Starting from the centers $\nu_{r}$, we run the second step of algorithm Cluster. Then, we have the analogue of Theorem 2.2 in this setting.

Suppose a mixture of distribution satisfies the conditions (8–10) above and at least $(1-\varepsilon)$ fraction of sampled points satisfy the proximity condition. Then we can correctly classify all but $O(k^{2}\varepsilon)$ fraction of the points.

We now remove the assumption that $|\mu_{r}-\mu_{s}|\leq D_{\min}\cdot\left(\frac{d}{w_{\min}}\right)^{\beta}$ – let $\gamma$ denote the latter quantity. We construct a graph $G=(V,E)$ as follows : $V$ is the set of points $A\cup B$, and we join two points by an edge if the distance between them is at most $\gamma/k$. First observe that if $i,j\in T_{r}$, then they will be joined by an edge provided the following condition holds (using condition (9)) :

and the same for $A$ replaced by $B$ above. This would hold if $\alpha<0.1$ (recall that $n$ is roughly $\left(\frac{d}{w_{\min}}\right)^{8(\beta+1)}$). Now consider the connected components of this graph. In each connected component, any two vertices are joined by a path of length at most $k$ (because any two vertices from the same cluster $T_{r}$ have an edge between them). So the distance between any two vertices from the same component is at most $\gamma$. Therefore the distance from the mean of two clusters in the same component is at most $\gamma$. Now, we can apply the arguments of this section to each component independently. This would, however, require us to know the number of clusters in each component of this graph. If we treat $k$ as a constant, this is only constant number of choices. A better way is to modify the definition of $X$ as follows : consider a point $A_{i}$. Let $\mu$ denote the mean of the points in the same component as $A_{i}$ in the graph $G$. Then $X_{ij}=(A_{i}-\mu)\cdot(B_{j}-\mu)$ if $A_{i},B_{j}$ belong to the same component of $G$, $L$ otherwise, where $L$ is a large quantity. Now note that $\theta_{r}-\theta_{s}$ will still satisfy the statement of Lemma 7.1, because if they are from the same component in $G$, then it follows from the lemma, otherwise the distance between them is at least $L$. But Lemma 7.2 continues to hold without any change, and so rest of the arguments follow as they are.

We now give some applications of Theorem 7.7.

Suppose we are given a mixture of Gaussian distribution $F_{1},\ldots,F_{k}$. Suppose the means satisfy the following separation condition for all $r,s,r\neq s$ :

1.2 Learning Power Law Distributions

Consider a mixture of distributions $F_{1},\ldots,F_{k}$ where each of the distributions $F_{r}$ satisfies the following condition for every unit vector $v$ :

where $\gamma\geq 2$ is a large enough constant. Let $A$ be a set of $n$ samples from the mixture. Suppose the means satisfy the following separation condition for every $r,s,r\neq s$ :

Proof. Let $e_{1},\ldots,e_{d}$ be orthonormal basis for the space. Then $|(A_{i}-C_{i})\cdot e_{l}|\leq\sigma(nd)^{\frac{1}{\gamma}}\cdot\log(n)$ for all $i$ with high probability. So, with high probability, for all $i$,