PCA via eigendecomposition and SVD

2.5.9 · AI-ML › Unsupervised Learning

PCA Kyun Zaroori Hai

Problem: Real data high dimensions mein rehta hai (hazaron features), lekin zyada variation ek lower-dimensional subspace mein hoti hai. Hum chahte hain:

• Compress karna data ko (kam dimensions → kam storage, faster computation)
• Visualize karna high-D data ko 2D/3D mein
• Denoise karna — signal rakhke, noise dimensions hatake
• Decorrelate karna features ko downstream algorithms ke liye

Solution: Orthogonal directions (principal components) dhundho jo kitna variance capture karte hain usi order mein arrange hon.

Method 1: Covariance Matrix ka Eigendecomposition

Step 1: Data ko Center Karo

Data matrix $\mathbf{X}\in {\mathbb{R}}^{n\times d}$ se shuru karo (n samples, d features).

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

jahaan $\mathbf{\mu }=\frac{1}{n}{\sum }_{i=1}^n{\mathbf{x}}_i$ mean vector hai.

KYUN? PCA variance ki directions dhundta hai. Variance mean se measure hoti hai, isliye pehle center karna zaroori hai. Center kiye bina, pehla PC sirf origin se data cloud ke center ki taraf point karega — jo kisi kaam ka nahi.

Step 2: Covariance Matrix Compute Karo

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

$n-1$ se divide kyun karte hain? Bessel's correction — unbiased variance estimation ke liye (1 degree of freedom mean ke liye lost hoti hai).

Step 3: Eigendecomposition

Eigenvalue problem solve karo:

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

Isse $d$ eigenvectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_d$ aur eigenvalues ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_d\ge 0$ milte hain.

Eigenvalues = variance kyun? Socho centered data ko unit vector $\mathbf{w}$ par project karna:

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

Hum isko maximize karna chahte hain $\Vert \mathbf{w}\Vert =1$ subject to. Lagrange multipliers use karke:

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

$\mathbf{w}$ ke w.r.t. derivative leke zero set karo:

$\frac{\partial \mathcal{L}}{\partial \mathbf{w}}=2\mathbf{Cw}-2\lambda \mathbf{w}=0⟹\mathbf{Cw}=\lambda \mathbf{w}$

Toh $\mathbf{w}$ ek eigenvector hona chahiye! Wapas substitute karne par: $\text{Var}={\mathbf{w}}^T\mathbf{Cw}=\lambda {\mathbf{w}}^T\mathbf{w}=\lambda$. Eigenvalue hi us direction ki variance hai.

Step 4: Data Project Karo

$k$ dimensions mein reduce karne ke liye, top $k$ eigenvectors par project karo:

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

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

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

Method 2: Singular Value Decomposition (SVD)

Koi bhi matrix aise decompose ho sakti hai:

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

jahaan:

• $\mathbf{U}\in {\mathbb{R}}^{n\times n}$ orthogonal hai (left singular vectors)
• $\mathbf{\Sigma }\in {\mathbb{R}}^{n\times d}$ diagonal hai singular values ${\sigma }_1\ge {\sigma }_2\ge \dots \ge 0$ ke saath
• $\mathbf{V}\in {\mathbb{R}}^{d\times d}$ orthogonal hai (right singular vectors)

Eigendecomposition se Connection

Covariance matrix se shuru karo:

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

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

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

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

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

Yeh $\mathbf{C}$ ka eigendecomposition hai! Eigenvectors $\mathbf{V}$ ke columns hain, aur:

Singular values squared ($n-1$ se divide karke) eigenvalues dete hain.

SVD kyun use karein?

1. Numerical stability: Covariance matrix ill-conditioned ho sakti hai; SVD usse form karne se bachata hai
2. Efficiency: Jab $n\ll d$ (zyada features, kam samples), SVD faster hai
3. Direct interpretation: $\mathbf{U}$ sample projections deta hai, $\mathbf{V}$ feature loadings deta hai

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, $\mathbf{U}\mathbf{\Sigma }$ use karo: $\mathbf{U}\mathbf{\Sigma }$ ke pehle $k$ columns same projection dete hain.

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

${\mathbf{X}}_{\text{centered}}=\left[\begin{array}{cc}-2& -3.2\\ -1& -1.2\\ 0& -0.2\\ 1& 1.8\\ 2& 2.8\end{array}\right]$

Step 2: Covariance $\mathbf{C}=\frac{1}{4}{\mathbf{X}}_{\text{centered}}^T{\mathbf{X}}_{\text{centered}}=\left[\begin{array}{cc}2.5& 3.75\\ 3.75& 5.7\end{array}\right]$

Yeh step kyun? Hum compute kar rahe hain ki har feature kitna vary aur co-vary karta hai.

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

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

Quadratic formula use karke: ${\lambda }_1\approx 8.18,{\lambda }_2\approx 0.02$

Yeh step kyun? Hum dhundh rahe hain ki kaun si directions sabse zyada variance capture karti hain. ${\lambda }_1$ 99.8% variance capture karta hai!

${\lambda }_1$ ka Eigenvector: ${\mathbf{v}}_1\approx [0.56,0.83{]}^T$ (elongated direction ki taraf point karta hai).

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

Interpretation: Yeh 5 values original 2D data ko minimal information loss ke saath summarize karti hain (99.8% variance retain hai).

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

Singular values: ${\sigma }_1\approx 5.72$, ${\sigma }_2\approx 0.28$

Eigenvalue connection check karo: ${\lambda }_1=\frac{{\sigma }_1^2}{n-1}=\frac{32.72}{4}=8.18✓$

Right singular vectors ($\mathbf{V}$ ke columns) principal components hain: ${\mathbf{v}}_1\approx [0.56,0.83{]}^T$ — eigendecomposition jaisa hi!

Yeh kyun kaam karta hai? SVD data matrix ko hi factor karta hai; right singular vectors automatically maximum-variance directions ki taraf point karte hain.

Variance Explained

${\text{EVR}}_k=\frac{{\sum }_{i=1}^k{\lambda }_i}{{\sum }_{i=1}^d{\lambda }_i}$

Practical use: $k$ aise choose karo ki ${\text{EVR}}_k\ge 0.95$ (95% information retain ho).

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

Decision: $k=3$ use karo 97% variance retain karne ke liye (5D se 3D compress karo).

Common Mistakes

Kyun sahi lagta hai: "PCA toh sirf covariance matrix ka eigendecomposition hai — preprocessing kyun karein?"

Problem: Center kiye bina, pehla PC origin se data cloud ke center ki taraf point karta hai (location capture karta hai, spread nahi). Tumhe variance mean ke around chahiye, origin se nahi.

Fix: Hamesha center karo: X_centered = X - X.mean(axis=0). Standardize karna (std se divide karna) optional hai lekin recommend kiya jaata hai agar features alag-alag units mein hain.

Kyun sahi lagta hai: "Bada singular value = zyada important dimension."

Problem: Singular values data magnitude aur sample size ke saath scale karte hain. Eigenvalues ki ek specific interpretation hai — variance ke roop mein.

Fix: Sahi convert karo: ${\lambda }_i=\frac{{\sigma }_i^2}{n-1}$. Ya explained variance ratio use karo: $\frac{{\sigma }_i^2}{{\sum }_j{\sigma }_j^2}$.

Kyun sahi lagta hai: "PCA dimensionality reduction hai — kisi bhi data par kaam karna chahiye."

Problem: PCA sabse best linear subspace dhundta hai. Non-linear structure (Swiss roll, circular clusters) ke liye, linear projections geometry destroy kar dete hain.

Fix: Kernel PCA use karo (implicitly higher-D mein map karta hai jahaan structure linear hai) ya 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$ (kam features) | | SVD of $\mathbf{X}$ | $O(\min (n{d}^2,n^{2}d))$ | $O(nd)$ | $n\ll d$ (kam samples) | | Randomized SVD | $O(ndk)$ | $O(nk)$ | $k\ll d$, bahut bada $d$ |

Practical tip: $d>10,000$ ke liye, randomized/truncated SVD use karo (jaise sklearn.decomposition.PCA with svd_solver='randomized').

Yeh dekho: Tumhare paas firefly positions ka ek bada spreadsheet hai (shayad 1000 dimensions — har firefly ki brightness, position, speed, etc.). PCA "sabse interesting" directions dhundta hai — wo jinmein data sabse zyada spread hota hai. Phir boring directions (jahaan sab ek jaisa dikhta hai) hata dete hain aur sirf 2-3 important directions rakhte hain. Ab tum cloud ko paper par draw kar sakte ho!

Eigendecomposition wala tarika poochhta hai: "Kis direction mein sabse zyada variance hai?" Yeh dekhta hai ki data points average se kaise differ karte hain aur mathematically wo direction dhundta hai (covariance matrix ka eigenvector).

SVD wala tarika poochhta hai: "Main data ko simple pieces mein kaise tod sakta hoon?" Yeh data ko $2\times 3=6$ ki tarah factor karta hai — lekin giant matrices ke liye. Pata chalta hai, yeh pieces wahi important directions batate hain!

Dono methods same answer dete hain: yeh rahi tumhari 2-3 magic camera angles. Data compress karo, visualize karo, aur kaam khatam!

SVD PCA ke liye SVP:

• 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 aksar preprocessing ke taur par use hota hai clustering speed up karne ke liye
• 2.5.01-Introduction-to-Unsupervised-Learning - PCA ek foundational unsupervised technique hai
• 2.4.03-Feature-Scalingand-Normalization - PCA se pehle standardization feature importance equalize karta hai
• 3.2.05-Autoencoders - Neural networks use karke PCA ka non-linear generalization
• Linear-Algebra-Eigenvalues-and-Eigenvectors - Eigendecomposition ki mathematical foundation
• Linear-Algebra-SVD - SVD theory aur PCA se aage applications
• 2.6.04-Kernel-PCA - Non-linear data ke liye extended PCA

#flashcards/ai-ml

PCA ka full form kya hai aur yeh kya karta hai? :: Principal Component Analysis data mein orthogonal directions dhundta hai jo variance ke order mein arrange hote hain, dimensionality reduction enable karta hai maximum information preserve karte hue.

Concept Map