2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I found the explanation in books.google.com/books?id=FtC9rHW7ORMC&pg=PA217 clear enough; which parts don't you understand? $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 19, 2010 at 20:35
  • 2
    $\begingroup$ 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. $\endgroup$
    – alext87
    Commented Sep 20, 2010 at 7:07
  • $\begingroup$ Thanks guys I did implement my own with your help (esp. the google books link). $\endgroup$
    – dougvk
    Commented Sep 30, 2010 at 2:08

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 20, 2010 at 8:55
  • $\begingroup$ 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. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 20, 2010 at 8:57
  • $\begingroup$ @J.M. Thanks that is interesting. I'm going to get myself up to speed with all this now. (+1) $\endgroup$
    – alext87
    Commented Sep 20, 2010 at 10:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .