M2-058M2: Classical Machine LearningDimensionality ReductionEasy
⚡Flashcard Drill➔Mastery:

Explain the Exact Mathematical Equivalence Between PCA and Singular Value Decomposition (SVD)

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M2-059 →
📐 Mathematical Definition
X=UΣV⊤⇒PCs=V, λi=σi2/nX=U\Sigma V^\top\Rightarrow \text{PCs}=V,\ \lambda_i=\sigma_i^2/n
⚡ One-Sentence Core Answer
For a zero-centered data matrix X=UΣVTX = U\Sigma V^T, the right singular vectors VV are the principal component loading directions, the singular values relate to eigenvalues via λi=σi2N−1\lambda_i = \frac{\sigma_i^2}{N-1}, and UΣU\Sigma provides the projected principal coordinates.

📌 Key Takeaways

  • •
    Covariance Connection: Σcov=1N−1XTX=1N−1(VΣTUT)(UΣVT)=V(Σ2N−1)VT\Sigma_{\text{cov}} = \frac{1}{N-1}X^T X = \frac{1}{N-1}(V\Sigma^T U^T)(U\Sigma V^T) = V \left(\frac{\Sigma^2}{N-1}\right) V^T.
  • •
    Eigenvalue Equivalence: The eigenvalues of the covariance matrix are directly proportional to squared singular values: λi=σi2N−1\lambda_i = \frac{\sigma_i^2}{N-1}.
  • •
    Principal Components: Projected coordinates are Z=XV=(UΣVT)V=UΣZ = X V = (U \Sigma V^T) V = U \Sigma.

📐 Mathematical Derivations

Let X∈RN×dX \in \mathbb{R}^{N \times d} be mean-centered (E[X]=0E[X]=0). The compact SVD of XX is X=UΣVTX = U \Sigma V^T, where U∈RN×rU \in \mathbb{R}^{N \times r} has orthonormal columns (UTU=IrU^T U = I_r), Σ=diag(σ1,…,σr)\Sigma = \text{diag}(\sigma_1, \dots, \sigma_r) with σ1≥⋯≥σr>0\sigma_1 \ge \dots \ge \sigma_r > 0, and V∈Rd×rV \in \mathbb{R}^{d \times r} has orthonormal columns (VTV=IrV^T V = I_r). The sample covariance matrix is: S=1N−1XTX=1N−1(VΣUT)(UΣVT)=V(Σ2N−1)VTS = \frac{1}{N-1} X^T X = \frac{1}{N-1} (V \Sigma U^T)(U \Sigma V^T) = V \left(\frac{\Sigma^2}{N-1}\right) V^T. Because VV is orthogonal and Σ2N−1\frac{\Sigma^2}{N-1} is diagonal with positive entries, this equation is the unique spectral eigenvalue decomposition of SS! The right singular vectors VV are precisely the principal direction eigenvectors of SS, and the eigenvalues are λi=σi2N−1\lambda_i = \frac{\sigma_i^2}{N-1}. The low-dimensional projected data is Zk=XVk=UkΣkVkTVk=UkΣkZ_k = X V_k = U_k \Sigma_k V_k^T V_k = U_k \Sigma_k.

🏭 Production Trade-offs

Why production libraries (scikit-learn PCA) strictly use SVD rather than XTXX^T X: (1) Numerical Precision: Inverting or decomposing XTXX^T X squares the condition number: κ(XTX)=κ(X)2\kappa(X^T X) = \kappa(X)^2. If κ(X)=105\kappa(X) = 10^5, XTXX^T X has condition number 101010^{10}, causing severe loss of numerical precision. SVD operates directly on XX, preserving dynamic range. (2) Dimensionality efficiency: When d≫Nd \gg N (e.g. N=100N=100 samples with d=50,000d=50,000 features), computing XTXX^T X takes O(Nd2)O(N d^2) memory and time. SVD computes the N×NN\times N Gram matrix XXTX X^T in O(N2d)O(N^2 d) time.
⚠️ Common Interview Pitfalls
  • ✕
    Computing SVD without centering features (SVD on raw uncentered XX does NOT equal PCA).
  • ✕
    Dividing singular values by NN instead of N−1N-1 when calculating unbiased sample variance.
🎯 Interviewer Follow-up Inquiries
  • ?
    How does Randomized SVD (Halko et al., 2011) compute truncated PCA in O(Ndk)O(N d k) time for massive matrices?
  • ?
    Why does centering data change the right singular vectors of a matrix?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM2-057: Formulate Principal Component Analysis (PCA): Maximum Variance and Minimum Reconstruction Error Perspectives📋 Back to BankNext →M2-059: Enumerate the Limitations of PCA and Scenarios Where Linear PCA Fails