Eigen Decomposition and Singular Value DecompositionIntroductionWhat are eigenvalues?Calculating the Eigenvectors/valuesEigenvalue examplePhysical interpretationPhysical interpretationPhysical interpretationSpectral Decomposition theoremExample for spectral decompositionSingular Value DecompositionSingular Value Decomposition (contd.)Example for SVDExample for SVDApplications of SVD in Linear AlgebraApplications of SVD in Linear AlgebraWhat is the use of SVD?Image Compression using SVDEigen Decomposition and Singular Value DecompositionMani ThomasCISC 489/689Introduction Eigenvalue decomposition Spectral decomposition theorem Physical interpretation of eigenvalue/eigenvectors Singular Value Decomposition Importance of SVD Matrix inversion Solution to linear system of equations Solution to a homogeneous system of equations SVD applicationWhat are eigenvalues? Given a matrix, A, x is the eigenvector and λ is the corresponding eigenvalue if Ax = λx A must be square the determinant of A - λ I must be equal to zeroAx - λx = 0 → x(A - λI) = 0 Trivial solution is if x = 0 The non trivial solution occurs when det(A - λI) = 0 Are eigenvectors are unique? If x is an eigenvector, then βx is also an eigenvector and βλ is an eigenvalueA(βx) = β(Ax) = β(λx) = λ(βx)Calculating the Eigenvectors/values Expand the det(A - λI) = 0 for a 2 × 2 matrix For a 2 × 2 matrix, this is a simple quadratic equation with two solutions (maybe complex) This “characteristic equation” can be used to solve for x()()()()( )000det01001detdet2112221122112211222112221121122211211=−++−=−−−⇒=⎥⎦⎤⎢⎣⎡−−=⎟⎟⎠⎞⎜⎜⎝⎛⎥⎦⎤⎢⎣⎡−⎥⎦⎤⎢⎣⎡=−aaaaaaaaaaaaaaaaaaIAλλλλλλλλ()()()211222112221122114 aaaaaaaa−+±+=λEigenvalue example Consider, The corresponding eigenvectors can be computed as For λ = 0, one possible solution is x = (2, -1) For λ = 5, one possible solution is x = (1, 2)()( )()⎪⎩⎪⎨⎧==⇒+==⋅−⋅++−=−++−⇒⎥⎦⎤⎢⎣⎡=5,0)41(02241)41(04221222112221122112λλλλλλλλaaaaaaA⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡−+−=⎥⎦⎤⎢⎣⎡⋅⎥⎦⎤⎢⎣⎡−−⇒=⎥⎦⎤⎢⎣⎡⋅⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−⎥⎦⎤⎢⎣⎡⇒=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡++=⎥⎦⎤⎢⎣⎡⋅⎥⎦⎤⎢⎣⎡⇒=⎥⎦⎤⎢⎣⎡⋅⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−⎥⎦⎤⎢⎣⎡⇒=0012241224050054221500422142210000042210yxyxyxyxyxyxyxyxλλFor more information: Demos in Linear algebra by G. Strang, http://web.mit.edu/18.06/www/Physical interpretation Consider a correlation matrix, A Error ellipse with the major axis as the larger eigenvalue and the minor axis as the smaller eigenvalue25.0,75.1175.75.121==⇒⎥⎦⎤⎢⎣⎡=λλAPhysical interpretation Orthogonal directions of greatest variance in data Projections along PC1 (Principal Component) discriminate the data most along any one axisOriginal Variable AOriginal Variable BPC 1PC 2Physical interpretation First principal component is the direction of greatest variability (covariance) in the data Second is the next orthogonal (uncorrelated) direction of greatest variability So first remove all the variability along the first component, and then find the next direction of greatest variability And so on … Thus each eigenvectors provides the directions of data variances in decreasing order of eigenvaluesFor more information: See Gram-Schmidt Orthogonalization in G. Strang’s lecturesSpectral Decomposition theorem If A is a symmetric and positive definite k × k matrix (xTAx> 0) with λi(λi> 0) and ei, i = 1 L k being the k eigenvector and eigenvalue pairs, then This is also called the eigen decomposition theorem Any symmetric matrix can be reconstructed using its eigenvalues and eigenvectors Any similarity to what has been discussed before?()()() ()()()()()()()TkikTikiikkkTkkkkkTkkTkkkPPeeAeeeeeeA Λ==⇒++=∑=××××××××××111111212211111λλλλL()[]()⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=Λ=××kkkkkkλλλLMOMMLLL000000,,2121eeePExample for spectral decomposition Let A be a symmetric, positive definite matrix The eigenvectors for the corresponding eigenvalues are Consequently,()()()()02316.016.650det8.24.04.02.22=−−=−+−⇒=−⇒⎥⎦⎤⎢⎣⎡=λλλλλIAA⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡=51,52,52,5121TTee⎥⎦⎤⎢⎣⎡−−+⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡−⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−+⎥⎦⎤⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡=4.08.08.06.14.22.12.16.05152515225251525138.24.04.02.2ASingular Value Decomposition If A is a rectangular m × k matrix of real numbers, then there exists an m × m orthogonal matrix U and a k × k orthogonal matrix V such that  Λ is an m × k matrix where the (i, j)thentry λi≥ 0, i = 1 L min(m, k) and the other entries are zero The positive constants λiare the singular values of A If A has rank r, then there exists r positive constants λ1, λ2,Lλr, r orthogonal m × 1 unit vectors u1,u2,L,urand r orthogonal k × 1 unit vectors v1,v2,L,vrsuch that Similar to the spectral decomposition theorem()()()()IVVUUVUA ==Λ=××××TTkkTkmmmkm∑==riTiii1vuAλSingular Value Decomposition (contd.) If A is a symmetric and positive definite then  SVD = Eigen decomposition EIG(λi) = SVD(λi2) Here AAThas an eigenvalue-eigenvector pair (λi2,ui) Alternatively, the viare the eigenvectors of ATA with the same non zero eigenvalue λi2TTVVAA2Λ=()()TTTTTTTUUUVVUVUVUAA2Λ=ΛΛ=ΛΛ=Example for SVD Let A be a symmetric, positive definite matrix U can be computed as V can be computed as ()⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡=⇒==⇒=−⎥⎦⎤⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−⎥⎦⎤⎢⎣⎡−=⇒⎥⎦⎤⎢⎣⎡−=21,21,21,2110,120det1111111131131311131311132121TTTTuuIAAAAAγγγ()⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡−=⎥⎦⎤⎢⎣⎡=⇒===⇒=−⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡−⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−=⇒⎥⎦⎤⎢⎣⎡−=305,302,301,0,51,52,61,62,610,10,120det24241002010131113113113131113321321TTTTTvvvIAAAAAγγγγExample for SVD Taking λ21=12 and λ22=10, the singular value decomposition of A is Thus the U, V and Λ are computed by performing eigendecomposition of AATand ATA Any matrix has a singular