PCA via eigendecomposition and SVD

Why PCA Matters

The Problem: Real data lives in high dimensions (thousands of features), but most variation happens in a lower-dimensional subspace. We want to:

• Compress data (fewer dimensions → less storage, faster computation)
• Visualize high-D data in 2D/3D
• Denoise by keeping signal, dropping noise dimensions
• Decorelate features for downstream algorithms

The Solution: Find orthogonal directions (principal components) ordered by how much variance they capture.

Method 1: Eigendecomposition of Covariance Matrix

Step 1: Center the Data

Start with data matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$ (n samples, d features).

$\mathbf{X}_{\text{centered}} = \mathbf{X} - \mathbf{1}_n \boldsymbol{\mu}^T$

where $\boldsymbol{\mu} = \frac{1}{n}\sum_{i=1}^n \mathbf{x}_i$ is the mean vector.

WHY? PCA finds directions of variance. Variance is measured from the mean, so we must center first. Without centering, the first PC would just point toward the mean from the origin—useless.

Step 2: Compute Covariance Matrix

$\mathbf{C} = \frac{1}{n-1}\mathbf{X}_{\text{centered}}^T \mathbf{X}_{\text{centered}}$

WHY divide by $n-1$? Bessel's correction for unbiased variance estimation (1 degree of freedom lost to the mean).

Step 3: Eigendecomposition

Solve the eigenvalue problem:

$\mathbf{C}\mathbf{v}_i = \lambda_i \mathbf{v}_i$

This gives $d$ eigenvectors $\mathbf{v}_1, \ldots, \mathbf{v}_d$ and eigenvalues $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_d \geq 0$.

WHY eigenvalues = variance? Consider projecting centered data onto unit vector $\mathbf{w}$:

$\text{Var}(\mathbf{X}_{\text{centered}}\mathbf{w}) = \frac{1}{n-1}\|\mathbf{X}_{\text{centered}}\mathbf{w}\|^2 = \mathbf{w}^T\mathbf{C}\mathbf{w}$

We want to maximize this subject to $\|\mathbf{w}\|=1$. Using Lagrange multipliers:

$\mathcal{L} = \mathbf{w}^T\mathbf{C}\mathbf{w} - \lambda(\mathbf{w}^T\mathbf{w} - 1)$

Taking derivative w.r.t. $\mathbf{w}$ and setting to zero:

$\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = 2\mathbf{C}\mathbf{w} - 2\lambda\mathbf{w} = 0 \implies \mathbf{C}\mathbf{w} = \lambda\mathbf{w}$

So $\mathbf{w}$ must be an eigenvector! Substituting back: $\text{Var} = \mathbf{w}^T\mathbf{C}\mathbf{w} = \lambda\mathbf{w}^T\mathbf{w} = \lambda$. The eigenvalue is the variance along that direction.

Step 4: Project Data

To reduce to $k$ dimensions, project onto the top $k$ eigenvectors:

$\mathbf{Z} = \mathbf{X}_{\text{centered}}\mathbf{V}_k$

where $\mathbf{V}_k = [\mathbf{v}_1 \mid \mathbf{v}_2 \mid \ldots \mid \mathbf{v}_k] \in \mathbb{R}^{d \times k}$.

Result: $\mathbf{Z} \in \mathbb{R}^{n \times k}$ is the low-dimensional representation.

Method 2: Singular Value Decomposition (SVD)

Any matrix can be decomposed as:

$\mathbf{X}_{\text{centered}} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$

where:

• $\mathbf{U} \in \mathbb{R}^{n \times n}$ is orthogonal (left singular vectors)
• $\boldsymbol{\Sigma} \in \mathbb{R}^{n \times d}$ is diagonal with singular values $\sigma_1 \geq \sigma_2 \geq \ldots \geq 0$
• $\mathbf{V} \in \mathbb{R}^{d \times d}$ is orthogonal (right singular vectors)

Connection to Eigendecomposition

Start with the covariance matrix:

$\mathbf{C} = \frac{1}{n-1}\mathbf{X}_{\text{centered}}^T\mathbf{X}_{\text{centered}}$

Substitute $\mathbf{X}_{\text{centered}} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$:

$\mathbf{C} = \frac{1}{n-1}(\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T)^T(\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T) = \frac{1}{n-1}\mathbf{V}\boldsymbol{\Sigma}^T\mathbf{U}^T\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$

Since $\mathbf{U}^T\mathbf{U} = \mathbf{I}$:

$\mathbf{C} = \frac{1}{n-1}\mathbf{V}\boldsymbol{\Sigma}^T\boldsymbol{\Sigma}\mathbf{V}^T = \mathbf{V}\left(\frac{\boldsymbol{\Sigma}^T\boldsymbol{\Sigma}}{n-1}\right)\mathbf{V}^T$

This is the eigendecomposition of $\mathbf{C}$! The eigenvectors are the columns of $\mathbf{V}$, and:

The singular values squared (divided by $n-1$) give the eigenvalues.

WHY use SVD?

1. Numerical stability: Covariance matrix can be ill-conditioned; SVD avoids forming it
2. Efficiency: For $n \ll d$ (many features, few samples), SVD is faster
3. Direct interpretation: $\mathbf{U}$ gives sample projections, $\mathbf{V}$ gives feature loadings

SVD-Based PCA Algorithm

1. Center the data: X_centered = X - mean(X, axis=0)
2. Compute SVD: U, Σ, V^T = SVD(X_centered)
3. Principal components: V (columns are PCs)
4. Eigenvalues: λ_i = σ_i² / (n-1)
5. Project to k dimensions: Z = X_centered @ V[:, :k]

Alternatively, use $\mathbf{U}\boldsymbol{\Sigma}$: the first $k$ columns of $\mathbf{U}\boldsymbol{\Sigma}$ give the same projection.

Step 1: Center Mean: $\boldsymbol{\mu} = [3, 5.2]^T$

$\mathbf{X}_{\text{centered}} = \begin{bmatrix} -2 & -3.2 \\ -1 & -1.2 \\ 0 & -0.2 \\ 1 & 1.8 \\ 2 & 2.8 \end{bmatrix}$

Step 2: Covariance $\mathbf{C} = \frac{1}{4}\mathbf{X}_{\text{centered}}^T\mathbf{X}_{\text{centered}} = \begin{bmatrix} 2.5 & 3.75 \\ 3.75 & 5.7 \end{bmatrix}$

Why this step? We're computing how much each feature varies and co-varies.

Step 3: Eigendecomposition Solve $\det(\mathbf{C} - \lambda\mathbf{I}) = 0$:

$(2.5-\lambda)(5.7-\lambda) - 3.75^2 = 0$ $\lambda^2 - 8.2\lambda + 0.1875 = 0$

Using quadratic formula: $\lambda_1 \approx 8.18, \quad \lambda_2 \approx 0.02$

Why this step? We're finding which directions capture the most variance. $\lambda_1$ captures 99.8% of variance!

Eigenvector for $\lambda_1$: $\mathbf{v}_1 \approx [0.56, 0.83]^T$ (points along the elongated direction).

Step 4: Project to 1D $\mathbf{Z} = \mathbf{X}_{\text{centered}}\mathbf{v}_1 \approx [-3.8, -1.6, -0.2, 2.1, 3.5]^T$

Interpretation: These 5 values summarize the original 2D data with minimal information loss (99.8% variance retained).

$\mathbf{X}_{\text{centered}} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$

Singular values: $\sigma_1 \approx 5.72$, $\sigma_2 \approx 0.28$

Check eigenvalue connection: $\lambda_1 = \frac{\sigma_1^2}{n-1} = \frac{32.72}{4} = 8.18 \quad \checkmark$

Right singular vectors (columns of $\mathbf{V}$) are the principal components: $\mathbf{v}_1 \approx [0.56, 0.83]^T$ — same as eigendecomposition!

Why this works? SVD factors the data matrix itself; the right singular vectors automatically point in the maximum-variance directions.

Variance Explained

$\text{EVR}_k = \frac{\sum_{i=1}^k \lambda_i}{\sum_{i=1}^d \lambda_i}$

Practical use: Choose $k$ such that $\text{EVR}_k \geq 0.95$ (retain 95% of information).

Total variance: $10.5 + 3.2 + 0.8 + 0.3 + 0.2 = 15$

Decision: Use $k=3$ to retain 97% of variance (compress from 5D to 3D).

Common Mistakes

Why it feels right: "PCA is just eigendecomposition of the covariance matrix—why preprocess?"

The problem: Without centering, the first PC points from the origin to the data cloud's center (capturing location, not spread). You want variance around the mean, not from the origin.

The fix: Always center: X_centered = X - X.mean(axis=0). Standardizing (dividing by std) is optional but recommended if features have different units.

Why it feels right: "Bigger singular value = more important dimension."

The problem: Singular values scale with data magnitude and sample size. Eigenvalues have a specific interpretation as variance.

The fix: Convert correctly: $\lambda_i = \frac{\sigma_i^2}{n-1}$. Or use explained variance ratio: $\frac{\sigma_i^2}{\sum_j \sigma_j^2}$.

Why it feels right: "PCA is dimensionality reduction—should work on any data."

The problem: PCA finds the best linear subspace. For non-linear structure (Swiss roll, circular clusters), linear projections destroy the geometry.

The fix: Use kernel PCA (implicitly maps to higher-D where structure is linear) or manifold learning methods (t-SNE, UMAP, Isomap).

Computational Complexity

| Method | Time Complexity | Space | Best When | |--------|-------------|--------| | Eigendecomposition of $\mathbf{C}$ | $O(d^2 n + d^3)$ | $O(d^2)$ | $d \ll n$ (few features) | | SVD of $\mathbf{X}$ | $O(\min(nd^2, n^2 d))$ | $O(nd)$ | $n \ll d$ (few samples) | | Randomized SVD | $O(nd k)$ | $O(nk)$ | $k \ll d$, very large $d$ |

Practical tip: For $d >10{,}000$, use randomized/truncated SVD (e.g., sklearn.decomposition.PCA with svd_solver='randomized').

Here's how: You have a big spreadsheet of firefly positions (maybe 1000 dimensions—each firefly's brightness, position, speed etc.). PCA finds the "most interesting" directions—the ones where the data spreads out the most. Then you throw away the boring directions (where everything looks the same) and keep only 2-3 important ones. Now you can draw the cloud on paper!

The eigendecomposition way asks: "Which direction has the biggest variance?" It looks at how data points differ from the average and finds that direction mathematically (eigenvector of the covariance matrix).

The SVD way asks: "How can I break down the data itself into simple pieces?" It factors the data like $2 \times 3 = 6$—but for giant matrices. Turns out, the pieces tell you the same important directions!

Both methods give you the same answer: here are your 2-3 magic camera angles. Compress your data, visualize it, and you're done!

SVP for SVD PCA:

• SVD decomposition of centered X
• V matrix = principal components
• Variance = sigma² / (n-1)
• Project: Z = XV_k

Connections

• 2.5.07-K-Means-Clustering - PCA often used as preprocessing to speed up clustering
• 2.5.01-Introduction-to-Unsupervised-Learning - PCA is a foundational unsupervised technique
• 2.4.03-Feature-Scalingand-Normalization - Standardization before PCA equalizes feature importance
• 3.2.05-Autoencoders - Non-linear generalization of PCA using neural networks
• Linear-Algebra-Eigenvalues-and-Eigenvectors - Mathematical foundation of eigendecomposition
• Linear-Algebra-SVD - SVD theory and applications beyond PCA
• 2.6.04-Kernel-PCA - PCA extended to non-linear data

#flashcards/ai-ml

What does PCA stand for and what does it do? :: Principal Component Analysis finds orthogonal directions in data ordered by variance, enabling dimensionality reduction while preserving maximum information.

Concept Map

Hinglish (regional understanding)