PCA and image compression

Question

I have two questions related to principal component analysis (PCA):

1. How do you prove that the principal components matrix forms an orthonormal basis? Are the eigenvalues always orthogonal?

2. On the meaning of PCA. For my assignment, I have to compute the first 5 principal components for twenty-four $60 \times 50$ images. I've done that. But then it asks me to show those $5$ principal components as images and comment on what I see. I can see stuff, but I don't understand what is important about what I am seeing. Assuming I am doing everything right, what I should I be seeing/commenting on?

Answer 1

When computing the PCA of some matrix, the eigenvectors are orthogonal because we symmetrize the matrix during the process. In general, eigenvectors of a matrix are not necessarily orthogonal; however, this is a property that holds for symmetric matrices.

The singular value decomposition of a matrix $A$ can be written as

$$A = U \Sigma V^T$$

where $U$ and $V$ are orthonormal. In practice, we don't often compute this because of numerical issues.

Instead, we might look at $$A^TA = V\Sigma^T U^T U \Sigma V^T = V\Sigma^2 V^T.$$

Equivalently, if we look at $A^TA$ as a symmetric, diagonalizable matrix, we can compute its eigendecomposition as $A^TA = W\Lambda W^T$ and we know that the eigenvectors found in the columns of $W$ are orthogonal due to symmetry.

The link between SVD and PCA is recognizing that these are the same things.

Answer 2

You may have more luck at finding mathematical facts if you use the other name of PCA, which is SVD, singular value decomposition. Still another name for the same mathematical idea is Karhunen-Loeve transformation.

The properties of PCA that you asked about result from the properties of the spectral decomposition of symmetric matrices. They always have real eigenvalues, eigenspaces to different eigenvalues are orthogonal, inside an eigenspace an orthogonal basis of eigenvectors can be found, so that the transformation matrix can always be constructed to be orthogonal (orthonormal columns).

The first components should show common features of the images, like the average over all images.

Answer 3

The matrices coming from the PCA of $A$ are from the eigendecompositions of $A^TA$ and $AA^T$, and your question can be framed as a question about eigenvectors of real symmetric matrices.

Suppose that $v,w$ are two eigenvalues of $A=A^T$, with $Av=\lambda v, Aw=\mu w$. If $\mu\neq \lambda$, then simplifying $v^T (A w)=(Av)^Tw$ we have have $(\mu-\lambda)v^Tw =0$, and so $v^T w=0$. This shows that the different eigenspaces are orthogonal. Within any particular eigenspace, we can choose an orthonormal basis. Combining the orthonormal bases for each eigenspace, we have an orthonormal eigenbasis. Note that some choices were required, so the eigenbasis will not be unique, but that is fine.

As far as your second question, you have that the larger principal components of your matrix contain more of your original image, and so taking an image generated by using the first few principal components should give you a decent approximation, with the use of more components giving successively better approximations. The key insight is that it (hopefully) requires less data to generate these approximations than it takes to store the original image, so you can use PCA as a means of lossy image compression.

Answer 4

PCA was originally defined as a sequence of optimization problems in which the the components (the sequence of vectors that are the optima) are required to be mutually orthogonal. Every principal component is chosen, using the optimization criterion, from the subspace orthogonal to the previously determined components, so of course all components will be orthogonal to each other.

The reformulation as an algebra problem of finding eigenvectors of the covariance matrix came later, and amounts to the theory of Rayleigh quotients, or principal axes of ellipsoids. Pearson's founding article on PCA does not use eigenvalues.