# Incremental approach of calculating the Singular Value Decomposition

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.

-
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

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.