What is the relation between k-means clustering and PCA? It is a common practice to apply PCA (principal component analysis) before a clustering algorithm (such as k-means). It is believed that it improves the clustering results in practice (noise reduction). 
However I am interested in a comparative and in-depth study of the relationship between PCA and k-means. For example, Chris Ding and Xiaofeng He, 2004, K-means Clustering via Principal Component Analysis showed that "principal components are the continuous
solutions to the discrete cluster membership indicators for K-means clustering". However, I have hard time understanding this paper, and Wikipedia actually claims that it is wrong.
Also, the results of the two methods are somewhat different in the sense that PCA helps to reduce the number of "features" while preserving the variance, whereas clustering reduces the number of "data-points" by summarizing several points by their expectations/means (in the case of k-means).
So if the dataset consists in $N$ points with $T$ features each, PCA aims at compressing the $T$ features whereas clustering aims at compressing the $N$ data-points.
I am looking for a layman explanation of the relations between these two techniques + some more technical papers relating the two techniques.
 A: Intuitive relationship of PCA and KMeans


*Theoretically PCA dimensional analysis (the first K dimension retaining say the 90% of variance...does not need to have direct relationship with K Means cluster), however the value of using PCA came from
a) practical consideration given the nature of objects that we analyse tends to naturally cluster around/evolve from ( a certain segment of) their principal components (age, gender..)
b) PCA eliminates those low variance dimension (noise), so itself adds value (and form a sense similar to clustering) by focusing on those key dimension
In simple terms, it is just like X-Y axis is what help us master any abstract mathematical concept but in a more advance manner.


*K Means try to minimize overall distance within a cluster for a given K


*For a set of objects with N dimension parameters, by default similar objects Will have MOST parameters “similar” except  a few key difference (eg  a group of young IT students, young dancers, humans… will have some highly similar features (low variance) but a few key features still quite diverse and capturing those "key Principal Componenents" essentially capture the majority of variance, eg. color, area of residence.... Hence low distortion if we neglect those features of minor differences, or the conversion to lower PCs will not loss much information


*It is thus “very likely” and “very natural” that grouping them together to look at the differences (variations) make sense for data evaluation
(eg. if you make 1,000 surveys in a week in the main street, clustering them based on ethnic, age, or educational background as PC make sense)
Under K Means’ mission, we try to establish a fair number of K so that those group elements (in a cluster) would have overall smallest distance (minimized) between Centroid and whilst the cost to establish and running the K clusters is optimal (each members as a cluster does not make sense as that is too costly to maintain and no value)


*K Means grouping could be easily “visually inspected” to be optimal,  if such K is along the Principal Components (eg. if for people in different age, ethnic / regious clusters they tend to express similar opinions so if you cluster those surveys based on those PCs, then that achieve the minization goal (ref. 1)
Also those PCs (ethnic, age, religion..) quite often are orthogonal, hence visually distinct by viewing the PCA


*However this intuitive deduction lead to a sufficient but not a necessary condition.
(Ref 2: However, that PCA is a useful relaxation of k-means clustering was not a new result (see, for example,[35]), and it is straightforward to uncover counterexamples to the statement that the cluster centroid subspace is spanned by the principal directions.[36])
Choosing clusters based on / along the CPs may comfortably lead to comfortable allocation mechanism
This one could be an example if x is the first PC along X axis:
(...........CC1...............CC2............CC3    X axis)
where the X axis say capture over 9X% of variance and say is the only PC


*Finally PCA is also used to visualize after K Means is done (Ref 4)
If the PCA display* our K clustering result to be orthogonal or close to, then it is a sign that our clustering is sound  , each of which exhibit unique characteristics
(*since by definition PCA find out / display those major dimensions (1D to 3D) such that say K (PCA) will capture probably over a vast majority of the variance.
So PCA is both useful in visualize and confirmation of a good clustering, as well as an intrinsically useful  element in determining  K Means clustering -  to be used prior to after the K Means.
References:

*

*https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx

*https://en.wikipedia.org/wiki/Principal_component_analysis

*Clustering using principal component analysis: application of elderly people autonomy-disability (Combes & Azema)

*http://cs229.stanford.edu/notes/cs229-notes10.pdf Andrew Ng

A: Solving the k-means on its O(k/epsilon) low-rank approximation (i.e., projecting on the span of the first largest singular vectors as in PCA) would yield a (1+epsilon) approximation in term of multiplicative error.
Particularly, Projecting on the k-largest vector would yield 2-approximation.
In fact, the sum of squared distances for ANY set of k centers can be approximated by this projection. Then we can compute coreset on the reduced data to reduce the input to poly(k/eps) points that approximates this sum.
See:
    Dan Feldman, Melanie Schmidt, Christian Sohler:
Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. SODA 2013: 1434-1453
A: In a recent paper, we found that PCA is able to compress the Euclidean distance of intra-cluster pairs while preserving Euclidean distance of inter-cluster pairs.
Notice that K-means aims to minimize Euclidean distance to the centers. Hence the compressibility of PCA helps a lot.
This phenomenon can also be theoretical proved in random matrices. Please see our paper.
"Compressibility: Power of PCA in Clustering Problems Beyond Dimensionality Reduction"
Chandra Sekhar Mukherjee and Jiapeng Zhang
https://arxiv.org/abs/2204.10888
A: PCA and K-means do different things.
PCA is used for dimensionality reduction / feature selection / representation learning e.g. when the feature space contains too many irrelevant or redundant features. The aim is to find the intrinsic dimensionality of the data.
Here's a two dimensional example that can be generalized to
higher dimensional spaces. The dataset has two features, $x$ and $y$, every circle is a data point.

In the image $v1$ has a larger magnitude than $v2$. These are the Eigenvectors. The dimension of the data is reduced from two dimensions to one dimension (not much choice in this case) and this is done by projecting on the direction of the $v2$ vector (after a rotation where $v2$ becomes parallel or perpendicular to one of the axes). This is because $v2$ is orthogonal to the direction of largest variance. One way to think of it, is minimal loss of information. (There is still a loss since one coordinate axis is lost).
K-means is a clustering algorithm that returns the natural grouping of data points, based on their similarity. It's a special case of Gaussian Mixture Models.
In the image below the dataset has three dimensions. It can be seen from the 3D plot on the left that the $X$ dimension can be 'dropped' without losing much information. PCA is used to project the data onto two dimensions. In the figure to the left, the projection plane is also shown. Then, 
K-means can be used on the projected data to label the different groups, in the figure on the right, coded with different colors.

PCA or other dimensionality reduction techniques are used before both unsupervised or supervised methods in machine learning. In addition to the reasons outlined by you and the ones I mentioned above, it is also used for visualization purposes (projection to 2D or 3D from higher dimensions).
As to the article, I don't believe there is any connection, PCA has no information regarding the natural grouping of data and operates on the entire data, not subsets (groups). If some groups might be explained by one eigenvector ( just because that particular cluster is spread along that direction ) is just a coincidence and shouldn't be taken as a general rule.

"PCA aims at compressing the T features whereas clustering aims at compressing the N data-points."

Indeed, compression is an intuitive way to think about PCA. 
However, in K-means, to describe each point relative to it's cluster you still need at least the same amount of information (e.g. dimensions) $x_i = d( \mu_i, \delta_i) $, where $d$ is the distance and $\delta_i$ is stored instead of $x_i$. And you also need to store the $\mu_i$ to know what the delta is relative to. You can of course store $d$ and $i$ however you will be unable to retrieve the actual information in the data.
Clustering adds information really. I think of it as splitting the data into natural groups (that don't have to necessarily be disjoint) without knowing what the label for each group means (well, until you look at the data within the groups).
A: It is true that K-means clustering and PCA appear to have very different goals and at first sight do not seem to be related. However, as explained in the Ding & He 2004 paper K-means Clustering via Principal Component Analysis, there is a deep connection between them.
The intuition is that PCA seeks to represent all $n$ data vectors as linear combinations of a small number of eigenvectors, and does it to minimize the mean-squared reconstruction error. In contrast, K-means seeks to represent all $n$ data vectors via small number of cluster centroids, i.e. to represent them as linear combinations of a small number of cluster centroid vectors where linear combination weights must be all zero except for the  single $1$. This is also done to minimize the mean-squared reconstruction error.
So K-means can be seen as a super-sparse PCA.
Ding & He paper makes this connection more precise.

Unfortunately, the Ding & He paper contains some sloppy formulations (at best) and can easily be misunderstood. E.g. it might seem  that Ding & He claim to have proved that cluster centroids of K-means clustering solution lie in the $(K-1)$-dimensional PCA subspace:

Theorem 3.3. Cluster centroid subspace is spanned by the first
$K-1$ principal directions [...].

For $K=2$ this would imply that projections on PC1 axis will necessarily be negative for one cluster and positive for another cluster, i.e. PC2 axis will separate clusters perfectly.
This is either a mistake or some sloppy writing; in any case, taken literally, this particular claim is false.
Let's start with looking at some toy examples in 2D for $K=2$. I generated some samples from the two normal distributions with the same covariance matrix but varying means. I then ran both K-means and PCA. The following figure shows the scatter plot of the data above, and the same data colored according to the K-means solution below. I also show the first principal direction as a black line and class centroids found by K-means with black crosses. PC2 axis is shown with the dashed black line. K-means was repeated $100$ times with random seeds to ensure convergence to the global optimum.

One can clearly see that even though the class centroids tend to be pretty close to the first PC direction, they do not fall on it exactly. Moreover, even though PC2 axis separates clusters perfectly in subplots 1 and 4, there is a couple of points on the wrong side of it in subplots 2 and 3.
So the agreement between K-means and PCA is quite good, but it is not exact.
So what did Ding & He prove? For simplicity, I will consider only $K=2$ case. Let the number of points assigned to each cluster be $n_1$ and $n_2$  and the total number of points $n=n_1+n_2$. Following Ding & He, let's define cluster indicator vector $\mathbf q\in\mathbb R^n$  as follows: $q_i = \sqrt{n_2/nn_1}$ if $i$-th points belongs to cluster 1 and $q_i = -\sqrt{n_1/nn_2}$ if it belongs to cluster 2. Cluster indicator vector has unit length $\|\mathbf q\| = 1$ and is "centered", i.e. its elements sum to zero $\sum q_i = 0$.
Ding & He show that K-means loss function $\sum_k \sum_i (\mathbf x_i^{(k)} - \boldsymbol \mu_k)^2$ (that K-means algorithm minimizes), where $x_i^{(k)}$ is the $i$-th element in cluster $k$, can be equivalently rewritten as $-\mathbf q^\top \mathbf G \mathbf q$, where $\mathbf G$ is the $n\times n$ Gram matrix of scalar products between all points: $\mathbf G = \mathbf X_c \mathbf X_c^\top$, where $\mathbf X$ is the $n\times 2$ data matrix and $\mathbf X_c$ is the centered data matrix.
(Note: I am using notation and terminology that slightly differs from their paper but that I find clearer).
So the K-means solution $\mathbf q$ is a centered unit vector maximizing $\mathbf q^\top \mathbf G \mathbf q$. It is easy to show that the first principal component (when normalized to have unit sum of squares) is the leading eigenvector of the Gram matrix, i.e. it is also a centered unit vector $\mathbf p$ maximizing $\mathbf p^\top \mathbf G \mathbf p$. The only difference is that $\mathbf q$ is additionally constrained to have only two different values whereas $\mathbf p$ does not have this constraint.
In other words, K-means and PCA maximize the same objective function, with the only difference being that K-means has additional "categorical" constraint.
It stands to reason that most of the times the K-means (constrained) and PCA (unconstrained) solutions will be pretty to close to each other, as we saw above in the simulation, but one should not expect them to be identical. Taking $\mathbf p$ and setting all its negative elements to be equal to $-\sqrt{n_1/nn_2}$ and all its positive elements to $\sqrt{n_2/nn_1}$ will generally not give exactly  $\mathbf q$.
Ding & He seem to understand this well because they formulate their theorem as follows:

Theorem 2.2. For K-means clustering where $K= 2$, the continuous solution of the cluster indicator vector is the [first] principal component

Note that words "continuous solution". After proving this theorem they additionally comment that PCA can be used to initialize K-means iterations which makes total sense given that we expect $\mathbf q$ to be close to $\mathbf p$. But one still needs to perform the iterations, because they are not identical.
However, Ding & He then go on to develop a more general treatment for $K>2$ and end up formulating Theorem 3.3 as

Theorem 3.3. Cluster centroid subspace is spanned by the first
$K-1$ principal directions [...].

I did not go through the math of Section 3, but I believe that this theorem in fact also refers to the "continuous solution" of K-means, i.e. its statement should read "cluster centroid space of the continuous solution of K-means is spanned [...]".
Ding & He, however, do not make this important qualification, and moreover write in their abstract that

Here we prove
that principal components are the continuous
solutions to the discrete cluster membership
indicators for
K-means clustering.  Equivalently, we show that the subspace spanned
by the cluster centroids are given by spectral expansion of the data covariance matrix truncated at $K-1$ terms.

The first sentence is absolutely correct, but the second one is not. It is not clear to me if this is a (very) sloppy writing or a genuine mistake. I have very politely emailed both authors asking for clarification. (Update two months later: I have never heard back from them.)

Matlab simulation code
figure('Position', [100 100 1200 600])

n = 50;
Sigma = [2 1.8; 1.8 2];

for i=1:4
    means = [0 0; i*2 0];
    
    rng(42)
    X = [bsxfun(@plus, means(1,:), randn(n,2) * chol(Sigma)); ...
         bsxfun(@plus, means(2,:), randn(n,2) * chol(Sigma))];
    X = bsxfun(@minus, X, mean(X));
    [U,S,V] = svd(X,0);
    [ind, centroids] = kmeans(X,2, 'Replicates', 100);
    
    subplot(2,4,i)
    scatter(X(:,1), X(:,2), [], [0 0 0])

    subplot(2,4,i+4)
    hold on
    scatter(X(ind==1,1), X(ind==1,2), [], [1 0 0])
    scatter(X(ind==2,1), X(ind==2,2), [], [0 0 1])
    plot([-1 1]*10*V(1,1), [-1 1]*10*V(2,1), 'k', 'LineWidth', 2)
    plot(centroids(1,1), centroids(1,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(1,1), centroids(1,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
    plot(centroids(2,1), centroids(2,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(2,1), centroids(2,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
    
    plot([-1 1]*5*V(1,2), [-1 1]*5*V(2,2), 'k--')
end

for i=1:8
    subplot(2,4,i)
    axis([-8 8 -8 8])
    axis square
    set(gca,'xtick',[],'ytick',[])
end    

A: It is common to whiten data before using k-means. The reason is that k-means is extremely sensitive to scale, and when you have mixed attributes there is no "true" scale anymore. Then you have to normalize, standardize, or whiten your data. None is perfect, but whitening will remove global correlation which can sometimes give better results. PCA/whitening is $O(n\cdot d^2 + d^3)$ since you operate on the covariance matrix.
To my understanding, the relationship of k-means to PCA is not on the original data. It is to using PCA on the distance matrix (which has $n^2$ entries, and doing full PCA thus is $O(n^2\cdot d+n^3)$ - i.e. prohibitively expensive, in particular compared to k-means which is $O(k\cdot n \cdot i\cdot d)$ where $n$ is the only large term), and maybe only for $k=2$. K-means is a least-squares optimization problem, so is PCA. k-means tries to find the least-squares partition of the data. PCA finds the least-squares cluster membership vector.
The first Eigenvector has the largest variance, therefore splitting on this vector (which resembles cluster membership, not input data coordinates!) means maximizing between cluster variance. By maximizing between cluster variance, you minimize within-cluster variance, too.
But for real problems, this is useless. It is only of theoretical interest.
