low_rank_toolbox.randomized.rangefinder

low_rank_toolbox.randomized.rangefinder(A, r, p=5, q=0, seed=1234, **extra_args)[source]

The (randomized) rangefinder method, also called HMT method.

Reference:

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

The mathematical formulation is:

Q, _ = qr((A A^H)^q A Omega, mode=’economic’)

where Omega is a Gaussian random matrix of shape (n, r + p).

When A is a low-rank matrix, the rangefinder provides a good approximation of the range of A with high probability.

Parameters:

  • A (LinearOperator) – The matrix to sketch.

  • r (int) – The target rank.

  • p (int, optional) – The number of over-sampling (default: 5).

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

  • seed (int, optional) – The seed for the random number generator (default: 1234).

  • **extra_args (dict) – Additional arguments. If ‘Omega’ is provided, use it as the sketching matrix.

Returns:

Q – Estimation of the range of A.

Return type:

ndarray