randomized Singular Value Decomposition

Extremely fast computation of truncated SVD
2.2K Downloads
Updated 15 Sep 2014

View License

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 !

Cite As

Antoine Liutkus (2024). randomized Singular Value Decomposition (https://www.mathworks.com/matlabcentral/fileexchange/47835-randomized-singular-value-decomposition), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2012b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Eigenvalues in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.0.0.0