On the fly/matrix free SVD of large sparse matrix

Question

I am trying to apply SVD to large sparse matrices. I already compared the performances of Propack and irlba to those of the matlab svd and svds. These two packages enhance significantly the computing time but I still have to handle the memory issue. Therefore, I am looking for a free matrix SVD algorithm which allows me to compute M largest singulars values on the fly without having to compute the entire matrix at the entry of the SVD. I read about Incremental SVD http://www.math.fsu.edu/~cbaker/IncPACK/ and also saw this topic mentioning using Lanczos with Fast Block matrix-vector multiplication via FFTs instead of the SVD SVD of large block-hankel matrix but since I am not specialist I still can not see an easy way to compute the SVD without bearing the memory cost of computing the entire matrix. Can someone help me to find out?

Answer 1

Incremental SVD methods will only help you if you want to calculate a truncated (preferably low-rank) SVD. The memory requirements for these algorithms are more or less the ability to store a single column of your large sparse matrix plus the current truncated SVD. If you attempt to calculate the whole SVD with an incremental method, you won't save that much memory; however, if you only calculate the left singular vectors and singular values, you could conceivably save memory if your matrix has many more columns than rows.