Introduction
Principal Component Analysis found the best single direction. In practice you keep directions: the eigenvectors of the largest eigenvalues of . This note builds the -dimensional transform, rebuilds the sample from it, shows that the error is exactly the sum of the dropped eigenvalues, and finds how many eigenvalues can be nonzero.
Main idea
$\mathbf{y}=\boldsymbol{\Phi}^T(\mathbf{x}-\boldsymbol{\mu})$ and $\hat{\mathbf{x}}=\boldsymbol{\Phi}\mathbf{y}+\boldsymbol{\mu}$, where $\boldsymbol{\Phi}$ holds the eigenvectors of the $m$ largest eigenvalues of $\mathbf{S}^t$. Each dropped direction loses its own variance, so $E[\|\Delta\|^2]=\sum_{k=m+1}^{n}\lambda_k$. With $q$ samples, $\mathbf{S}^t$ has at most $q-1$ nonzero eigenvalues, so $q-1$ dimensions already rebuild the training data with zero error.
Overview
The sizes, with dimensions, kept directions and :
goes down from to numbers, and goes back up from to .
Step 1: reduce to m dimensions
Sort the eigenvalues of from largest to smallest, , and keep the eigenvectors of the first :
How to read it:
- row of is , so entry of is , the coordinate along direction
- so is the one-direction projection of Principal Component Analysis, done times at once
- is symmetric, and the eigenvectors of a symmetric matrix can always be chosen orthonormal (perpendicular to each other and of unit length), so , and Eigen-Decomposition shows why
This is the famous principal component analysis (PCA) transform from -dimensional to -dimensional .
Why the top eigenvectors are the best directions:
- the goal is the same as for one direction: keep the most total variance, with each kept direction of unit length and perpendicular to the others
- the best first direction is , the best second direction perpendicular to it is , and so on, each adding the next largest variance
- Eigen-Decomposition writes this goal as one trace, and its answer is the eigenvectors of the largest eigenvalues
Step 2: reconstruct the sample
To rebuild the original -dimensional sample from the numbers, walk steps along each kept direction and add back the mean:
The second form comes from multiplying by column by column: column of times entry of .
Going down and back up in one line:
Why this is not a perfect rebuild:
- , but is with rank only , so when
- keeps the part of inside the kept directions and drops the rest, the -direction version of
- only with all eigenvectors is , and then
With these directions, the total reconstruction error is the smallest possible:
Step 3: error equals the dropped eigenvalues
The reconstruction error of one sample is (the index is dropped for short):
To find its size, use all eigenvectors. They are orthonormal directions in dimensions, so together they are a complete set of axes, and any centred sample is the sum of its pieces along them:
Explaining each step:
- the reconstruction keeps the first pieces, so the error is the rest:
- square it: , summing and from to
- is when and otherwise, so every cross term vanishes and
- write for the average over all training samples, then is the variance along , which is (eigenvalue is the variance, in Principal Component Analysis)
So the mean squared reconstruction error is:
where the are sorted in descending order. What this means:
- each dropped direction adds its own variance to the error
- dropping the smallest eigenvalues gives the smallest possible error, which is why PCA keeps the largest
- the total error over all samples is , because is the average and is the sum
Step 4: rank of the total scatter matrix
The rank of a matrix is its number of independent columns, which is the number of independent directions its outputs can point in. For a symmetric matrix it equals the number of nonzero eigenvalues, because (Eigen-Decomposition) only gives outputs along the eigenvectors with .
Why the rank is at most :
- is , so its rank is at most
- for any vector , is a weighted sum of the (each is a number), so the outputs of cannot cover more directions than the vectors span
- the centred samples add up to zero:
- so the last one is fixed by the others, , and the vectors span at most directions
So has at most nonzero eigenvalues. For example, 2 samples always lie on one line through their mean, and 3 samples always lie in one plane, even in a space of thousands of dimensions.
What follows when :
- the eigenvalues are all zero, so the data has no spread at all along their eigenvectors
- PCA with a -dimensional fully represents the original -dimensional training data, because every dropped eigenvalue is zero:
Why do we need this
It turns PCA into a recipe with a dial: choose , and the eigenvalues tell you exactly how much is lost. The rank result also warns that with few samples, most directions in a high-dimensional space contain no training data at all.
Next step
Eigen-Decomposition writes the whole covariance matrix in terms of its eigenvectors, and shows why the PCA features are uncorrelated.
Visual 1: error is the sum of dropped eigenvalues

How to read it:
- left: the eigenvalues of for , sorted from largest to smallest, with kept (blue) and 5 dropped (red)
- right, a 2-D case with : each sample is rebuilt as on the line, and the error (red) always points along the dropped axis
- so is the squared coordinate along , and its average over the samples is the spread along , which is
- with more dropped axes the error has one such piece per dropped axis, at right angles, so the mean squared error is , as in Step 3
Visual 2: why few samples give few directions

The cause behind the rank result of Step 4:
- left, : the two centred offsets are exact opposites, , so they point along one line even though the space is 2-D
- right, : laid tip to tail, the three offsets come back to the start, so adds no new direction
- this holds for any , because the offsets from the mean always add to zero, so samples span at most directions
- with samples in dimensions, only 5 directions hold any data, and the other 10 eigenvalues of are zero