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

array_like; numeric $(m, n)$ input matrix (or data frame). If the data contain $N A$ s na.omit is applied.

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

mode

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

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

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

idx_only

bool, optional; if ( $T R U E$ ), 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 ( $T R U E$ ), a probabilistic strategy is used, otherwise a deterministic algorithm is used.

Value

rid returns a list containing the following components:

C: array_like; column subset $C = A [, i d x]$ , if mode='column'; array with dimensions $(m, k)$ .
R: array_like; row subset $R = A [i d x,]$ , 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$ .

Details

Algorithm for computing the ID of a rectangular $(m, n)$ matrix $A$ , with target rank $k << m i n (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 $r a n d =^{'} T R U E^{'}$ a probabilistic strategy is used to compute the decomposition, otherwise a deterministic algorithm is used.

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. 10.18637/jss.v089.i11.

Examples

Run this code

# 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))
# }

Run the code above in your browser using DataLab

Last chance! 50% off unlimited learning