Part 1: Dimensionality Reduction

Dimensionality reduction → Consider a high-dimensional input data i.e. a large number of parameters/ features (noisy) → Dimensionality reduction "simplifying" a dataset by projecting it onto a lower dimensional subspace while preserving important trend/characteristics of the original dataset change the basis achieved by multiplying by an orthogonal matrix → dimensionality reduction assumes that the data can be represented/approximated well by lower dimensional data i.e. the data lies on a lower-dimension manifold (manifold hypothesis) Benefits of dimensionality reduction Important if model doesn't scale well with high dimensions (computational benefit) Stability and performance (numerical benefit) Removes irrelevant/redundant info (interpretability/simplicity benefit) Principal component analysis → dimensionality reduction technique that aims to find directions of maximum variance and minimum error in the data → PCA removes dependence on the original set of axes → We consider a data matrix X:d×N 1. d: nr. of features 2. N: nr. of samples → now we consider projecting the data on a one-dimensional subspace spanned by u vector (to ensure new metrics must be orthogonal) → projected data is u T X u T X where u is a unit centered data L mean: u T X ˉ L variance: u T (X− X ˉ )(X− X ˉ ) T u Steps to maximize the variance (L,2,3) Use the Lagrange multipliers with the condition u T u=1 To maximize u T S u ​ u differentiate ⊗ in terms of u and equate to zero →S u ​ u=λu We end up with the equation S u ​ u=λu→λ=u T S u ​ u To so maximize u T S u ​ u we say u is the eigenvector of S associated with the largest eigenvalue (non-eigenvalue problem) → We say the first k principal components of the data set are the eigenvectors of the sample covariance matrix associated with the k largest eigenvalues of the sample covariance (these eigenvalues represents the variance along the principal components) 1. PCA using singular value decomposition (SVD) (More stable than eigendecomposition) → D=UΣV T (where D is the centered data) → setting r=rank(X) we get the compact SVD → now we rotate the data so our axes align with the principal components D rot ​ =U T D → D rot ​ =ΣV T → if we want to whiten the data: D white ​ =Σ −1 D rot ​ → whitened makes the data spherical and ensures unit variance along principal components r< d zero forced → U T D align with the principal components Important: A rotation matrix R preserves the determinant of the matrix It makes bias changes the basis (xx T ​ ) 2. PCA using eigendecomposition → S=XX T /D (covariance matrix) (It only works for X=D, but eigendecomposition of DD T also optimizes eigendecomposition of the data for D and D T ) → now we apply eigendecomposition (It gives principal directions and scales, eigendecomposition of DD T also gives principal directions and scales in decreasing order) 1. Q is made up of the eigenvectors of S (principal components) 2. Λ is a diagonal matrix with the eigenvalues of S on its diagonal → now we rotate the data: D rot ​ =Q T D (Q is a rotating principal component) → If we want to whiten the data: D white ​ =Λ −1/2 Q T D Λ 1/2 D white ​ Quantifying loss with eigenvalues - Frobenius norm: Frobenius norm of D: ∥D∥ F ​ = ∑ i=1 m ​ ∑ j=1 n ​ ∣D ij ​ ∣ 2 ​ = trace(D T D) ​ i.e. the square root of the sum of variance