Principal Component Analysis

Project onto the top covariance eigenvectors to compress data.

The idea

Principal component analysis finds the directions along which a dataset actually varies, so that a few coordinates describe the data instead of all of them. It works because data with many features is often less varied than its dimension suggests: measurements repeat one another, and the points sit near some lower-dimensional set inside the space.

The directions are read off the covariance matrix $\Sigma$ of the data, which records how the features vary and vary together; the unit eigenvectors of $\Sigma$ are the principal components.

Algorithm.

Algorithm: PCA Input: a dataset of points with d features, a target dimension k Output: the same points in k coordinates, keeping as much variance as k directions allow 1. center the data: subtract each feature's mean from that feature in every point 2. form the covariance matrix Σ of the centred data 3. compute the eigenvalues λ1 ≥ λ2 ≥ ... ≥ λd of Σ and their unit eigenvectors u1, ..., ud 4. keep the k components with the largest eigenvalues, discard the rest 5. return each centred point's dot products with u1, ..., uk // its coordinates in the kept components

Centering matters because the covariance should measure spread about the mean, not distance from an arbitrary zero. For any unit direction $u$, the variance of the centred data projected onto $u$ is $u^{\top}\Sigma u$, so the direction of greatest variance is the unit $u$ making $u^{\top}\Sigma u$ largest — the eigenvector of $\Sigma$ belonging to the largest eigenvalue, and that eigenvalue is the variance. Asking again among the directions orthogonal to those already taken picks off the remaining eigenvectors in order of eigenvalue. Since $\Sigma$ is symmetric, the components can be chosen mutually orthogonal, and their eigenvalues add up to the total variance. For a plane dataset this is visible in the scatter: an elongated cloud has its first component $u_{1}$ along the long axis, carrying the largest variance $\lambda_{1}$, and its second $u_{2}$ perpendicular to it, carrying the smaller $\lambda_{2}$.

Ways to work on it

• Walkthrough. Components as eigenvectors, eigenvalues as variance, keeping the top k.
• Practice. Fraction of variance explained by the first component.
• Hardest. Cumulative variance, centering, and orthogonality.

Not sure where to start? Take the ten-question placement test.