9
$\begingroup$

Christopher Bishop writes in his book Pattern Recognition and Machine Learning a proof, that each consecutive principal component maximizes the variance of the projection to one dimension, after the data has been projected to orthogonal space to the previously selected components. Others show similar proofs.

However, this only proves that each consecutive component is the best projection to one dimension, in terms of maximizing the variance. Why does this imply, that variance of a projection to say 5 dimensions is maximized choosing first such components?

$\endgroup$
  • $\begingroup$ Could you please tell us exactly what would be meant by the "variance" of the five-dimensional dataset that results from a projection of a dataset into five dimensions? (In order for such a quantity to be subject to maximization it would have to be a single number.) $\endgroup$ – whuber Jun 9 '14 at 13:27
  • 3
    $\begingroup$ Very good point. Chris Bishop in his book refers to minimizing variance of a projection and it is not very clear what that would mean for more then 1 dimension. I would like to learn in what sence the variance is minimized and why such a procedure minimizes it jointly. $\endgroup$ – michal Jun 10 '14 at 10:11
  • 1
    $\begingroup$ @user123675: In your last comment you probably mean "maximizing", not "minimizing". $\endgroup$ – amoeba Jun 11 '14 at 10:08
  • $\begingroup$ Yes, you are right. Sorry! $\endgroup$ – michal Jul 3 '14 at 14:56
10
$\begingroup$

What is understood by variance in several dimensions ("total variance") is simply a sum of variances in each dimension. Mathematically, it's a trace of the covariance matrix: trace is simply a sum of all diagonal elements. This definition has various nice properties, e.g. trace is invariant under orthogonal linear transformations, which means that if you rotate your coordinate axes, the total variance stays the same.

What is proved in Bishop's book (section 12.1.1), is that the leading eigenvector of covariance matrix gives the direction of maximal variance. Second eigenvector gives the direction of maximal variance under an additional constraint that it should be orthogonal to the first eigenvector, etc. (I believe this constitutes the Exercise 12.1). If the goal is to maximize the total variance in the 2D subspace, then this procedure is a greedy maximization: first choose one axis that maximizes variance, then another one.

Your question is: why does this greedy procedure obtain a global maximum?

Here is a nice argument that @whuber suggested in the comments. Let us first align the coordinate system with the PCA axes. The covariance matrix becomes diagonal: $\boldsymbol{\Sigma} = \mathrm{diag}(\lambda_i)$. For simplicity we will consider the same 2D case, i.e. what is the plane with maximal total variance? We want to prove that it is the plane given by the first two basis vectors (with total variance $\lambda_1+\lambda_2$).

Consider a plane spanned by two orthogonal vectors $\mathbf{u}$ and $\mathbf{v}$. The total variance in this plane is $$\mathbf{u}^\top\boldsymbol{\Sigma}\mathbf{u} + \mathbf{v}^\top\boldsymbol{\Sigma}\mathbf{v} = \sum \lambda_i u_i^2 + \sum \lambda_i v_i^2 = \sum \lambda_i (u_i^2+v_i^2).$$ So it is a linear combination of eigenvalues $\lambda_i$ with coefficients that are all positive, do not exceed $1$ (see below), and sum to $2$. If so, then it is almost obvious that the maximum is reached at $\lambda_1 + \lambda_2$.

It is only left to show that the coefficients cannot exceed $1$. Notice that $u_k^2+v_k^2 = (\mathbf{u}\cdot\mathbf{k})^2+(\mathbf{v}\cdot\mathbf{k})^2$, where $\mathbf{k}$ is the $k$-th basis vector. This quantity is a squared length of a projection of $\mathbf k$ onto the plane spanned by $\mathbf u$ and $\mathbf v$. Therefore it has to be smaller than the squared length of $\mathbf k$ which is equal to $|\mathbf{k}|^2=1$, QED.

See also @cardinal's answer to What is the objective function of PCA? (it follows the same logic).

$\endgroup$
  • 1
    $\begingroup$ (+1) But is it not intuitively obvious that given a collection of wallets of various amounts of cash (modeling the non-negative eigenvalues), and a fixed number $k$ that you can pick, that selecting the $k$ richest wallets will maximize your total cash? The proof that this intuition is correct is almost trivial: if you haven't taken the $k$ largest, then you can improve your sum by exchanging the smallest one you took for a larger amount. $\endgroup$ – whuber Jun 11 '14 at 17:23
  • $\begingroup$ @amoeba: if the goal is to maximize the sum of the variances and not variance of the sum, there is no reason for the second projection to be orthogonal to the first. $\endgroup$ – Innuo Jun 11 '14 at 19:32
  • 1
    $\begingroup$ I apologize--I had thought you had already developed the analysis to the point of recognizing that the total variance in a $k$-dimensional subspace is a non-negative linear combination of the eigenvalues, in which none of the coefficients can exceed $1$ and the total of the coefficients equals $k$. (That's a matter of a simple matrix multiplication--Lagrange multipliers aren't needed.) That then brings us to the wallets metaphor. I agree that some such analysis has to be done. $\endgroup$ – whuber Jun 11 '14 at 22:47
  • 1
    $\begingroup$ @amoeba: I mean we are considering the problem in the base consisting of eigenvectors (this is the base of u and v if we calculate their variance by multiplicating by diagonal covariance matrix). u and v will turn out in the end to be them, but at the stage of this proof we shouldn't assume this I think. Shouldn't the argument rather be, that if at any point the sum was larger than 1, then the 2 vectors would not be orthogonal anymore, since the base is orthogonal and each of the vectors brings at most 1? But then again, why do we restrict ourselves to orthogonal vectors u and v? $\endgroup$ – michal Jul 2 '14 at 8:53
  • 1
    $\begingroup$ @Heisenberg: Ah, I see! No, of course I did not mean that! But I see now why it was confusing. I rewrote this last bit of the proof to get rid of this "choosing a basis" step. Please see my edit. Thank you. $\endgroup$ – amoeba Mar 10 '15 at 10:16
2
$\begingroup$

If you have $N$ uncorrelated random variables sorted in descending order of their variance and were asked to choose $k$ of them such that the variance of their sum is maximized, would you agree that the greedy approach of picking the first $k$ would accomplish that?

The data projected onto the eigenvectors of its covariance matrix is essentially $N$ uncorrelated columns of data and whose variance equals the respective eigenvalues.

For the intuition to be clearer we need to relate variance maximization with computing the eigenvector of the covariance matrix with the largest eigenvalue, and relate orthogonal projection to removing correlations.

The second relation is clear to me because the correlation coefficient between two (zero mean) vectors is proportional to their inner product.

The relation between maximizing variance and the eigen-decomposition of the covariance matrix is as follows.

Assume that $D$ is the data matrix after centering the columns. We need to find the direction of maximum variance. For any unit vector $v$, the variance after projecting along $v$ is

$E[(Dv)^t Dv] = v^t E[D^tD] v = v^t Cov(D) v$

which is maximized if $v$ is the eigenvector of $Cov(D)$ corresponding to the largest eigenvalue.

$\endgroup$
  • $\begingroup$ The original question is rather: choose $k$ orthogonal linear combinations of them (as opposed to $k$ of them) such that the sum of their variances is maximized. Is it still obvious that the greedy approach of picking the first $k$ accomplishes that? $\endgroup$ – amoeba Jun 11 '14 at 16:17
  • $\begingroup$ Finding $N$ orthogonal linear combinations and then choosing the first most variant $k$ of them is what the process describes (loosely). My answer just claims that orthogonality is what is sufficient for the greedy process to achieve the goal of maximizing the total variance. $\endgroup$ – Innuo Jun 11 '14 at 16:26
  • $\begingroup$ I am not sure I follow the argument. How does the orthogonality matter? If you have $N$ variables and have to choose $k$ with highest total variance, you should pick $k$ with highest variance (irrespective of whether they are correlated or not). $\endgroup$ – amoeba Jun 11 '14 at 16:31
  • $\begingroup$ Ah, I understand the confusion. There was a typo in my answer. Fixed now. $\endgroup$ – Innuo Jun 11 '14 at 17:13
  • $\begingroup$ I think you might be on to something here, but the magical appearance of the sum needs explaining. What relevance does that have to PCA or even to spectral decompositions? $\endgroup$ – whuber Jun 11 '14 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.