Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I can't find a single solid explanation of how to implement this -- whitepapers too detailed/confusing. Closest I came to an answer was this:

http://www.hep.ucl.ac.uk/~bino/libbpm/doc/pro/html/gsl__linalg_8c-source.html

see:

[1] gsl_linalg_bidiag_decomp

[2] gsl_linalg_SV_decomp (which calls [1])

Which perform it, but really, really obfusticate the process underneath.

share|improve this question
1  
I found the explanation in books.google.com/books?id=FtC9rHW7ORMC&pg=PA217 clear enough; which parts don't you understand? –  J. M. Sep 19 '10 at 20:35
2  
If you want to learn the ins-and-outs of how to compute the SVD then a great way is write your own algorthim. If you want to actually use SVD as a means to an end then software packages will typically out-perform your implementation. –  alext87 Sep 20 '10 at 7:07
    
Thanks guys I did implement my own with your help (esp. the google books link). –  dougvk Sep 30 '10 at 2:08

1 Answer 1

up vote 2 down vote accepted

Golub-Kahan Bidiagonalisation

In this process householder reflectors are applied alternatively on the left and then the right. The $i^{\text{th}}$ left reflector introduces zeros below the diagonal in the $i^{\text{th}}$ column. The $i^{\text{th}}$ right reflector introduces zeros to the right of the first super-diagonal in the $i^{\text{th}}$ row.

In software packages I suspect they use a mixture of this Golub-Kahan bidiagonalisation and a process called Lawson-Hanson-Chan (LHC) bidiagonalisation depending on the size of the matrix.

Computing the SVD

The first phase of computing the SVD is bidiagonalising the matrix. Then the SVD of the bidiagonal matrix is determined by a process very similar to the QR algorithm. This process is described in Golub and Kahn, "Calculating the singular values and pseudo-inverse of a matrix" (1960). Since this paper there have been some alterations to provide better accuracy when the singular values are small, see Demmel and Kahan: "Accurate singular values of bidiagonal matrices" (1990)

Having been lectured by N. Trefethen on this very subject he briefly mentioned a divide-and-conquer type algorithm was now state-of-the-art though I don't know much about the details.

share|improve this answer
1  
The divide and conquer approach is the straightforward application of the very same technique for the symmetric tridiagonal eigenproblem to a Golub-Kahan matrix, a matrix with zero diagonal and the alternating diagonal and off-diagonal entries of a bidiagonal matrix as off-diagonal entries. The key thing about a Golub-Kahan tridiagonal is that its positive eigenvalues correspond to the singular values of the associated bidiagonal. –  J. M. Sep 20 '10 at 8:55
    
In general, all the tricks for computing the eigenvalues of a symmetric tridiagonal matrix carry over to the bidiagonal SVD naturally by using them on the Golub-Kahan tridiagonal. As for bidiagonal SVD's state-of-the-art, the best one yet is "differential quotient difference", constructed by Parlett and Fernando from the old "quotient-difference" algorithm of Heinz Rutishauser. –  J. M. Sep 20 '10 at 8:57
    
@J.M. Thanks that is interesting. I'm going to get myself up to speed with all this now. (+1) –  alext87 Sep 20 '10 at 10:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.