Principal components analysis (PCA)

PCA is a lossy compression method you can derive with nothing but this chapter’s linear algebra. Each point x ∈ ℝⁿ gets a shorter code c ∈ ℝˡ, with l < n. Decoding is a matrix product, g(c) = Dc, where D ∈ ℝⁿˣˡ has columns that are orthogonal to each other and of unit norm.

Minimizing the squared L² distance between x and its reconstruction gives a very cheap encoder: c = Dᵀx. The full round trip is r(x) = DDᵀx.

To choose D for a whole dataset X (one example per row), minimize the Frobenius norm of the reconstruction errors. The first principal component turns out to be the eigenvector of XᵀX with the largest eigenvalue; with l components, D holds the eigenvectors of the l largest eigenvalues.