API Reference

Sketchy

Sketchy is a randomized linear dimension reduction map that is used to reduce the dimension of the data matrix in the data-streaming setting. It is based on the sketching technique that is used to approximate the Singular Value Decomposition of the data matrix. The Sketchy algorithm is used to compute the SVD of the data matrix in an incremental fashion. For more details see [TYUC2019].

Fields

• V::AbstractArray{T}: Left singular vector matrix.
• Σ::AbstractArray{T}: Singular value matrix.
• W::AbstractArray{T}: Right singular vector matrix.
• Υ::AbstractArray{T}: Test matrix for range (k x m).
• Ω::AbstractArray{T}: Test matrix for corange (k x n).
• Φ::AbstractArray{T}: Test matrix for core (s x m).
• Ψ::AbstractArray{T}: Test matrix for core (s x n).
• Θ::AbstractArray{T}: Gaussian test matrix for error (q x m).
• X::AbstractArray{T}: Corange sketch (k x n).
• Y::AbstractArray{T}: Range sketch (m x k).
• Z::AbstractArray{T}: Core sketch (s x s).
• W::AbstractArray{T}: Error sketch (q x n).
• increment::Function: Single step incremental update function.
• full_increment!::Function: All data incremental update function.

References

• [TYUC2019] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, “Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation,” SIAM J. Sci. Comput., vol. 41, no. 4, pp. A2430-A2463, Jan. 2019, doi: 10.1137/18M1201068.
• [TYUC2019SUP] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, “Suplementary Materials: Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation,” SIAM J. Sci. Comput., vol. 41, no. 4, pp. A2430-A2463, Jan. 2019, doi: 10.1137/18M1201068.

gaussian_rng(m, n)

Standard Gaussian random matrix generator (default).

rademacher_rng(m, n)

Rademacher random matrix (entries are ±1 with equal probability). More efficient than Gaussian for some applications.

rsvd(A::AbstractArray, k::Int; p::Int=5, q::Int=0, 
     rng::Union{DimRedux,Function}=randn, 
     transpose_trick::Bool=true)

Compute a rank-k randomized SVD approximation of matrix A using power iterations and orthonormalization for improved accuracy.

Arguments

• A::AbstractArray: Input matrix (m x n)
• k::Int: Target rank for the approximation

Keyword Arguments

• p::Int=5: Oversampling parameter (samples k+p random vectors)
• q::Int=0: Number of power iterations (0 means no power iterations)
• rng::Union{DimRedux,Function}=Gauss: Random matrix generator function with signature (nrows, ncols)
• transpose_trick::Bool=true: Use transpose trick when m >> n for efficiency

Returns

• V: Left singular vectors (m x k)
• Σ: Singular values (vector of length k)
• W: Right singular vectors (n x k)

Examples

# Basic usage with default Gaussian random matrix
V, Σ, W = rsvd(A, 50)

# With power iterations for better accuracy
V, Σ, W = rsvd(A, 50, q=2)

# With custom random matrix (e.g., sparse random)
using SparseArrays
sparse_rng(m, n) = sprandn(m, n, 0.1)  # 10% density
V, Σ, W = rsvd(A, 50, rng=sparse_rng)

# With Rademacher (±1) random matrix (faster generation)
V, Σ, W = rsvd(A, 50, rng=rademacher_rng)

# With SRFT (Subsampled Randomized Fourier Transform) - very efficient
V, Σ, W = rsvd(A, 50, rng=srft_rng, q=1)

rsvd_adaptive(A, k; tol=1e-10, max_iter=10, p=5, q=0, rng=randn)

Adaptive randomized SVD that automatically determines the rank based on singular value decay.

Arguments

• A: Input matrix
• k: Initial target rank estimate

Keyword Arguments

• tol::Float64=1e-10: Tolerance for singular value cutoff
• max_iter::Int=10: Maximum number of adaptive iterations
• p::Int=5: Oversampling parameter
• q::Int=0: Number of power iterations
• rng::Function=randn: Random matrix generator

Returns

• U, S, V: SVD factors where rank is automatically determined

sparse_gaussian_rng(density)

Create a sparse Gaussian random matrix generator with specified density.

sparse_rng(m, n; zeta=8, field="real")

Sparse random matrix generator based on the Sparse dimension reduction structure. Creates a sparse matrix with approximately zeta non-zero entries per column, where each entry is randomly ±1 (real) or a complex sign.

This is more efficient than dense Gaussian matrices and is particularly useful for large-scale randomized SVD computations.

Arguments

• m::Int: Number of rows (output dimension)
• n::Int: Number of columns (input dimension)

Keyword Arguments

• zeta::Int=8: Number of non-zero entries per column (default: 8, clamped to min(m,8))
• field::String="real": "real" for ±1 entries, "complex" for complex unit entries

Returns

• Sparse: sparse dimension reduction object

Notes

• Returns a dense matrix for compatibility with existing rsvd code
• For very large problems, consider using the Sparse object directly with LeftApply or RightApply for memory efficiency
• The sparsity pattern is random with zeta non-zeros per column

srft_rng(m, n)

Subsampled Randomized Fourier Transform (SRFT) matrix generator. More efficient than Gaussian random matrices, especially for large problems.

The SRFT is an implicit structured random matrix of the form: SRFT = √(m/k) · R · F · D

where:

• D is a diagonal matrix with random ±1 entries (size m × m)
• F is the DFT matrix (applied via FFT)
• R is a random row sampling matrix (selects n rows from m)

The resulting matrix has size (n, m).

This implementation doesn't form the matrix explicitly but returns a lazy operator that applies the SRFT efficiently.

uniform_rng(m, n)

Uniform random matrix generator on [-1, 1].

SRFTMatrix

Lazy representation of a Subsampled Randomized Fourier Transform matrix. The matrix has size (mout, nin): takes nin-dimensional vectors and produces mout-dimensional outputs.

rsvd_standard(A, k, p, q, rng)

Standard randomized SVD implementation (for m ≤ n or when transpose trick is disabled).

rsvd_transpose(A, k, p, q, rng)

Transpose trick for tall-thin matrices (m >> n). More efficient when the matrix has many more rows than columns.