rid: Randomized interpolative decomposition (ID). In Benli11/rPCA: Randomized Singular Value Decomposition

Description

Randomized interpolative decomposition.

Usage

 ```1 2``` ```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, [email protected]

References

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

•  N. B. Erichson, S. Voronin, S. Brunton, J. N. Kutz. "Randomized matrix decompositions using R" (2016). (available at 'arXiv http://arxiv.org/abs/1608.02148).

`rcur`,
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23``` ```## 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) ```