next up previous contents index
Next: Generalized Symmetric Definite Eigenproblems Up: Computational Routines Previous: EigenvaluesEigenvectors, and Schur

Singular Value Decomposition

 

Let A be a general real m-by-n matrix. The singular value decomposition (SVD) of A is the factorization  tex2html_wrap_inline14119, where U and V are orthogonal and tex2html_wrap_inline14125, tex2html_wrap_inline14127, with tex2html_wrap_inline14129. If A is complex, its SVD is tex2html_wrap_inline14133, where U and V are unitary and tex2html_wrap_inline12820 is as before with real diagonal elements. The tex2html_wrap_inline12826 are called the singular values , the first r columns of V the right singular vectors , and the first r columns of U the left singular vectors .

The routines described in this section, and listed in table 3.10, are used to compute this decomposition. The computation proceeds in the following stages:

  1. The matrix A is reduced to bidiagonal  form: tex2html_wrap_inline14153 if A is real (tex2html_wrap_inline14157 if A is complex), where tex2html_wrap_inline14161 and tex2html_wrap_inline14163 are orthogonal (unitary if A is complex), and B is real and upper-bidiagonal when tex2html_wrap_inline13306 and lower bidiagonal when m < n, so that B is nonzero only on the main diagonal and either on the first superdiagonal (if tex2html_wrap_inline13306) or the first subdiagonal (if m<n).
  2. The SVD of the bidiagonal matrix B is computed: tex2html_wrap_inline14181, where tex2html_wrap_inline14183 and tex2html_wrap_inline14185 are orthogonal and tex2html_wrap_inline12820 is diagonal as described above. The singular vectors of A are then tex2html_wrap_inline14191 and tex2html_wrap_inline14193.

The reduction to bidiagonal form is performed by the subroutine PxGEBRD and the SVD of B is computed using the LAPACK routine xBDSQR.       

The routine PxGEBRD represents tex2html_wrap_inline14161 and tex2html_wrap_inline14163 in factored form as products of elementary reflectors,   as described in section 3.4. If A is real, the matrices tex2html_wrap_inline14161 and tex2html_wrap_inline14163 may be multiplied by other matrices without forming tex2html_wrap_inline14161 and tex2html_wrap_inline14163 using routine PxORMBR  . If A is complex, one instead uses PxUNMBR  .

If tex2html_wrap_inline14213, it may be more efficient to first perform a QR factorization of A, using the routine PxGEQRF    , and then to compute the SVD of the n-by-n matrix R, since if A = QR and tex2html_wrap_inline14227, then the SVD of A is given by tex2html_wrap_inline14231. Similarly, if tex2html_wrap_inline14233, it may be more efficient to first perform an LQ factorization of A, using xGELQF. These preliminary QR and LQ      factorizations are performed by the driver PxGESVD.     

The SVD may be used to find a minimum norm solution  to a (possibly) rank-deficient linear least squares   problem (3.1). The effective rank, k, of A can be determined as the number of singular values which exceed a suitable threshold. Let tex2html_wrap_inline14247 be the leading k-by-k submatrix of tex2html_wrap_inline12820, and tex2html_wrap_inline14255 be the matrix consisting of the first k columns of V. Then the solution is given by
displaymath14109
where tex2html_wrap_inline13502 consists of the first k elements of tex2html_wrap_inline14265. tex2html_wrap_inline14267 can be computed by using PxORMBR.   

  table2093
Table 3.10: Computational routines for the singular value decomposition


next up previous contents index
Next: Generalized Symmetric Definite Eigenproblems Up: Computational Routines Previous: EigenvaluesEigenvectors, and Schur

Susan Blackford
Tue May 13 09:21:01 EDT 1997