26
$\begingroup$

What is the best way to compute singular value decomposition (SVD) of a very large positive matrix (65M x 3.4M) where data is extremely sparse?

Less than 0.1% of the matrix is non zero. I need a way that:

  • will fit into memory (I know that online methods exists)
  • will be computed in a reasonable time: 3,4 days
  • will be accurate enough however accuracy is not my main concern and I would like to be able to control how much resources I put into it.

It would be great to have a Haskell, Python, C# etc. library which implements it. I am not using mathlab or R but if necessary I can go with R.

$\endgroup$
  • 3
    $\begingroup$ How much memory do you have? 0.1% of 65M*3.4M is still 221e9 non zero values. If you use 4 bytes per value, that is still more than 55 gb assuming no overhead, so the sparsity still doesn't solve the problem... Do you need to load the whole set into memory at once? $\endgroup$ – Bitwise Oct 26 '12 at 18:02
  • $\begingroup$ I should have been more precise. No more than 250-500mb with 32-bit integer. Probably much less, but the dimensionalilty is the problem as I understand it. I have a 16GB machine. $\endgroup$ – Sonia Oct 26 '12 at 18:05
  • $\begingroup$ How about this? quora.com/… $\endgroup$ – Bitwise Oct 26 '12 at 19:16
  • $\begingroup$ This webpage links to a Python library which implements "a fast, incremental, low-memory, large-matrix SVD algorithm": en.wikipedia.org/wiki/Latent_semantic_analysis $\endgroup$ – Bitwise Oct 26 '12 at 19:56
  • $\begingroup$ See also stats.stackexchange.com/questions/2806. $\endgroup$ – amoeba May 23 '17 at 19:16
21
$\begingroup$

If it fits into memory, construct a sparse matrix in R using the Matrix package, and try irlba for the SVD. You can specify how many singular vectors you want in the result, which is another way to limit the computation.

That's a pretty big matrix, but I've had very good results with this method in the past. irlba is pretty state-of-the-art. It uses the implicitly restarted Lanczos bi-diagonalization algorithm.

It can chew through the netflix prize dataset (480,189 rows by 17,770 columns, 100,480,507 non-zero entries) in milliseconds. You dataset is ~ 200,000 times bigger than the Netflix dataset, so it take significantly longer than that. It might be reasonable to expect that it could do the computation in a couple of days.

$\endgroup$
  • $\begingroup$ the data matrix fits into memory, will irlba will handle the decomposition in a memory efficient way as well? $\endgroup$ – Sonia Oct 26 '12 at 17:56
  • $\begingroup$ @Sonia: irlba is very memory efficient: it computes an approximate solution, you can limit the number of singular vectors, and it was designed to work on sparse matrices. As far as I know, it's as fast as you're going to get for computing partial SVDs. $\endgroup$ – Zach Oct 26 '12 at 18:05
  • $\begingroup$ @Sonia: Good luck! $\endgroup$ – Zach Oct 26 '12 at 18:14
  • $\begingroup$ Gave it a try - out of memory... I will compute a triangle block form before running it. $\endgroup$ – Sonia Nov 3 '12 at 13:13
  • $\begingroup$ @Sonia do you have it stored as a sparse Matrix? Try limiting the number of singular values you compute... maybe just look at the top 10? $\endgroup$ – Zach Nov 3 '12 at 18:43
-2
$\begingroup$
  1. Apache Spark: https://spark.apache.org/docs/1.1.0/mllib-data-types.html
  2. Mahout Samsara (out of core runs over Spark and others) : https://mahout.apache.org/users/environment/out-of-core-reference.html
  3. SciDB (for really big data): http://www.paradigm4.com/scidb-how-linear-algebra-operations-scale/
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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