Slide 1SVDSVD: Mathematical BackgroundSVD: The mathematical formulationSVD - InterpretationSlide 6Slide 7Slide 8Dimensionality reductionSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Another example-EigenfaceSlide 20Principal Components Analysis (PCA)Recitation:SVD and dimensionality reduction Zhenzhen KouThursday, April 21, 2005SVD•Intuition: find the axis that shows the greatest variation, and project all points into this axisf1e1e2f2SVD: Mathematical Background=Xm X nUm X rSr X rV’r X nxSkk X k Ukm X kVk’k X nThe reconstructed matrix Xk = Uk.Sk.Vk’ is the closest rank-k matrix to the original matrix R.XkSVD: The mathematical formulation•Let X be the M x N matrix of M N-dimensional points•SVD decomposition –X= U x Sx VT–U(M x M)•U is orthogonal: UTU = I•columns of U are the orthogonal eigenvectors of XXT•called the left singular vectors of X–V(N x N)•V is orthogonal: VTV = I •columns of V are the orthogonal eigenvectors of XTX•called the right singular vectors of X–S(M x N)•diagonal matrix consisting of r non-zero values in descending order•square root of the eigenvalues of XXT (or XTX)–r is the rank of the symmetric matrices•called the singular valuesSVD - InterpretationSVD - Interpretation•X = U S VT - example:1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 10.18 00.36 00.18 00.90 00 0.530 0.800 0.27=9.64 00 5.29x0.58 0.58 0.58 0 00 0 0 0.71 0.71xv1SVD - Interpretation•X = U S VT - example:1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 10.18 00.36 00.18 00.90 00 0.530 0.800 0.27=9.64 00 5.29x0.58 0.58 0.58 0 00 0 0 0.71 0.71xvariance (‘spread’) on the v1 axisSVD - Interpretation•X = U S VT - example:–U gives the coordinates of the points in the projection axis1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 10.18 00.36 00.18 00.90 00 0.530 0.800 0.27=9.64 00 5.29x0.58 0.58 0.58 0 00 0 0 0.71 0.71xDimensionality reduction•set the smallest eigenvalues to zero:1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 10.18 00.36 00.18 00.90 00 0.530 0.800 0.27=9.64 00 5.29x0.58 0.58 0.58 0 00 0 0 0.71 0.71xDimensionality reduction1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 10.18 00.36 00.18 00.90 00 0.530 0.800 0.27~9.64 00 0x0.58 0.58 0.58 0 00 0 0 0.71 0.71xDimensionality reduction1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 10.18 00.36 00.18 00.90 00 0.530 0.800 0.27~9.64 00 0x0.58 0.58 0.58 0 00 0 0 0.71 0.71xDimensionality reduction1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 10.180.360.180.90000~9.64x0.58 0.58 0.58 0 0xDimensionality reduction1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 1~1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 0 00 0 0 0 00 0 0 0 0Dimensionality reductionEquivalent:‘spectral decomposition’ of the matrix:1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 10.18 00.36 00.18 00.90 00 0.530 0.800 0.27=9.64 00 5.29x0.58 0.58 0.58 0 00 0 0 0.71 0.71xDimensionality reductionEquivalent:‘spectral decomposition’ of the matrix:1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 1=x xu1u212v1v2Dimensionality reduction‘spectral decomposition’ of the matrix:1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 1=u11vT1u22vT2++...nmn x 11 x mr termsDimensionality reductionapproximation / dim. reduction:by keeping the first few terms (Q: how many?)1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 1=u11vT1u22vT2++...nmassume: 1 >= 2 >= ...Dimensionality reductionA heuristic: keep 80-90% of ‘energy’ (= sum of squares of i ’s)1 1 1 0 02 2 2 0 01 1 1 0 05 5 5 0 00 0 0 2 20 0 0 3 30 0 0 1 1=u11vT1u22vT2++...nmassume: 1 >= 2 >= ...Another example-Eigenface•The PCA problem in HW5•Face data X•Eigenvectors associated with the first few large eigenvalues of XXT have face-like imagesDimensionality reduction•Matrix V in the SVD decomposition (X = USVT ) is used to transform the data.•XV (= US defines the transformed dataset.•For a new data element x, xV defines the transformed data. •Keeping the first k (k < n) dimensions, amounts to keeping only the first k columns of V.Principal Components Analysis (PCA)•Transfer the dataset to the center by subtracting the means: let matrix X be the result.•Compute the matrix XTX.•The covariance matrix except for constants.•Project the dataset along a subset of the eigenvectors of XTX.•Matrix V in the SVD decomposition (X= U S VT ) contains the eigenvectors of XTX.•Also known as K-L
View Full Document
Unlocking...