rid: Randomized interpolative decomposition (ID)

In rsvd: Randomized Singular Value Decomposition

Randomized interpolative decomposition (ID)

Description

Approximate a matrix by expressing its columns or rows as linear combinations of a selected subset of the original data. The selected data and the coefficients of these combinations form an interpolative decomposition. A randomized sketch can reduce the work needed to choose the subset when the target rank is small.

Usage

rid(A, k = NULL, mode = "column", 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 or rows to select. The default, NULL, uses min(dim(A)) after missing rows are omitted. Larger requests are capped at this value. Use a substantially smaller rank to obtain a compressed approximation. A fractional value of at least one is truncated toward zero.
mode	Either "column" (the default) or "row", specifying which type of subset to select.
p	A non-negative integer oversampling parameter, used only when rand = TRUE. The default is 10. The sketch width is bounded by the matrix dimensions.
q	A non-negative integer number of power iterations, used only when rand = TRUE. The default is zero.
idx_only	Logical. If TRUE, leave both selected-data components C and R as NULL. The interpolation matrix Z, indices and scores are still computed and returned. The default is FALSE.
rand	Logical. If TRUE (the default), select the subset using a randomized QB sketch. If FALSE, use column-pivoted QR on the full input, or its conjugate transpose for a row ID.

Details

An interpolative decomposition (ID) retains actual columns or rows, so the selected subset can be examined in the original units of the data. This is useful when the factors should correspond to measured variables or observations. An orthonormal representation of the data is available through rsvd.

A column ID combines the selected columns with coefficients that approximate each input column. For an m \times n matrix, this gives

A \approx C Z.

Here C = A[, idx, drop = FALSE] contains k actual columns, and each column of Z gives the coefficients for one input column. Its selected columns satisfy Z[, idx, drop = FALSE] = diag(k), so the selected data columns are reproduced exactly. A row ID applies the same idea to rows and has the form

A \approx Z R,

R = A[idx, , drop = FALSE] contains the selected rows, and Z[idx, , drop = FALSE] = diag(k). Dimensions and indices in these expressions refer to the input after missing-row omission.

Selection depends on how the data are represented. Centering or rescaling changes the matrix used to choose the subset and can therefore change the selected variables or observations. The function uses the supplied data without automatic centering or scaling.

To reduce the work of subset selection, the randomized algorithm first compresses the input with rqb. It applies column-pivoted QR to the projected factor and selects the first k columns in the resulting pivot order. A row ID applies this procedure to the conjugate transpose, so the pivots identify input rows. Oversampling and power iterations can improve the subspace used for selection, at additional time and memory cost. The supplied parameters remain fixed throughout the calculation; the algorithm does not adjust them to meet an error tolerance.

The interpolation coefficients are computed using a numerical pseudoinverse of the selected QR block. This permits requests for more columns than the numerical rank, including cases where the selected columns are dependent. Neither column-pivoted QR nor this pseudoinverse guarantees an optimal rank-k approximation or uniformly small coefficients. Assess the reconstruction error to determine whether the selected subset meets the accuracy needs of the application. The QR scores describe the selection procedure and have no interpretation as statistical importance scores or probabilities.

With sparse Matrix input, the randomized algorithm forms its dense sketch using sparse matrix products. Returned factors are ordinary dense R matrices. With rand = FALSE, the input is converted to a dense matrix before QR. Forming C %*% Z or Z %*% R also produces a dense reconstruction.

Use set.seed() before a randomized call for a repeatable result in the same computational environment. Pivot choices can differ across numerical libraries when columns have similar scores.

Value

A list of class "rid" with the following components. Here m is the number of complete input rows and k is the effective rank after clamping.

C

The selected m by k column matrix for a column ID, or NULL for a row ID or when idx_only = TRUE.

R

The selected k by n row matrix for a row ID, or NULL for a column ID or when idx_only = TRUE.

Z

The dense interpolation matrix, with dimensions k by n for a column ID or m by k for a row ID.

idx

An integer vector of length k containing the selected column or row indices, in selection order. Row indices refer to the matrix after rows with missing values have been omitted.

pivot

The full QR column-pivot permutation, or the corresponding row permutation for a row ID. Its first k entries are idx.

scores

Absolute diagonal entries of the QR factor, mapped back to input column or row order. Entries without a corresponding QR diagonal are NA, which can occur for rectangular inputs or reduced sketches.

scores.idx

The QR scores of the selected subset, in the same order as idx.

mode, rand

The selection mode and randomization setting.

Author(s)

N. Benjamin Erichson

References

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.

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")}.

See Also

rcur, rqb, 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))

# Column ID: all columns are approximated using five original columns.
fit <- rid(A, k = 5)
A_id <- fit$C %*% fit$Z
norm(A - A_id, "F") / norm(A, "F")
fit$idx
fit$Z[, fit$idx, drop = FALSE]

# Row ID has the opposite factor order.
row_fit <- rid(A, k = 5, mode = "row")
norm(A - row_fit$Z %*% row_fit$R, "F") / norm(A, "F")

# Retain indices and coefficients without returning the selected data.
small <- rid(A, k = 5, idx_only = TRUE, rand = FALSE)
is.null(small$C)
dim(small$Z)

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