Understanding the Singular Value Decomposition

The Singular Value Decomposition (SVD) is a powerful factorization method for matrices, extending the concept of eigenvectors and eigenvalues to non-symmetric matrices. This decomposition allows any matrix to be expressed as the product of three matrices: two orthogonal matrices and a diagonal matrix containing singular values. The SVD provides insights into linear systems and can be used for various applications, such as least squares solutions. This article explores the existence of SVD and its significance in matrix analysis.

• Singular Value Decomposition
• Matrix Factorization
• Linear Algebra
• Orthogonal Matrices
• Eigenvalues

niles Follow

Uploaded on Aug 05, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Lecture 10: The Singular Value Decomposition Nicholas Ruozzi University of Texas at Dallas

2. Motivation We just spent a lot of time looking at interesting consequences of the observation that any symmetric matrix ? can be factorized as ? = ????for some orthogonal matrix ? and some diagonal matrix ? Is there a generalization of this for arbitrary matrices? Yes! It is based on the same eigenvectors/eigenvalues construction as above, but it isn t symmetric 2

3. The Singular Value Decomposition Every matrix ? ? ? can be factorized as ? = ? ?? where ? ? ? and ? ? ? are orthogonal matrices and ? ? is a diagonal matrix The diagonal entries of ? are called the singular values of the matrix ? We ll show that we can use this decomposition similarly to the eigenvalue decomposition, e.g., for finding least squares solutions for linear systems But first, let s show that the SVD exists 3

4. Existence of the SVD Let ? ? ? be an arbitrary matrix and consider the positive semidefinite matrix ??? For now, let s assume that it is full rank, i.e., it has no zero eigenvalues ???(?)???, where ? ? are ? It can be written as ??? = ?=1 orthonormal eigenvectors in ? Define ??= ?? Let ?(?)=??? ??. Note that ????(?)= 1 and ????(?)= ???(?) 4

5. Existence of the SVD Let ? ? ? be an arbitrary matrix and consider the positive semidefinite matrix ??? Let ?(?)=??? ??. Note that ????(?)= 1 and ????(?)= ???(?) The ? ? are orthonormal eigenvectors of ??? Let ? ? be a diagonal matrix with ??= ?? and 1 ? ?be a diagonal matrix with ?? 1= 1/?? Now, by construction, ? = ?? 1 ? = ?? ????= ? 5

6. Existence of the SVD Finally if the positive semidefinite matrix ??? is not full rank, we can apply the same argument by constructing one ? for each of the non-zero eigenvalues and then extending them to an orthonormal basis We keep the diagonal entries of both and 1 equal to zero for vectors in the extension That s it *This nice argument was taken from a blog post of Gregory Gunderson 6

7. The Singular Value Decomposition Every matrix ? ? ? can be factorized as ? = ? ?? where ? ? ? and ? ? ? are orthogonal matrices and ? ? is a diagonal matrix The diagonal entries of ? are called the singular values of the matrix ? and they are the square roots of the eigenvalues of ??? and ??? ? are orthonormal eigenvectors of ??? ? are orthonormal eigenvectors of ??? 7

8. Least Squares Solutions Linear Systems 1 2 2 min ? ? ?2 subject to ?? = ? ? ?,? =1 2??? + ??(?? ?) ?? = ? + ??? = 0 ? = ????+??? ? = ??+???, where ???= ???? ? = ????+??? Note that ? = ???? where ???= ??? 8

9. Least Squares Solutions Linear Systems 1 2 2 min ? ? ?2 subject to ?? = ? ? ?,? =1 2??? + ??(?? ?) ?? = ? + ??? = 0 ? = ????+??? ? = ??+???, where ???= ???? ? = ????+??? = ? QTQD+QTb = V +??? Note that ? = ???? where ???= 9 ???

10. The Morse-Penrose Pseudo-inverse If the linear system ?? = ? has a solution, then the solution of minimum norm is given by ? = ?+? where ? = ? ??, the singular value decomposition ?+= ??+?? If ? is invertible, then ?+= ? 1 All the interesting algebraic properties of ?+ following directly from the definition above, e.g., ??+? = ? ??? +??? ??= ? + ??= ? ??= ? 10

11. Ex 1: Convex Quadratic Minimization 1 2???? ??? inf ? ? ? ? ? is an arbitrary p.s.d matrix Either ?? = ? or 1 2???? ??? = inf ? 11

12. Pseudoinverse 2 min ? ??? ?2 12

13. Pseudoinverse ? ??? ??(?? ?) min 13

14. Pseudoinverse ? ??????? 2???? + ??? min Either ???? = ??? or ??????? 2???? = inf 14

15. Pseudoinverse ? ??????? 2???? + ??? min Either ???? = ??? or ??????? 2???? = inf 15

16. Pseudoinverse ? ??????? 2???? + ??? min ???? = ??? Let ? = ? ?? ? = ???+??? = ? + 2??? ??? = ? +??? = ?+? The pseudoinverse solves the norm minimization problem even if there is no solution to ?? = ?! 16

17. Ex 2: Convex Quadratic Minimization 1 2???? ??? min ? ? ? ? ? is an arbitrary p.s.d matrix subject to ? 0 ? ?,? =1 2???? ??? ??? 17

18. Ex 2: Convex Quadratic Minimization 1 2???? ??? min ? ? subject to ? 0 ? ?,? =1 2???? ??? ??? Either ?? = ? + ? or inf ?? ?,? = 18

19. Ex 2: Convex Quadratic Minimization 1 2???? ??? min ? ? subject to ? 0 ? ?,? =1 2???? ??? ??? 1 2 ? + ???+??+(? + ?) ? + ???+(? + ?) max ? subject to ? ??.?? = ? + ? ? 0 19

20. Ex 2: Convex Quadratic Minimization 1 2???? ??? min ? ? subject to ? 0 ? ?,? =1 2???? ??? ??? 1 2? + ???+(? + ?) max ? subject to ? ??.?? = ? + ? ? 0 20

21. Ex 2: Convex Quadratic Minimization 1 2???? ??? min ? ? subject to ? 0 ? ?,? =1 2???? ??? ??? 1 2? + ???+(? + ?) max ? subject to (? + ?) span(???.???.?? ? ??? ??? ???? ??????????) ? 0 21

22. Ex 2: Convex Quadratic Minimization 1 2???? ??? min ? ? subject to ? 0 ? ?,? =1 2???? ??? ??? 1 2? + ???+(? + ?) max ? ???(?)??? ? = subject to ? ??? ??? ? ??.??= 0, ? + ???(?)= 0 ? 0 22

23. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 23

24. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 ? ?,? = ???? + 2??? + ? ??? 1 = ??? + ?? ? + 2??? ? 24

25. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 ? ?,? = ???? + 2??? + ? ??? 1 = ??? + ?? ? + 2??? ? Bounded from below only if ? + ?? is positive semidefinite and the linear system ? + ?? = ? has a solution 25

26. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 ? ?,? = ???? + 2??? + ? ??? 1 = ??? + ?? ? + 2??? ? Bounded from below only if ? + ?? is positive semidefinite and the linear system ? + ?? = ? has a solution ?? = 2 ? + ?? ? + 2? = 0 ? = ? + ??+? 26

27. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 ? ?,? = ???? + 2??? + ? ??? 1 = ??? + ?? ? + 2??? ? ? 0??? + ??+? + ?? ? + ??+? 2??? + ??+? ? subject to ? + ?? 0 ? st. ? + ?? ? = ? max 27

28. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 ? ?,? = ???? + 2??? + ? ??? 1 = ??? + ?? ? + 2??? ? ? 0 ??? + ??+? ? max subject to ? + ?? 0 ? st. ? + ?? ? = ? 28

29. Eigenvectors of ? + ?? If is ? an eigenvector of ? with eigenvalue ?, then ?? = ?? ??? = ?? ? + ?? ? = ? + ? ? So, ? + ?? is positive semidefinite if and only if ? ???? where ???? is the smallest eigenvalue of ? 29

30. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 ? ?,? = ???? + 2??? + ? ??? 1 = ??? + ?? ? + 2??? ? ? 0 ??? + ??+? ? max subject to ? ???? ? st. ? + ?? ? = ? 30

31. Range of a Matrix ? st. ? + ?? ? = ? has a solution for a symmetric matrix ? + ?? if and only if ? is in the span of the eigenvectors of ? + ?? with non-zero eigenvalues (note the eigenvectors of ? + ?? are the same as the orthonormal eigenvectors of ?) 2 ???? In this case, ??? + ??+? = ?:?+??>0 ?+?? Otherwise, the constraint that ? st. ? + ?? ? = ? is violated, i.e., there exists an eigenvector ?(?) of ? such that ? + ?? ?(?)= 0 and ???(?) 0 Note that, for large enough ?, this system always has a solution, indeed, ? > ?:???(?) 0?? min 31

32. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 max ? 0 ?(?) ? subject to ? ???? where if ? ??.???? 0 ??? ? + ??= 0 , 2 ???? ? ? = , ?? ?????? ? + ?? ?:?+??>0 32

33. Non-Convex Quadratic Minimization ? ????? + 2??? min ? ? ? is an arbitrary symmetric matrix subject to ??? 1 max ? 0 ?(?) ? subject to ? ???? where if ? ??.???? 0 ??? ? + ??= 0 , 2 ???? ? ? = How would you solve this problem? , ?? ?????? ? + ?? ?:?+??>0 33

34. SVD Reformulated Let ? ? ? with svd, ? = ? ?? min(?,?)???(?)??? ? = ?=1 Without loss of generality, we can assume that the singular values are in decreasing order, i.e., ?1= 11 ?2= 22 ??= ?? 2 2= ????? ??? = ??? ?? 34

35. Applications of SVD: Low Rank Approximations 2 ? = arg ? ??.???? ? =?? ?? min min(?,?) ???(?)??? ? = ? ??= ?=1 ? ???(?)??? ? = ?=1 Note: ? s must be in decreasing order for this! 35