Understanding Singular Value Decomposition (SVD)
Singular Value Decomposition (SVD) is a powerful method for solving systems of linear equations or matrices that are singular or close to singular. When LU-decomposition or Gaussian elimination fail, SVD provides a stable matrix decomposition helpful in various applications. It is particularly useful for solving linear least squares problems by decomposing the matrix into its singular values. SVD helps in understanding linear mappings and transformations, making it a versatile tool for simultaneous equations and unique matrix decomposition.
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.
E N D
Presentation Transcript
Singular Value Decomposition (SVD) Connor Welch
What is SVD? A powerful tool to solve for a system of linear equations or matrices that are either singular or close to singular. Where, LU-decomposition or Gaussian elimination fail outright or do not provide useful results. SVD is the meathod of choice for solving most linear least squares problems. SVD generates a stable (numerically) matrix decomposition that is guaranteed to exist. This is able to be used for a wide variety of purposes a few of which will be highlighted later.
Simultaneous Equations ? ? = ? Starting with a simple equation we have an A matrix (? ?) and x and b are vectors of dimension N and M respectively. Where SVD comes into play is that the A matrix is a linear mapping (or transformation) from an N dimensional space to an M dimensional space. This A matrix can be further decomposed using SVD.
Unique Matrix Decomposition Textbook ? ?? ?= ?? ??? ??? ? Another Likely Form To Encounter ? = ? ??
Continued Note: ? = ? ?? Both U and ??are unitary matrices or are orthogonal. The W or term is an N x N diagonal matrix. These terms are the non-negative singular values. There only exist singular values for the rank of M and the rest are zero. These values are hierarchically ordered or essentially ordered in importance of columns. Represents a scale along an axis. (scalar value) Left singular vectors. This also geometrically represents a Pure Rotation. Right singular vector. Geometrically represents a Pure Rotation The columns of U and ??are called the left singular vectors and right singular vectors respectively.
Definitions SVD Singular Value Decomposition. Eigenvectors nonzero vector that changes at most by a scalar factor when a linear transformation is applied. Eigenvalues factors by which the eigenvector is scaled. Null space right singular vectors of V corresponding to the zeroed singular values Rank the number of nonzero singular values Range the left singular vectors of U that correspond to non-zero singular values
Definitions Cont. Rank-nullity theorem for any A, the rank plus the nullity is equal to the number of columns N. Condition number ratio of the largest (magnitude) of singular values to the smallest. If condition number is infinite the matrix is singular. Ill-conditioned condition number is too large where the reciprocal approaches the floating-point precision of the machine
??? = ???= ? ?? ??? = ? 2?? Interpreting SVD (in terms of correlations) This interpretation gives the eigenvalue decomposition method of solving for SVD. This interpretation is using the economy SVD. ??? ? = ? 2 ???= ? ??= ? ??? ?? = ? 2 ?? This is not the way SVD is typically calculated as this method computationally intensive. SVD is typically calculated by using Householder reflections and QR decomposition ??? ? = ? 2
SVD: Solving Linear Equations SVD of a Square matrix, A = N x N Will only fail if singular values are either zero or very small (-singular matrix) ? = ? 1??? ? 1= ? 1?? Moore Penrose Pseudoinverse
Advantages and Disadvantages Advantages Disadvantages Algorithm is very numerically stable Can help diagnose what LU. decomposition and Gaussian elimination are breaking/failing on. Preferred way to solve least squares problems. Is extremely useful in many different fields and tasks. Relatively simple Linear Algebra The results of the transform can be difficult to interpret and visualize.
Other forms of SVD Economy SVD only uses values that have a corresponding non-zero singular values the rest of the terms are set to zero. SVD approximation if you have very small in magnitude terms you can set those values to zero and only use values singular values from 1 r instead of the economy SVD from 1 N
SVD Equations vs. Unknowns Fewer Equations than Unknowns Do not expect a unique solution. Usually, there is an N M dimensional family of solutions. Find the shortest solution and find the basis vectors for the null space where the final solution is the shortest solution plus any linear combination of the basis vectors. This system is called underdetermined. More equations than Unknowns Least-squares solution is found by the additional step of applying the pseudoinverse to the square matrix equations The matrix W will not be singular
SVD: Solving Linear Equations If M N solve Ax = b Overdetermined Solution: If M < N solve ?? Underdetermined Solution: ? = ????? ? = ????? Where Z = diagonal matrix of 1/singular values from and values are zeroed if the singular value is zero. Where Z = diagonal matrix of 1/singular values from and values are zeroed if the singular value is zero.
Uses of SVD Computing Pseudoinverse Solving homogeneous linear equations Total least squares minimization Finding Range, null space, and rank Low-rank matrix approximation Separable models Nearest orthogonal matrix The Kabsch algorithm Signal processing, image processing, and big data Numerical weather prediction
References Brunton, S. L., & Kutz, J. N. (2020). Data-driven science and engineering: Machine learning, dynamical systems and control. Cambridge University Press. Cook, T. (n.d.). Linear Algebra (3) . personalpages.manchester. Retrieved September 21, 2021, from https://personalpages.manchester.ac.uk/staff/timothy.f.cootes/MathsMethodsNote s/L3_linear_algebra3.pdf. Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (2007). Numerical recipes: The art of scientific computing. Cambridge University Press. https://en.wikipedia.org/wiki/Singular_value_decomposition https://www.youtube.com/watch?v=gXbThCXjZFM&list=PLMrJAkhIeNNSVjnsviglFo Y2nXildDCcv Dr. Steve Brunton s video lecture series based off the textbook above.
