PCA and SVD

Concept: PCA and SVD

Core Intuition

PCA identifies the most meaningful basis to re-express data by maximizing the signal-to-noise ratio (SNR): ${\sigma }_{signal}^2/{\sigma }_{noise}^2$.

• Maximize signal: measured by variance magnitude; large variance encodes interesting structure.
• Minimize redundancy (noise): measured by covariance magnitude.

Mathematical Foundation

Setup

Let the observed data be

$$\underset{(m\times n)}{X}=\{x_{ij}\}=\left[\begin{array}{ccc}{x}_{11}& \cdots & x_{1n}\\ ⋮& & ⋮\\ x_{m1}& \cdots & x_{mn}\end{array}\right]=\left[\begin{array}{c}{x}_{1.}^T\\ ⋮\\ x_{m.}^T\end{array}\right]=[x_{.1},\cdots ,x_{.n}]$$

where each row $x_{i.}^T$ represents an example on $n$-dimensional features:

$$x_{i.}^T=[x_{i1}\dots x_{in}]$$

For notation simplicity, we also denote each row $x_{i.}^T$ by $x_i^T$. Each column

$$x_{.j}=\left[\begin{array}{c}{x}_{1j}\\ ⋮\\ x_{mj}\end{array}\right]$$

is normalized to zero mean $E(x_{.j})=0$ and unit variance $\text{Var}(x_{.j})=1$.

The covariance matrix of $X$ is

$$\underset{(n\times n)}{{\Sigma }_X}=\frac{1}{m}{X}^{T}X=\frac{1}{m}\left[\begin{array}{c}{x}_{.1}^T\\ ⋮\\ x_{.n}^T\end{array}\right][x_{.1},\dots ,x_{.n}]=\frac{1}{m}\left[\begin{array}{ccc}{x}_{.1}^T{x}_{.1}& \cdots & x_{.1}^T{x}_{.n}\\ ⋮& & ⋮\\ x_{.n}^T{x}_{.1}& \cdots & x_{.n}^T{x}_{.n}\end{array}\right]$$

Goal: find $Y=f(X)$ such that the covariance of $Y$ is a diagonal matrix,

$$\underset{(n\times n)}{{\Sigma }_Y}=\frac{1}{m}{Y}^{T}Y$$

PCA Assumptions

• Linear transformation: let $\underset{n\times n}{E}=[e_1,\dots ,e_n]$,

$$Y=XE$$

• Large variance encodes important structure.
• Principal components are orthogonal.

The last assumption provides an intuitive simplification that makes PCA soluble with linear algebra decomposition techniques.

Eigendecomposition

Suppose $Y=XE$. Its covariance matrix is

$${\Sigma }_Y=\frac{1}{m}{Y}^{T}Y=\frac{1}{m}(XE{)}^T(XE)=E^T\left(\frac{1}{m}{X}^{T}X\right)E$$

Since $\frac{1}{m}{X}^{T}X$ is symmetric, it admits the spectral decomposition:

$$\frac{1}{m}{X}^{T}X=VD{V}^T$$

where $D=\text{diag}(d_1,\dots ,d_n)$ with $d_1\ge \cdots \ge d_n$, and $V=[v_1,\dots ,v_n]$ has orthonormal columns ($V^{T}V=V{V}^T=I$).

Sketch of proof: From the spectral decomposition, for all $j$:

$$\frac{1}{m}{X}^{T}X{v}_j=d_j{v}_j$$

Then $\frac{1}{m}{X}^{T}XV=VD$, which implies $\frac{1}{m}{X}^{T}X=VD{V}^T$.

Choosing $E=V$:

$${\Sigma }_Y=E^T\left(\frac{1}{m}{X}^{T}X\right)E=V^T(VD{V}^T)V=D$$

The eigenvalue $d_j$ is the variance of projected feature $y_j$.

Alternative derivation via Lagrangian: PCA finds a unit vector $u$ (with $\Vert u\Vert =1$) maximizing the variance of the projection of all examples $x_i$ onto $u$:

$$\frac{1}{m}\sum _{i=1}^m(x_i^{T}u{)}^2=\frac{1}{m}\sum _{i=1}^m(x_i^{T}u{)}^T(x_i^{T}u)=u^T\left(\frac{1}{m}\sum _{i=1}^m{x}_i{x}_i^T\right)u$$

Why does the variance take this form? If the angle between $x_i$ and $u$ is $\theta$, the projection of $x_i$ onto $u$ is

$$x_i^{\prime }=x_i\cos \theta =x_i\frac{x_i^{T}u}{|x_i||u|}=x_i\frac{x_i^{T}u}{|x_i|}$$

since $u$ is a unit vector. The length of this projection is

$${\left[x_i^{\prime T}{x}_i^{\prime }\right]}^{1/2}={\left[{\left(x_i\frac{x_i^{T}u}{|x_i|}\right)}^T\left(x_i\frac{x_i^{T}u}{|x_i|}\right)\right]}^{1/2}={\left[\left(\frac{x_i^{T}u}{|x_i|}\right)x_i^T{x}_i\left(\frac{x_i^{T}u}{|x_i|}\right)\right]}^{1/2}={\left[{\left(x_i^{T}u\right)}^2\right]}^{1/2}=x_i^{T}u$$

since $x_i^T{x}_i=\Vert x_i{\Vert }^2$. So the projection distance from the origin is $x_i^{T}u$.

The optimization problem is then

$$\underset{u}{\max }{u}^T\left(\frac{1}{m}\sum _{i=1}^m{x}_i{x}_i^T\right)u\text{s.t. }{u}^{T}u=1$$

Using Lagrange multipliers:

$$\underset{u}{\max }L(u,d)=u^T\left(\frac{1}{m}{X}^{T}X\right)u-d(u^{T}u-1)$$

Taking the partial derivative with respect to $u$ and setting to zero:

$$\frac{\partial }{\partial u}L(u,d)=\frac{1}{m}{X}^{T}Xu-du=0$$

Hence $\frac{1}{m}{X}^{T}Xu=du$, recovering the eigenvector equation.

SVD

Recall $\frac{1}{m}{X}^{T}X{v}_j=d_j{v}_j$. Define:

• Singular values: ${\lambda }_j=\sqrt{d_j}$ for $j=1,\dots ,n$.
• Left singular vectors $U=[u_1,\dots ,u_n]$ with

$$u_j=\frac{1}{{\lambda }_j}\left(\frac{1}{\sqrt{m}}X\right)v_j$$

Then:

• (1) $U$ is orthonormal: $u_i^T{u}_j=\{\begin{array}{ll}1,& i=j\\ 0,& \text{otherwise}\end{array}$
• (2) $\Vert X{v}_i\Vert ={\lambda }_i$

Sketch of proof:

$$u_i^T{u}_j=\frac{1}{m}{\left(\frac{1}{{\lambda }_i}X{v}_i\right)}^T\left(\frac{1}{{\lambda }_j}X{v}_j\right)=\frac{1}{{\lambda }_i{\lambda }_j}{v}_i^T\frac{1}{m}{X}^{T}X{v}_j=\frac{1}{{\lambda }_i{\lambda }_j}{v}_i^T{d}_j{v}_j=\frac{{\lambda }_j}{{\lambda }_i}{v}_i^T{v}_j$$

The first result follows from $v_i^T{v}_j=1[i=j]$. The second follows similarly.

By rewriting the definition of $u_j$:

$$\left(\frac{1}{\sqrt{m}}X\right)v_j={\lambda }_j{u}_j$$

That is, normalized $X$ multiplied by eigenvector $v_j$ of $\frac{1}{m}{X}^{T}X$ equals scalar ${\lambda }_j$ times $u_j$.

Matrix Version of SVD

Constructing $\Sigma =\text{diag}({\lambda }_1,\dots ,{\lambda }_n)$ with ${\lambda }_1\ge \cdots \ge {\lambda }_n$, and stacking columns $V=[v_1,\dots ,v_n]$, $U=[u_1,\dots ,u_n]$:

$$\left(\frac{1}{\sqrt{m}}X\right)V=U\Sigma ⟹\frac{1}{\sqrt{m}}X=U\Sigma V^T$$

Any matrix $\frac{1}{\sqrt{m}}X$ decomposes into:

• Rotation: $V^T$
• Stretch: $\Sigma$
• Second rotation: $U$

Connection Between PCA and SVD

$$\frac{1}{m}{X}^{T}X={\left(\frac{1}{\sqrt{m}}X\right)}^T\left(\frac{1}{\sqrt{m}}X\right)={\left(U\Sigma V^T\right)}^T\left(U\Sigma V^T\right)=V\Sigma U^{T}U\Sigma V^T=V{\Sigma }^2{V}^T\equiv VD{V}^T$$

Squared singular values equal PCA variances: ${\lambda }_j^2=d_j$.

How Many Principal Components to Use

Total variance: ${\sum }_{j=1}^n{\lambda }_j^2$.

Scree plot: choose the number of principal components by the elbow method.

Reduced Rank Approximation by SVD

From SVD:

$$\frac{1}{\sqrt{m}}X=U\Sigma V^T=\sum _{j=1}^n{\lambda }_j{u}_j{v}_j^T$$

Let $s<n=\text{rank}(X)$. The reduced rank-$s$ least-squares approximation is

$$\frac{1}{\sqrt{m}}\hat{X}=\sum _{j=1}^s{\lambda }_j{u}_j{v}_j^T$$

which minimizes the Frobenius norm

$$\frac{1}{m}\sum _{i=1}^m\sum _{j=1}^n{\left(x_{ij}-{\hat{x}}_{ij}\right)}^2=\text{tr}\left[\left(\frac{1}{\sqrt{m}}(X-\hat{X})\right){\left(\frac{1}{\sqrt{m}}(X-\hat{X})\right)}^T\right]$$

over all matrices $\hat{X}$ of rank no greater than $s$ (Eckart-Young theorem).

PCA Algorithm Summary

1. Standardize each feature: $x_j\leftarrow (x_j-{\bar{x}}_j)/{\sigma }_j$
2. Compute eigenvectors of ${\Sigma }_X=\frac{1}{m}{X}^{T}X$
3. The $i$-th principal component is $v_i$; its explained variance is $d_i$
4. Select number of components $s$ via scree plot (elbow on $\{{\lambda }_j^2\}$); total variance is ${\sum }_j{\lambda }_j^2$

Key Equation

$$\frac{1}{m}{X}^{T}X=VD{V}^T\text{(eigendecomposition / PCA)}$$ $$\frac{1}{\sqrt{m}}X=U\Sigma V^T\text{(SVD)}$$ $$\frac{1}{\sqrt{m}}\hat{X}=\sum _{j=1}^s{\lambda }_j{u}_j{v}_j^T\text{(rank-}s\text{ approximation, Eckart-Young)}$$

Analogy

PCA is like finding the natural axes of an ellipse fitted to a point cloud: the major axis captures the most spread (highest variance), the minor axis captures the least. SVD is the same operation written in terms of the data matrix directly rather than its covariance.

Component of

• Dimensionality Reduction todo
• Singular Value Decomposition todo

Insights

• SVD and PCA are two views of the same decomposition: ${\lambda }_j^2=d_j$.
• Rank-$s$ SVD is the optimal least-squares approximation to $X$ (Eckart-Young theorem).
• PCA is scale-sensitive: normalization is mandatory before computing the covariance.

Pitfalls

• PCA assumes linear structure; nonlinear geometry requires Kernel PCA or manifold methods.
• PCA is sensitive to outliers since covariance is not robust.

Connections

• Correspondence Analysis: generalized SVD applied to categorical count data.
• Kernel PCA todo
• Eckart-Young Theorem todo

Implementation Notes

• Prefer np.linalg.svd over explicit eigendecomposition for numerical stability.
• For large $n$, use randomized SVD (e.g., sklearn.utils.extmath.randomized_svd) to avoid the $O(n^3)$ cost.

References

[1] Shlens (arXiv, 2014). A Tutorial on Principal Component Analysis. [2] Johnson & Wichern (2002). Applied Multivariate Statistical Analysis.