low_rank_toolbox.randomized.randomized_svd

low_rank_toolbox.randomized.randomized_svd(X, r, p=10, q=0, truncate=True, seed=1234, **extra_data)[source]

Randomized SVD algorithm.

Reference:

“Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions”, Halko, Martinsson and Tropp 2010.

The randomized SVD computes an approximate SVD of a matrix X with the following steps: 1. Estimate the range with Q = rangefinder(X, r, p, q, seed) 2. Form the smaller matrix C = Q^H X 3. Compute the SVD of C: C = U_C S V^H 4. Form the approximate SVD of X: X_approx = Q U_C S V^H

Parameters:

  • X (SVD | LowRankMatrix | ndarray | LinearOperator) – Matrix or operator to be decomposed

  • r (int) – Rank of the decomposition, must be positive

  • p (int, optional) – Oversampling parameter (default: 10)

  • q (int, optional) – Number of power iterations (default: 0)

  • truncate (bool, optional) – If True, truncate the SVD to rank r (default: True)

  • seed (int, optional) – Random seed for reproducibility (default: 1234)

  • **extra_data (dict) – Additional arguments passed to SVD constructor. If ‘Omega’ is provided, use it as the sketching matrix.

Returns:

Near-optimal best rank r approximation of X

Return type:

SVD