rsvd: Randomized Singular Value Decomposition .

Description

Compute the approximate low-rank singular value decomposition (SVD) of a rectangular matrix.

Usage

rsvd(A, k = NULL, nu = NULL, nv = NULL, p = 5, q = 2, method = "standard", sdist = "unif", vt = FALSE)

Arguments

array_like a real/complex input matrix (or data frame), with dimensions $(m, n)$.

int, optional determines the target rank of the low-rank decomposition and should satisfy $k << min(m,n)$.

int, optional the number of left singular vectors to be computed. This must be between $0$ and $k$.

int, optional the number of right singular vectors to be computed. This must be between $0$ and $k$.

int, optional oversampling parameter for (default $p=5$).

int, optional number of power iterations (default $q=2$).

method

str c('standard', 'fast'), optional 'standard' : (default): Standard algorithm as described in [1, 2]. 'fast' : Version II algorithm as described in [2].

sdist

str c('normal', 'unif'), optional Specifies the sampling distribution. 'unif' : (default) Uniform `[-1,1]`. 'normal' : Normal `~N(0,1)`.

bool ($TRUE$, $FALSE$), optional $TRUE$ : returns the transposed right singular vectors $vt$. $FALSE$ : (default) returns the right singular vectors as $v$, this is the format as svd returns $v$.

.............

Value

u: array_like Right singular values; array with dimensions $(m, k)$.
d: array_like Singular values; 1-d array of length $(k)$.
v (or vt): array_like Left singular values; array with dimensions $(n, k)$. Or if $vt=TRUE$, array with dimensions $(k, n)$.
.............: .

Details

The singular value decomposition (SVD) plays a central role in data analysis and scientific computing. Randomized SVD (rSVD) is a fast algorithm to compute the the approximate low-rank SVD of a rectangular $(m,n)$ matrix $A$ using a probablistic algorithm. Given a target rank $k << n$, rsvd factors the input matrix $A$ as $A = U * diag(d) * V'$. The right singluar vectors are the columns of the real or complex unitary matrix $U$ . The left singular vectors are the columns of the real or complex unitary matrix $V$. The singular values $d$ are non-negative and real numbers.

The parameter $p$ is a oversampling parameter to improve the approximation. A value between 2 and 10 is recommended and $p=5$ is set as default.

The parameter $q$ 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 archive good results, however, computing power iterations increases the computational time. The number of power iterations is set to $q=2$ by default.

If $k > (min(n,m)/1.5)$, a deterministic partial or truncated svd algorithm might be faster.

References

[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).

Examples

Run this code

library(rsvd)
set.seed(123)

#Create real random test matrix with dimension (m, n) and rank k
m = 10
n = 3
k = 5
A <- matrix(runif(m*k), m, k)
A <- A %*% t(A)
A <- A[,1:n]

#Randomized SVD, no low-rank approximation
s <- rsvd(A)
Atilde = s$u %*% diag(s$d) %*% t(s$v)
100 * norm( A - Atilde, 'F') / norm( Atilde,'F') #Percentage reconstruction error << 1e-8

#Randomized SVD, low-rank approximation k=3
s <- rsvd(A, k=3)
Atilde = s$u %*% diag(s$d) %*% t(s$v)
100 * norm( A - Atilde, 'F') / norm( Atilde,'F') #Percentage reconstruction error << 1e-8

#Randomized SVD, low-rank approximation k=2
s <- rsvd(A, k=2)
Atilde = s$u %*% diag(s$d) %*% t(s$v)
100 * norm( A - Atilde, 'F') / norm( Atilde,'F') #Percentage reconstruction error < 3.5%

Run the code above in your browser using DataLab