Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a fairly large array, a billion or so by 500,000 array. I need to calculate the singular value decomposition of this array. The problem is that my computer RAM will not be able to handle the whole matrix at once. I need an incremental approach of calculating the SVD. This would mean that I could take one or a couple or a couple hundred/thousand (not too much though) rows of data at one time, do what I need to do with those numbers, and then throw them away so that I can address memory toward getting the rest of the data.

People have posted a couple of papers on similar issues such as http://www.bradblock.com/Incremental_singular_value_decomposition_of_uncertain_data_with_missing_values.pdf and http://www.jofcis.com/publishedpapers/2012_8_8_3207_3214.pdf.

I am wondering if anyone has done any previous research or has any suggestions on how should go on approaching this? I really do need the FASTEST approach, without losing too much accuracy in the data.

share|improve this question
    
As long as I know there is paper about such. I dont remember but y colleagues should know. From my experience I used SVD and it is so slow in MATLAB. How big is your matrix? –  Seyhmus Güngören Aug 6 '12 at 19:01
    
@SeyhmusGüngören it will be nearly a billion by 500,000 big, which is why I need to take in a couple of entries at a time. Overall, there are going to be around 500 trillion numbers. –  mathguy Aug 6 '12 at 19:05
    
Ok. I see the problem. You are right. One needs too much memory for such a calculation. If you dont receive any answer until tomorrow, I will ask it to my colleagues and let you know about a possible solution. –  Seyhmus Güngören Aug 6 '12 at 20:18
    
@SeyhmusGüngören That would be very much appreciated! Thank you so much. –  mathguy Aug 6 '12 at 22:49
    
You might want to see this. –  J. M. Aug 7 '12 at 0:30
show 7 more comments

2 Answers

up vote 2 down vote accepted
+50

You could compute the SVD of randomly chosen submatrices of your original matrix, as shown e.g. in the 2004 paper by Drineas, Frieze, Kannan, Vempala and Vinay, and scale the result to obtain an approximate SVD of the original matrix. There has been quite a bit of additional work on randomized matrix methods since then. The grandfather of all this is the Kaczmarz method of 1939 for solving the problem $Ax = b$, if only one row of $A$ at a time is accessible.

It might also be useful to check if maybe a few top singular values are sufficient for your purposes. If so, Lanczos methods (e.g.) will result in additional time savings.

share|improve this answer
    
I'm really liking Lanczos method so far. I think I might go with that! Thank you for your help! –  mathguy Aug 16 '12 at 3:14
add comment

So is there any other property that the matrix has? For example, is it sparse or is it symmetric, real/complex, etc... As there are optimized algorithms for various situations, SVD may not be the best option -- it would be helpful to know what you are trying to get from the SVD.

share|improve this answer
    
This is more of a comment than an answer... –  J. M. Aug 15 '12 at 4:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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