9. Singular Value Decomposition (SVD)

We now consider what is perhaps the most important matrix factorization in linear algebra. We introduced the SVD in Singular Value Decomposition because we needed it to solve systems of linear equations, especially rectangular systems. This chapter presents a more complete picture of the SVD and its applications.

Three properties summarize the importance of the SVD.

1. The SVD can factor any matrix, even singular and rectangular matrices.

2. The SVD solves many linear algebra problems and has applications in many science and engineering fields, including artificial intelligence, data analysis, and image processing. The linear algebra applications of the SVD include finding the rank of a matrix, finding the inverse of a square matrix (Singular Value Decomposition), and the pseudo-inverse of rectangular matrices (Over-determined Pseudo-inverse, Under-determined Pseudo-inverse) [1], finding the condition number of a matrix, finding orthogonal basis vectors for the column space of a matrix, finding the null space, row space, and the left null space of a matrix, and low-rank matrix approximations.

3. The algorithm to find the SVD is now fast and numerically accurate. That was not always the case. We discuss the development of the modern SVD algorithm and present a simple implementation in Calculating the SVD with Unitary Transformations.

The fast factoring algorithm and the vast application domain of the decomposition have made the SVD a key algorithm in software such as MATLAB. It has replaced some elimination-based algorithms in the internal workings of MATLAB and other software.

Note

Our discussion of the SVD in this chapter focuses primarily on its interpretation and application.

The history of the SVD

The official introduction of the SVD came in 1873 when Eugenio Beltrami published a paper describing it. Unaware of Beltrami’s paper, Camille Jordan independently published a paper describing it a year later. Jordan’s paper is more complete and accurate in the details presented. Beltrami and Jordan built on previous works on the eigenvalues and eigenvectors of symmetric matrices. Augustin-Louis Cauchy established the properties of eigenvalues and eigenvectors of symmetric matrices in 1827. Then, in 1846, Carl Jacobi presented the diagonalization factorization of symmetric matrices. Stewart gives a nice summary of the early history of SVD and related topics [STEWART93].

Cleve Moler, co-founder of MathWorks, observed in a blog post that the SVD was of little practical value until 1970 [MOLER06]. Even when computers became available, the algorithm was too slow to be useful. The SVD algorithms developed between 1965 and 1990 are faster than the classic SVD algorithm and provide more numerically accurate results [YETURU20] and [LAMBERS10].

Contents

• 9.1. The Geometry of the SVD
  • 9.1.1. Ordered Columns of the SVD
  • 9.1.2. SVD of Rectangular Matrices
  • 9.1.3. Economy SVD
  • 9.1.4. The Classic SVD
  • 9.1.5. Implementation Difficulties
• 9.2. How SVD Changes Vectors
• 9.3. Rank from the SVD
• 9.4. Condition Number
• 9.5. Fundamental Matrix Subspaces
  • 9.5.1. Column Space
  • 9.5.2. Null Space
  • 9.5.3. Row Space
  • 9.5.4. Left Null Space
  • 9.5.5. Orthogonality of Spaces
• 9.6. Dimensionality Reduction
• 9.7. Other Applications of the SVD
  • 9.7.1. Projection and the Economy SVD
  • 9.7.2. Polar Decomposition

Footnote:

[1]

Computing the inverse and pseudo-inverse is covered in Introduction to Linear Algebra, so it is not part of this chapter.