randomized Singular Value Decomposition

Extremely fast computation of truncated SVD

This functions implements a fast truncated SVD.
We often want to compute singular value decompositions. But most of the time, we actually don't need all the singular vectors/values as in Principal Components Analysis.

This is also justified by the fact that many matrices occuring in practice do exhibit some kind of structure that leads to only a few singular values actually being non-negligible.

Recent research has shown that when we want a truncated SVD, randomized algorithms can yield an incredible amount of acceleration.

usage :

input:
* A : matrix whose SVD we want
* K : number of components to keep

output:
* U,S,V : classical output as the builtin svd matlab function

Here is a small example for a 2000x2000 matrix of rank 100 on my small laptop computer:

>> A = randn(2000,100)*randn(100,2000);
>> tic; [U1,S1,V1] = svd(A); toc
Elapsed time is 6.509186 seconds.

>> tic; [U2,S2,V2] = rsvd(A,150); toc
Elapsed time is 0.238175 seconds.

>> norm(U1*S1*V1'-U2*S2*V2')

ans =

2.3591e-11

So in that case a near 30x speed improvement. It just gets crazy when your matrix gets big...

You'll find more information about these breakthrough algorithms in a nice paper by Halko et al. : "finding structure through randomness"

enjoy !