Description Usage Arguments Details Value Note Author(s) References Examples
Compute the near-optimal low-rank singular value decomposition (SVD) of a rectangular matrix. The algorithm follows a randomized approach.
1 |
A |
array_like |
k |
int, optional |
l |
int, optional |
its |
int, optional |
sdist |
str c('normal', 'unif'), optional |
Randomized SVD (randSVD) is a fast algorithm to compute the approximate low-rank SVD of
a rectangular (m,n) matrix A using a probabilistic algorithm.
Given the decided rank k << n, rSVD
factors the input matrix A as
A = U * diag(S) * V', which is the typical SVD form. Precisely, the columns of
U are orthonormal, as are the columns of V, the entries of S are all nonnegative,
and the only nonzero entries of S appear in non-increasing order on its diagonal. The
dimensions are: U is (m,k), V is (n,k), and S is (k,k), when A
is (m,n).
Increasing its or l improves the accuracy of the approximation USV' to A.
The parameter its specifies the number of normalized power iterations (subspace iterations) to reduce the approximation error. This is recommended if the the singular values decay slowly. In practice 1 or 2 iterations achieve good results, however, computing power iterations increases the computational time. The number of power iterations is set to its=2 by default.
randSVD
returns a list containing the following three components:
d |
array_like |
u |
matrix |
v |
matrix |
The singular vectors are not unique and only defined up to sign (a constant of modulus one in the complex case). If a left singular vector has its sign changed, changing the sign of the corresponding right vector gives an equivalent decomposition.
L. Rimella, lorenzo.rimella@hotmail.it
[1] N. Halko, P. Martinsson, and J. Tropp.
"Finding structure with randomness: probabilistic
algorithms for constructing approximate matrix
decompositions" (2009).
(available at arXiv http://arxiv.org/abs/0909.4061).
[2] S. Voronin and P.Martinsson.
"RSVDPACK: Subroutines for computing partial singular value
decompositions via randomized sampling on single core, multi core,
and GPU architectures" (2015).
(available at 'arXiv http://arxiv.org/abs/1502.05366).
[3] N. Benjamin Erichson.
"Randomized Singular Value Decomposition (rsvd): R package" (2016).
(available in the CRAN).
[4] Nathan Halko, Per-Gunnar Martinsson, and Joel Tropp.
"Finding structure with randomness: Stochastic algorithms for
constructing approximate matrix decompositions" (2009).
(available at http://arxiv.org).
[5] V. Rokhlin, A. Szlam, M. Tygert.
"A randomized algorithm for principal component analysis" (2009).
(available at https://arxiv.org/abs/0809.2274).
The implementation of rand SVD is inspired by the MatLab implementation
of RandPCA by M. Tygert.
1 2 3 4 5 6 7 8 9 10 11 12 13 | #Simulate a general matrix with 1000 rows and 1000 columns
vy= rnorm(1000*1000,0,1)
y= matrix(vy,1000,1000,byrow=TRUE)
#Compute the randSVD for the first hundred components of the matrix y and measure the time
start.time <- Sys.time()
prova1= randSVD(y,k=100)
Sys.time()- start.time
#Compare with a classical SVD
start.time <- Sys.time()
prova2= svd(y)
Sys.time()- start.time
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.