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 matrixmatrix products
rather than matrixvector 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.Maisonobe@free.fr>wrote:
> The first one is related to sparse matrix and we don't have an answer
> yet.
>
