Singular value decomposition - Definition

In linear algebra the singular value decomposition (SVD) is a factorization of a rectangular real or complex matrix analogous to the diagonalization of symmetric or Hermitian square matrices using a basis of eigenvectors (see spectral theorem).

Suppose M is an m-by-n matrix whose entries come from the field K, which is either the field of real numbers or the field of complex numbers. A non-negative real number σ is a singular value for M if there exist non-zero vectors u in K^m and v in Kⁿ such that

<math>Mv = \sigma u \,\!<math> and <math>M^*u = \sigma v \,\!<math>

where M^* denotes the conjugate transpose of M. The vectors u and v are called left-singular and right-singular vectors for σ, respectively.

The singular-value decomposition theorem says that M has a factorization of the form

<math>M = U\Sigma V^* \,\!<math>

where U is an m-by-m unitary matrix over K, V is an n-by-n unitary matrix over K, and Σ is an m-by-n diagonal matrix whose diagonal entries Σ_i,i are non-negative real numbers. Such a factorization is called a singular-value decomposition of M.

In any such singular value decomposition, the diagonal entries of Σ are necessarily equal to the singular values of M. It is conventional to order the singular values in decreasing order.

The columns u₁,...,u_m of U are eigenvectors of MM^* and are left singular vectors of M. The columns v₁,...,v_n of V are eigenvectors of M^*M and are right singular vectors of M. Note however that different singular value decompositions of M can contain different singular vectors.

The linear transformation T: Kⁿ → K^m that takes a vector x to Mx has a particularly simple description with respect to these orthonormal bases: we have T(v_i) = d_i u_i, for i = 1,...,min(m,n), where d_i is the i-th diagonal entry of D, and T(v_i) = 0 for i > min(m,n).

Rank determination

The number of non-zero singular values is equal to the rank r of M. These non-zero singular values are equal to the square roots of the non-zero eigenvalues of the positive semi-definite matrix MM^*, and also equal to the square roots of the non-zero eigenvalues of M^*M. In numerical linear algebra the singular values can be used to determine the effective rank of a matrix, as rounding error may lead to small but non-zero singular values in a rank deficient matrix.

Reduced SVD

If we focus only on these r nonzero singular values, we can construct a singular-value decomposition of the following type:

<math>M = GDH^* \,\!<math>

where G is an m-by-r orthonormal matrix over K, H is an n-by-r orthonormal matrix over K and D is an r-by-r diagonal matrix whose diagonal entries are positive real numbers.

Norms

The sum of the k largest singular values of M is a matrix norm, the Ky Fan k-norm of M. The Ky Fan 1-norm is just the operator norm of M as a linear operator with respect to the Euclidean norms of K^m and Kⁿ. The square root of the sum of squares of the singular values is the Frobenius norm of M.

Applications of the SVD

The SVD is applied extensively to the study of linear inverse problems, and is useful in the analysis or regularization methods such as that of Tikhonov. It is widely used in statistics where it is related to principal component analysis, and in signal processing and pattern recognition.

See also

• matrix decomposition
• s-number
• generalized singular value decomposition
• empirical orthogonal functions (EOFs)
• canonical correlation analysis (CCA)
• latent semantic analysis

External links

• LAPACK users manual  (http://www.netlib.org/lapack/lug/node53.html) gives details of subroutines to calculate the SVD.
• Applications of SVD (http://www.imm.dtu.dk/~pch/Projekter/tsvd.html) on PC Hansen's web site.
• MIT Lecture (http://web.mit.edu/18.06/www/Video/video-fall-99.html) series by Gilbert Strang. See Lecture #29 on the SVD.
• Java applet (http://klebanov.homeip.net/~pavel/fb//java/la_applets/SVD/index.html) demonstrating the SVD.
• Java script  (http://users.pandora.be/paul.larmuseau/SVD.htm) demonstrating the SVD more extensively, paste your data from a spreadsheet.

References

• Strang G, Introduction to Linear Algebra, 3rd Edition, Wellesley-Cambridge Press, 1998, (Section 6.7) ISBN 0961408855
• Golub, G. H. and Van Loan, C. F. Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996, ISBN 0801854148
• Hansen, PC, The truncated SVD as a method for regularization, BIT, 27 , 1987, pp. 534-553.