Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!
Get Started for Free

rid

Randomized interpolative decomposition (ID).

Description

Randomized interpolative decomposition.

Usage

rid(A, k = NULL, mode = "column", p = 10, q = 0, idx_only = FALSE, rand = TRUE)

Arguments

A

array_like;
numeric (m, n) input matrix (or data frame).
If the data contain NAs na.omit is applied.
k

integer, optional;
number of rows/columns to be selected. It is required that k is smaller or equal to min(m,n).
mode

string c('column', 'row'), optional;
columns or rows ID.
p

integer, optional;
oversampling parameter (default p=10).
q

integer, optional.
number of additional power iterations (default q=0).
idx_only

bool, optional;
if (TRUE), the index set idx is returned, but not the matrix C or R. This is more memory efficient, when dealing with large-scale data.
rand

bool, optional;
if (TRUE), a probabilistic strategy is used, otherwise a deterministic algorithm is used.

Details

Algorithm for computing the ID of a rectangular (m, n) matrix A, with target rank k << min(m,n). The input matrix is factored as

A = C * Z

using the column pivoted QR decomposition. The factor matrix C is formed as a subset of columns of A, also called the partial column skeleton. If mode='row', then the input matrix is factored as

A = Z * R

using the row pivoted QR decomposition. The factor matrix R is now formed as a subset of rows of A, also called the partial row skeleton. The factor matrix Z contains a (k, k) identity matrix as a submatrix, and is well-conditioned.

If rand='TRUE' a probabilistic strategy is used to compute the decomposition, otherwise a deterministic algorithm is used.

Value

rid returns a list containing the following components:

C

array_like;
column subset C = A[,idx], if mode='column'; array with dimensions (m, k).

R

array_like;
row subset R = A[idx, ], if mode='row'; array with dimensions (k, n).

Z

array_like;
well conditioned matrix; Depending on the selected mode, this is an array with dimensions (k,n) or (m,k).

idx

array_like;
index set of the k selected columns or rows used to form C or R.

pivot

array_like;
information on the pivoting strategy used during the decomposition.

scores

array_like;
scores of the columns or rows of the input matrix A.

scores.idx

array_like;
scores of the k selected columns or rows in C or R.

Author(s)

N. Benjamin Erichson, erichson@uw.edu

References

  • [1] N. Halko, P. Martinsson, and J. Tropp. "Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions" (2009). (available at arXiv https://arxiv.org/abs/0909.4061).

  • [2] N. B. Erichson, S. Voronin, S. L. Brunton and J. N. Kutz. 2019. Randomized Matrix Decompositions Using R. Journal of Statistical Software, 89(11), 1-48. doi: 10.18637/jss.v089.i11.

See Also

Examples

## Not run: 
# Load test image
data("tiger")

# Compute (column) randomized interpolative decompsition
# Note that the image needs to be transposed for correct plotting
out <- rid(t(tiger), k = 150)

# Show selected columns 
tiger.partial <- matrix(0, 1200, 1600)
tiger.partial[,out$idx] <- t(tiger)[,out$idx]
image(t(tiger.partial), col = gray((0:255)/255), useRaster = TRUE)

# Reconstruct image
tiger.re <- t(out$C %*% out$Z)

# Compute relative error
print(norm(tiger-tiger.re, 'F') / norm(tiger, 'F')) 

# Plot approximated image
image(tiger.re, col = gray((0:255)/255))

## End(Not run)
rsvd

Randomized Singular Value Decomposition

v1.0.5
GPL (>= 3)
Authors
N. Benjamin Erichson [aut, cre]
Initial release
2021-04-11

We don't support your browser anymore

Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.