rcur: Randomized CUR matrix decomposition

In rsvd: Randomized Singular Value Decomposition

Randomized CUR matrix decomposition

Description

Approximate a matrix using selected columns and rows of the original data, joined by a small matrix of coefficients. The selected data retain their correspondence to measured variables and observations. Randomized column selection is useful when the input has low-rank structure and the requested rank is small.

Usage

rcur(A, k = NULL, p = 10, q = 0, idx_only = FALSE, rand = TRUE)

Arguments

A	A real or complex numeric matrix, a numeric data frame, or a matrix from the Matrix package. Rows containing missing values are omitted with a warning; the remaining entries must be finite.
k	A positive integer giving the number of columns and rows to select. The default, NULL, uses min(dim(A)) after missing rows are omitted. Larger requests are capped at this value. A fractional value of at least one is truncated toward zero.
p	A non-negative integer oversampling parameter for randomized column selection. The default is 10. Ignored when rand = FALSE.
q	A non-negative integer number of power iterations for randomized column selection. The default is zero. Ignored when rand = FALSE.
idx_only	Logical. If TRUE, leave C and R as NULL in the returned object. Their indices and the connector U are still computed and returned. The default is FALSE.
rand	Logical. If TRUE (the default), use randomized column selection; otherwise use a deterministic column-pivoted QR decomposition. Row selection from the chosen column matrix is deterministic in both cases.

Details

A column interpolative decomposition (ID) represents a matrix using selected columns and coefficients for combining them. CUR also selects rows, so both sides of the approximation contain subsets of the original data. For an m \times n matrix, these factors are combined as

A \approx C U R.

The m by k matrix C contains actual columns of the input, and the k by n matrix R contains actual rows. These subsets can be examined as measured variables and observations in their original units. The k by k matrix U contains the coefficients that connect the two subsets. Its role differs from that of the orthonormal left singular-vector matrix in a singular value decomposition (SVD).

The algorithm first computes a column interpolative decomposition with rid. It then chooses rows using column-pivoted QR of the conjugate transpose of C. To form the connector, it uses these rows to approximate the interpolation coefficients from the column ID,

U = Z R^{+},

where Z is the interpolation matrix from the column ID. The numerical pseudoinverse excludes negligible singular values using a threshold that depends on matrix dimensions and floating-point precision. This allows the calculation to proceed when the selected subsets are rank deficient, as can happen when k exceeds the input's numerical rank.

Oversampling and power iterations can improve randomized column selection at the cost of more computation. The supplied settings remain fixed; the algorithm does not adjust them to satisfy an error tolerance. Row selection from the chosen column matrix is deterministic in both modes.

The approximation error depends on the input's spectrum and on which subsets are selected, including their conditioning. Column and row selection does not guarantee the smallest possible rank-k error, so inspect the reconstruction residual when choosing a rank. The QR scores describe the selection procedure and have no interpretation as statistical importance scores.

Centering or rescaling changes the matrix used for selection and can therefore change which variables and observations are chosen. The function uses the supplied data without automatic centering or scaling.

Sparse Matrix input is supported. Randomized column selection uses sparse matrix products, but the selected column and row matrices and the connector are dense. With rand = FALSE, column selection also requires a dense input matrix. The option idx_only = TRUE reduces the returned object's size by omitting the selected data. Those data are still used internally to compute U, so this option does not remove their temporary storage. Explicit reconstruction creates a dense matrix.

Set the random seed before a randomized call for a repeatable result in the same computational environment.

Value

A list of class "rcur" with the following components. Dimensions refer to the input after missing-row omission and the effective k after clamping.

C

The dense m by k matrix containing columns C.idx of A. It is NULL when idx_only = TRUE.

R

The dense k by n matrix containing rows R.idx of A. It is NULL when idx_only = TRUE.

U

The dense k by k connector matrix.

C.idx

An integer vector of k selected column indices, in selection order.

R.idx

An integer vector of k selected row indices, in selection order. These index the matrix after rows with missing values have been omitted.

C.scores

Column QR scores in input column order, as returned by rid. Entries without a QR diagonal are NA.

R.scores

The k selected-row QR scores, in the same order as R.idx. Scores for unselected input rows are not returned.

rand

The randomization setting.

Author(s)

N. Benjamin Erichson

References

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. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.18637/jss.v089.i11")}.

N. Halko, P. G. Martinsson, and J. A. Tropp (2009). Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. https://arxiv.org/abs/0909.4061.

See Also

rid, rsvd

Examples

set.seed(42)
A <- matrix(rnorm(60 * 5), 60, 5) %*% matrix(rnorm(5 * 35), 5, 35)
A <- A + 0.01 * matrix(rnorm(length(A)), nrow(A), ncol(A))

fit <- rcur(A, k = 5)
A_cur <- fit$C %*% fit$U %*% fit$R
norm(A - A_cur, "F") / norm(A, "F")
fit$C.idx
fit$R.idx

# idx_only still returns the connector, so reconstruction remains possible.
small <- rcur(A, k = 5, idx_only = TRUE, rand = FALSE)
A_small <- A[, small$C.idx, drop = FALSE] %*% small$U %*%
  A[small$R.idx, , drop = FALSE]
norm(A - A_small, "F") / norm(A, "F")

rsvd documentation built on Nov. 2, 2026, 5:06 p.m.