randomized Singular Value Decomposition
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 !
引用格式
Antoine Liutkus (2024). randomized Singular Value Decomposition (https://www.mathworks.com/matlabcentral/fileexchange/47835-randomized-singular-value-decomposition), MATLAB Central File Exchange. 检索来源 .
MATLAB 版本兼容性
平台兼容性
Windows macOS Linux类别
- MATLAB > Mathematics > Linear Algebra > Eigenvalues >
标签
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!版本 | 已发布 | 发行说明 | |
---|---|---|---|
1.0.0.0 |