rsvd-faer 0.1.0

# rSVD for faer matrices

`rsvd-faer` is a Rust crate for randomized singular value decomposition, rewritten from the original [ekg/rsvd](https://github.com/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:

1. Draw a Gaussian test matrix `Ω`
2. Compute the sample matrix `Y = A Ω`
3. Optionally apply `q` power iterations to improve spectral approximation
4. Compute a thin QR factorization of `Y`
5. Project `A` into the smaller subspace and compute a thin SVD
6. 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

```rust
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

```rust
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`](https://github.com/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