Singular value decomposition

In linear algebra the singular value decomposition (SVD) is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics. This matrix decomposition is analogous to the diagonalization of symmetric or Hermitian square matrices using a basis of eigenvectors given by the spectral theorem.

Contents

1 Statement of the theorem 2 Singular values, singular vectors, and their relation to the SVD 3 Geometric meaning 4 Rank determination 5 Reduced SVD 6 Norms 7 Applications of the SVD 8 Computation of the SVD 9 See also 10 External links 11 References

Statement of the 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. Then there exists 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, V^* denotes the conjugate transpose of V, 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.

One commonly insists that the values Σ_i,i be ordered in non-increasing fashion. In this case, the diagonal matrix Σ is uniquely determined by M (though the matrices U and V are not).

Singular values, singular vectors, and their relation to the SVD

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 \,\mbox{ and } M^*u = \sigma v \,\!<math>.

The vectors u and v are called right-singular and left-singular vectors for σ, respectively.

In any singular value decomposition

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

the diagonal entries of Σ are necessarily equal to the singular values of M. The columns of U and V are left- resp. right singular vectors for the corresponding singular values. Note that the singular vectors are not uniquely determined by a given singular value, and likewise the matrices U and V are not uniquely determined by the matrix M.

One can show that the non-zero singular values for M are precisely the square roots of the non-zero eigenvalues of the positive semi-definite matrix MM^*, and these are precisely the square roots of the non-zero eigenvalues of M^*M. Furthermore, the columns of U are eigenvectors of MM^* and the columns of V are eigenvectors of M^*M.

Geometric meaning

Because U and V are unitary, we know that the columns u₁,...,u_m of U yield an orthonormal basis of K^m and the columns v₁,...,v_n of V yield an orthonormal basis of Kⁿ (with respect to the standard scalar products on these spaces).

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) = σ_i u_i, for i = 1,...,min(m,n), where σ_i is the i-th diagonal entry of Σ, and T(v_i) = 0 for i > min(m,n).

The geometric content of the SVD theorem can thus be summarized as follows: for every linear map T: Kⁿ → K^m one can find orthonormal bases of Kⁿ and K^m such that T maps the i-th basis vector of Kⁿ to a non-negative multiple of the i-th basis vector of K^m, and sends the left-over basis vectors to zero. With respect to these bases, the map T is therefore represented by a diagonal matrix with non-negative real diagonal entries.

Rank determination

The number of non-zero singular values is equal to the rank r of 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.It is also used in out-put only modal analsis where the non scaled mode shapes can be determined from the singular vectors.

Computation of the SVD

The LAPACK subroutine DGESVD (http://www.netlib.org/lapack/double/dgesvd.f) represents a typical approach to the computation of the singular value decomposition. If the matrix has more rows than columns a QR decomposition is first performed. The factor R is then reduced to a bidiagonal matrix. The desired singular values and vectors are then found by performing a bidiagonal QR iteration, using the LAPACK routine DBDSQR (http://www.netlib.org/lapack/double/dbdsqr.f) (See Demmel and Kahan for details).

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://ocw.mit.edu/OcwWeb/Mathematics/18-06Linear-AlgebraFall2002/VideoLectures/index.htm) 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.
• Chapter from "Numerical Recipes in C" (http://www.library.cornell.edu/nr/bookcpdf/c2-6.pdf) gives more information about implementation and applications of SVD.

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.
• Demmel J. and Kahan W. Computing Small Singular Values of Bidiagonal Matrices With Guaranteed High Relative Accuracy, SIAM J. Sci. Statist. Comput. vol. 11, no. 5, 1990 pp. 873-912.de:Singulärwertzerlegung