For sparse matrices, almost the only requirement is a good dense SVD. If you have an SVD that is very fast for tall skinny matrices, that would be excellent. If not, that can be worked around.
The basic idea is that right multiplication by a tall skinny random array (which is never stored explicitly) gives a tall skinny matrix to decompose. If the tall random array has a small multiple more columns than you want singular values, then you can say with high probability that the left singular vectors of the product contains the left singular vectors of the original matrix. Peeling these off and doing an SVD to the short wide result gives you the singular values and right singular vectors. This is vastly simpler than the more commonly used Lanczos algorithm and more susceptible to performance improvement due to BLAS improvements, threading or parallelization because it involves matrix-matrix products rather than matrix-vector products. These techniques are described here http://arxiv4.library.cornell.edu/abs/0909.4061 On Sun, Mar 14, 2010 at 12:21 PM, Luc Maisonobe <luc.maison...@free.fr>wrote: > The first one is related to sparse matrix and we don't have an answer > yet. >
