Principal component analysis

Setup: variance along a direction

Given centered data points $x_1,\dots,x_n\in\mathbb{R}^d$ (mean already subtracted), stacked as rows of $X$, the sample covariance matrix is $C=\tfrac1n\sum_ix_ix_i^T=\tfrac1nX^TX$, symmetric and positive semidefinite.

Projecting each point onto a unit direction $v$ gives a scalar $x_i^Tv$; the variance of these projections is:

$$ \operatorname{Var}(v) = \tfrac1n\sum_i (x_i^Tv)^2 = v^TCv. $$

Intuition: $C$ packages how the data spreads out in every direction at once; $v^TCv$ reads off the spread along one particular direction $v$.

Shapes

$$ \underbrace{X}_{n\times d}=\begin{pmatrix}-\,x_1^T-\\-\,x_2^T-\\ \vdots\\-\,x_n^T-\end{pmatrix}, \qquad \underbrace{C}_{d\times d}=\tfrac1n\underbrace{X^T}_{d\times n}\,\underbrace{X}_{n\times d}, \qquad \underbrace{v^T}_{1\times d}\,\underbrace{C}_{d\times d}\,\underbrace{v}_{d\times 1}=\underbrace{\operatorname{Var}(v)}_{1\times1}. $$

Intuition: rows are samples, columns are features. $X^TX$ sums over the sample axis (the shared inner $n$ disappears), leaving a features-by-features table.

Example

Reusing $C=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ (our running matrix, eigenvalues $3,1$, eigenvectors $\tfrac1{\sqrt2}(1,1), \tfrac1{\sqrt2}(1,-1)$): along $v=(1,0)$, $v^TCv=2$. Along $v=\tfrac1{\sqrt2}(1,1)$: $Cv=3v$, so $v^TCv=3$, more spread.

Derivation 1: maximize variance directly

The first principal component is the unit direction capturing the most variance:

$$ v_1 = \operatorname*{arg\,max}_{\|v\|=1} v^TCv. $$

By the spectral theorem, $C=Q\Lambda Q^T$ with $\lambda_1\geq\cdots\geq\lambda_d\geq0$. Write $v=\sum_ic_iq_i$ in the eigenbasis, with $\sum_ic_i^2=1$ since $v$ is a unit vector:

$$ v^TCv = \sum_i\lambda_ic_i^2 \ \leq\ \lambda_1\sum_ic_i^2 = \lambda_1, $$

with equality exactly when $v=q_1$, the top eigenvector.

Intuition: a unit vector's variance is a weighted average of the eigenvalues; to make that average as large as possible, put all the weight on the biggest one.

Example

With $C$ above, every unit $v$ has $v^TCv=3c_1^2+c_2^2\leq3$, maximized at $c_1=1,c_2=0$, i.e. $v=\tfrac1{\sqrt2}(1,1)$: the same direction found by hand.

Derivation 2: constrained optimization

Same objective, via the Lagrangian tangency condition (from The Lagrangian and KKT conditions): maximize $f(v)=v^TCv$ subject to $g(v)=v^Tv-1=0$.

$$ \nabla f(v) = 2Cv, \quad \nabla g(v) = 2v, \quad \nabla f = \lambda\nabla g \ \ \Rightarrow\ \ Cv = \lambda v. $$

Stationary points are exactly the unit eigenvectors of $C$, and at a stationary point $v^TCv=\lambda v^Tv=\lambda$: the objective value is the eigenvalue itself, so maximizing picks out the largest one.

Intuition: "maximize variance on the unit sphere" and "find eigenvectors of $C$" are the same question; constrained optimization and the eigenvalue problem share their stationary points.

Example

$Cv=\lambda v$ gives $\lambda=3,v=\tfrac1{\sqrt2}(1,1)$ or $\lambda=1,v=\tfrac1{\sqrt2}(1,-1)$: the two stationary points, with $\lambda=3$ the maximum, matching Derivation 1 exactly.

Further components

The second component maximizes the same variance subject to the extra constraint $v\perp v_1$; the same argument, restricted to that orthogonal complement, gives the next eigenvector $v_2$ with eigenvalue $\lambda_2$. Repeating gives all $d$ components: the eigenvectors of $C$, ranked by eigenvalue.

Intuition: each new component grabs the most remaining variance, in a direction already perpendicular to everything claimed so far.

Connection to the SVD

If $X=U\Sigma V^T$ (from Singular value decomposition), then:

$$ C = \tfrac1nX^TX = \tfrac1nV\Sigma^2V^T. $$

So the principal components are exactly the columns of $V$ (the right singular vectors of $X$), and the variance captured by component $i$ is $\sigma_i^2/n$.

Intuition: PCA is the spectral theorem applied to $C$, which is secretly the SVD of $X$; nothing new, just a direct application of what's already there.

Dimensionality reduction: projecting down

Keep only the top $k<d$ components. Stack them as the columns of $V_k\in\mathbb{R}^{d\times k}$ (the first $k$ columns of $V$), and replace each $d$-dimensional point $x_i$ by its $k$ coordinates along them:

$$ z_i = V_k^Tx_i\in\mathbb{R}^k, \qquad Z = XV_k. $$

Shapes

$$ \underbrace{Z}_{n\times k}=\underbrace{X}_{n\times d}\ \underbrace{V_k}_{d\times k} =\begin{pmatrix}-\,x_1^T-\\ \vdots\\-\,x_n^T-\end{pmatrix} \begin{pmatrix}\vert&&\vert\\v_1&\cdots&v_k\\\vert&&\vert\end{pmatrix} =\begin{pmatrix}x_1^Tv_1&\cdots&x_1^Tv_k\\ \vdots&&\vdots\\x_n^Tv_1&\cdots&x_n^Tv_k\end{pmatrix}. $$

Entry $(i,j)$ is how far point $i$ sits along component $j$. The $n$ rows (samples) are untouched; only the feature axis shrinks from $d$ columns to $k$. In SVD terms, $Z=XV_k=U_k\Sigma_k$, i.e. $(n\times k)(k\times k)$.

Intuition: the same $n$ points, but each is now described by $k$ numbers instead of $d$: its coordinates in the best $k$-dimensional coordinate system for the data.

Reconstruction

To go back up to $\mathbb{R}^d$, map the coordinates through the same directions:

$$ \underbrace{\hat X}_{n\times d}=\underbrace{Z}_{n\times k}\ \underbrace{V_k^T}_{k\times d}=XV_kV_k^T, \qquad \hat x_i = \sum_{j=1}^k (x_i^Tv_j)\,v_j. $$

$V_kV_k^T\in\mathbb{R}^{d\times d}$ is exactly the projection matrix onto $\operatorname{span}(v_1,\dots,v_k)$ from Rank, subspaces, and projections: with $A=V_k$ orthonormal, $A^TA=I$ and $A(A^TA)^{-1}A^T$ collapses to $V_kV_k^T$. So $\hat X$ is an $n\times d$ matrix of rank at most $k$; it can be stored as $nk+kd$ numbers instead of $nd$. Expanding gives the Low-rank approximation sum:

$$ \hat X=\sum_{i=1}^k\sigma_iu_iv_i^T. $$

Intuition: compress ($d\to k$ coordinates), then decompress ($k\to d$); what comes back is each point's shadow on the $k$-dimensional subspace, with the discarded directions flattened to zero.

How much is kept

Each point splits into a kept part and a discarded part that are perpendicular, $x_i=\hat x_i+(x_i-\hat x_i)$, so Pythagoras applies: $\|x_i\|^2=\|\hat x_i\|^2+\|x_i-\hat x_i\|^2$. Averaging over the data, with $\operatorname{tr}(C)=\sum_i\lambda_i$ the total variance:

$$ \underbrace{\sum_{i=1}^d\lambda_i}_{\text{total variance}} =\underbrace{\sum_{i=1}^k\lambda_i}_{\text{kept}} +\underbrace{\sum_{i=k+1}^d\lambda_i}_{\text{lost} \,=\, \text{mean squared reconstruction error}}. $$

So the two goals of PCA, maximize the variance you keep and minimize the reconstruction error, are the same goal, and the top $k$ eigenvectors achieve both. The standard summary is the explained variance ratio:

$$ \text{explained variance}(k)=\frac{\lambda_1+\cdots+\lambda_k}{\lambda_1+\cdots+\lambda_d}=\frac{\sigma_1^2+\cdots+\sigma_k^2}{\sigma_1^2+\cdots+\sigma_d^2}. $$

The new features are also uncorrelated, since the covariance of $Z$ is diagonal:

$$ \underbrace{\tfrac1nZ^TZ}_{k\times k}=V_k^TCV_k=\Lambda_k=\begin{pmatrix}\lambda_1&&\\&\ddots&\\&&\lambda_k\end{pmatrix}. $$

Intuition: every unit of variance is either kept or lost, and the dropped eigenvalues are precisely the price you pay; uncorrelated columns mean no component's information overlaps another's.

Example: $2\to1$ dimensions

Take four centered points whose covariance is our running $C=\begin{pmatrix}2&1\\1&2\end{pmatrix}$, with $n=4,\ d=2,\ k=1$ and $v_1=\tfrac1{\sqrt2}(1,1)$:

$$ \underbrace{X}_{4\times2}=\begin{pmatrix}\sqrt3&\sqrt3\\-\sqrt3&-\sqrt3\\1&-1\\-1&1\end{pmatrix},\qquad \underbrace{Z}_{4\times1}=\underbrace{X}_{4\times2}\underbrace{v_1}_{2\times1}=\begin{pmatrix}\sqrt6\\-\sqrt6\\0\\0\end{pmatrix}. $$

Reconstruction $\hat X=Zv_1^T$ is $(4\times1)(1\times2)=4\times2$:

$$ \hat X=\begin{pmatrix}\sqrt6\\-\sqrt6\\0\\0\end{pmatrix}\tfrac1{\sqrt2}\begin{pmatrix}1&1\end{pmatrix} =\begin{pmatrix}\sqrt3&\sqrt3\\-\sqrt3&-\sqrt3\\0&0\\0&0\end{pmatrix}. $$

The first two points lie on PC1 and are recovered perfectly; the last two lie entirely along the discarded direction $v_2$, so they collapse to the origin.

Check the bookkeeping: variance of $Z$ is $\tfrac14(6+6+0+0)=3=\lambda_1$; mean squared reconstruction error is $\tfrac14(0+0+2+2)=1=\lambda_2$; explained variance is $\tfrac{3}{3+1}=75\%$. ✓

Choosing $k$ and practical notes

• Choosing $k$. Plot $\lambda_i$ against $i$ (a scree plot) and look for the elbow where eigenvalues flatten out, or take the smallest $k$ whose explained variance passes a threshold (say 90% or 95%), or pick $k$ by how well a downstream task performs.
• Center first. Subtract the mean from every column before anything else, and add it back when reconstructing: $\hat x_i=\bar x+V_kV_k^T(x_i-\bar x)$.
• Scale if units differ. Variance depends on units, so a feature measured in large units dominates the top components; standardize columns (unit variance) if the features are not comparable.
• Compute via the SVD of $X$, not by forming $C=\tfrac1nX^TX$: squaring $X$ squares its condition number and loses precision. At most $\min(n-1,d)$ components carry any variance.
• Limits. PCA is linear, and high variance is not the same as importance: a large-variance direction may be noise, and a small-variance one may be the signal you care about.

Intuition: PCA compresses data by keeping only the few directions that matter most, the same "keep the big singular values, drop the small ones" idea as SVD.