Principal Component Analysis

Data with a thousand measurements is rarely a thousand independent things — the measurements move together. PCA finds the directions along which the data varies most and re-describes every point in terms of those, keeping only the few that matter. It is a change of basis, not a model: nothing is learned about any task, only about the shape of the data.

The principal directions are the top eigenvectors of the covariance matrix, equivalently the top right singular vectors of the centred data. It is linear, and among linear methods it is optimal — no other rank-k linear projection reconstructs with lower squared error. That optimality is also the limit: structure that is not a linear subspace is invisible to it, which is what the nonlinear methods exist for.

Centre X, take the SVD X = UΣVᵀ, project onto the first k columns of V. Variance captured is Σ sub _i≤k  σ sub _i ² / Σ sub _i  σ sub _i ², and the reconstruction is the best rank-k approximation in Frobenius norm — the Eckart-Young theorem, which is why PCA and truncated SVD are one operation with two names. Exact computation is Θ(nd·min(n,d)); randomised methods reach the top k in about Θ(nd·k).