#### Transcript SVD and PCA

SVD and PCA COS 323, Spring 05 SVD and PCA • Principal Components Analysis (PCA): approximating a high-dimensional data set with a lower-dimensional subspace * * Second principal component * * First principal component * * * * * * * ** * * Original axes * * * * * ** * * Data points SVD and PCA • Data matrix with points as rows, take SVD – Subtract out mean (“whitening”) • Columns of Vk are principal components • Value of wi gives importance of each component PCA on Faces: “Eigenfaces” Average face First principal component Other components For all except average, “gray” = 0, “white” > 0, “black” < 0 Uses of PCA • Compression: each new image can be approximated by projection onto first few principal components • Recognition: for a new image, project onto first few principal components, match feature vectors PCA for Relighting • Images under different illumination [Matusik & McMillan] PCA for Relighting • Images under different illumination • Most variation captured by first 5 principal components – can re-illuminate by combining only a few images [Matusik & McMillan] PCA for DNA Microarrays • Measure gene activation under different conditions [Troyanskaya] PCA for DNA Microarrays • Measure gene activation under different conditions [Troyanskaya] PCA for DNA Microarrays • PCA shows patterns of correlated activation – Genes with same pattern might have similar function [Wall et al.] PCA for DNA Microarrays • PCA shows patterns of correlated activation – Genes with same pattern might have similar function [Wall et al.] Multidimensional Scaling • In some experiments, can only measure similarity or dissimilarity – e.g., is response to stimuli similar or different? • Want to recover absolute positions in kdimensional space Multidimensional Scaling • Example: given pairwise distances between cities – Want to recover locations [Pellacini et al.] Euclidean MDS • Formally, let’s say we have n n matrix D consisting of squared distances dij = (xi – xj)2 • Want to recover n d matrix X of positions in d-dimensional space 0 ( x1 x2 ) 2 D 2 ( x1 x3 ) ( x1 x2 ) 2 ( x1 x3 ) 2 0 ( x2 x3 ) 2 ( x2 x3 ) 2 0 ( x1 ) X ( x2 ) Euclidean MDS • Observe that dij2 ( xi x j )2 xi 2 xi x j x j 2 2 • Strategy: convert matrix D of dij2 into matrix B of xixj – “Centered” distance matrix – B = XXT Euclidean MDS • Centering: – Sum of row i of D = sum of column i of D = si 2 2 2 d x 2 x x x ij i i j j j j nxi2 2 xi x j x 2j j j – Sum of all entries in D = s si 2n x 2 xi i i i 2 i 2 Euclidean MDS • Choose xi = 0 – Solution will have average position at origin – Then, si nxi2 x 2j , s 2n x 2j j j dij2 1n si 1n s j n12 s 2 xi x j • So, to get B: – – – – compute row (or column) sums compute sum of sums apply above formula to each entry of D Divide by –2 Euclidean MDS • Now have B, want to factor into XXT • If X is n d, B must have rank d • Take SVD, set all but top d singular values to 0 – – – – Eliminate corresponding columns of U and V Have B3=U3W3V3T B is square and symmetric, so U = V Take X = U3 times square root of W3 Multidimensional Scaling • Result (d = 2): [Pellacini et al.] Multidimensional Scaling • Caveat: actual axes, center not necessarily what you want (can’t recover them!) • This is “classical” or “Euclidean” MDS [Torgerson 52] – Distance matrix assumed to be actual Euclidean distance • More sophisticated versions available – “Non-metric MDS”: not Euclidean distance, sometimes just relative distances – “Weighted MDS”: account for observer bias