randomColumnSpace {RESET}

Implementation of a sparse powered randomized algorithm for computing a basis for the column space of a matrix.

Description

Computes a rank k approximation of the column space of an n-by-p input matrix X using a sparse randomized embedding with optional subspace power iterations. Specifically, a p-by-k random text matrix O is created where all elements are generated as independent N(0,1) or U(0,1) random variables except for elements designated as sparse via the specified sparsity.structure, which are set to 0. If a sparse structure is used, the non-zero elements can alternatively be set to the constant value of 1 for a non-random embedding. The test matrix is used to create an n-by-k sketch matrix Y as Y=XO. If q>0, subspace power iterations are performed on Y via algorithm 2 in the paper by Erichson, et al. associated with the rsvd R package (https://doi.org/10.18637/jss.v089.i11). The returned rank k column space approximation of X is then generated via a column-pivoted QR decomposition of Y.

Usage

    randomColumnSpace(X, k=2, q=0, sparsity.structure=NULL, test.dist="normal")

Arguments

X

An n-by-p target matrix.

k

Target rank. Defaults to 2.

q

Number of power iterations. Defaults to 0.

sparsity.structure

Optional sparsity structure. Should be specified as a vector whose elements are the indices (in column-oriented format) of the non-sparse elements in the p x k random test matrix O. If not specified, O will be dense.

test.dist

Type of random variable used to populate non-sparse elements of random test matrix O. Must be either 'normal' for N(0,1) RVs, 'uniform' for U(0,1) RVs or 'constant' for the value of 1. Note that 'constant' should only be used if sparsity.structure is specified.

Value

A n-by-k estimate of the column space of X.

See Also

randomSVD

Examples

  # Simulate a 100-by-100 matrix of random Poisson data
  X = matrix(rpois(10000, lambda=2), nrow=100)
  # Create a random sparsity structure for 100-by-5 random test matrix; half elements will be 0
  sparsity.structure = sample(1:500, 250, replace=TRUE)
  # Compute rank 5 estimate of column space of X using a sparse test matrix
  Q = randomColumnSpace(X,k=5,sparsity.structure=sparsity.structure)
  # Compute using a dense test matrix with U(0,1) RVs
  Q = randomColumnSpace(X,k=5,test.dist="uniform")