A Sampler of Useful Computational Tools for Applied Geometry, Computer Graphics, and Image Processing

62 PCA and SVD

of the scatter matrix is much smaller, as it is bounded by the

number of vectors that participate in the analysis, say N = 100,

and the principal components of the N vectors can be computed

with much less effort. Suppose our 16K × 100 matrix is denoted

by A. Instead of computing the PCA of the huge scatter matrix

of S = AA

>

, we can compute the PCA of A

>

A, which is much

smaller: a matrix of N × N elements (100 × 100 in our example

instead of 16K × 16K). Now, let us explain how.

Denote by v

i

the eigenvectors of the huge matrix AA

>

, and by

u

i

the eigenvectors of the small matrix A

>

A.

We have A

>

Au

i

= λ

i

u

i

. Multiplying both sides of the equation ...