rSVD for faer matrices

rsvd-faer is a Rust crate for randomized singular value decomposition, rewritten from the original ekg/rsvd implementation to work directly with faer matrices.

Overview

This crate computes an approximate rank-k SVD of a matrix A using randomized range finding and projection:

Draw a Gaussian test matrix Ω
Compute the sample matrix Y = A Ω
Optionally apply q power iterations to improve spectral approximation
Compute a thin QR factorization of Y
Project A into the smaller subspace and compute a thin SVD
Recover approximate factors U, S, and Vᵀ

The implementation uses faer for matrix storage, BLAS-style multiplication, QR decomposition, and SVD on the smaller projected matrix.

Features

Approximate truncated SVD for faer::Mat<f64> matrices with a target rank k which runs faster than full svd.
Supports RNG seed and faer::Parallelism.
Returns U, S, and Vᵀ directly as faer::Mat<f64>
Inspired by the original ekg/rsvd crate and adapted for the faer matrix ecosystem

Example

use faer::{Mat, Parallelism};
use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;
use rsvd_faer::rsvd;

let mut rng = ChaCha8Rng::seed_from_u64(42);
let a = Mat::<f64>::from_fn(3, 3, |i, j| {
    let data = [1.0, 2.0, 3.0, 8.0, 9.0, 4.0, 7.0, 6.0, 5.0];
    data[i * 3 + j]
});

let (u, s, vt) = rsvd(a.as_ref(), 2, 5, 1, &mut rng, Parallelism::Rayon(0));

println!("U shape = {} x {}", u.nrows(), u.ncols());
println!("S shape = {} x {}", s.nrows(), s.ncols());
println!("Vt shape = {} x {}", vt.nrows(), vt.ncols());

API

pub fn rsvd(
    a: MatRef<'_, f64>,
    k: usize,
    p: usize,
    q: usize,
    rng: &mut impl rand::Rng,
    par: faer::Parallelism,
) -> (Mat<f64>, Mat<f64>, Mat<f64>)

a: input matrix with shape (m, n)
k: target rank of the approximation
p: oversampling parameter, typically 5..10
q: number of power iterations; use 0 for no iteration
rng: random number generator for Gaussian sampling
par: faer::Parallelism mode for matrix multiplication

Returns:

U: left singular vectors with shape (m, k)
S: singular values as a (k, 1) matrix
Vᵀ: right singular vectors transposed with shape (k, n)

Notes

The crate uses a Gaussian random matrix for range sampling.
The returned S matrix contains the top k singular values down the diagonal.
q > 0 improves accuracy for matrices with slowly decaying singular values, at the cost of extra matrix multiplications.

Acknowledgements

This crate is inspired by the original ekg/rsvd implementation. Thanks to the original author for the reference implementation and the randomized SVD design.

References

Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp, “Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions,” 2011. https://arxiv.org/abs/0909.4061

License

MIT

rsvd-faer 0.1.0