next up previous
Next: Candidate Methods for Up: Introduction Previous: Singular Value Decomposition

1.2 Related Eigenvalue Problems

  The SVD(A) may be computed from two equivalent eigenvalue decompositions:
  1. Consider the 2-cyclic matrix

     

    If , it can be shown that the eigenvalues of C are the n pairs , where is a singular value of A, with additional zero eigenvalues if m > n. The multiplicity of the zero eigenvalue of C is m+n-2r, where .

  2. Alternatively, the SVD(A) can be computed indirectly by the eigenpairs of either the matrix or the matrix . If are linearly independent eigenvectors of so that , then is the nonzero singular value of A corresponding to the right singular vector . The corresponding left singular vector, , is then obtained as . Similarly, if are linearly independent eigenvectors of so that , then is the nonzero singular value of A corresponding to the left singular vector . The corresponding right singular vector, , is then obtained as .

Computing the SVD(A) using one of the eigenvalue problems above has its own advantages and disadvantages. The matrix is of order n, whereas the two-cyclic matrix C defined in Equation (2) is of order . If the matrix A is over-determined, i.e. , the smaller memory requirements for the matrix make it the more attractive choice for computing the SVD. However, this scheme only gives the right singular vectors, and the left singular vectors must be obtained by scaling .

The eigenvectors of the two-cyclic matrix, on the other hand, are of the form , and directly give complete information about the singular triplet . Also, each eigenvalue of is , forcing a clustering of the singular value approximations when . Evaluating the SVD from the eigen-decomposition of is thus most suited for problems when only the largest (or dominant) singular values are desired, with a potential loss of accuracy for the smaller singular values. Using the two-cyclic matrix C does not have this drawback, however, at the price of a larger memory requirement.



next up previous
Next: Candidate Methods for Up: Introduction Previous: Singular Value Decomposition



Michael W. Berry (berry@cs.utk.edu)
Sun May 19 11:34:27 EDT 1996