low_rank_toolbox.cssp.utils

Utility Functions for Column Subset Selection.

This submodule provides supporting numerical routines for CSSP algorithms, including QR factorization variants and Givens rotations.

Functions

givens : Compute Givens rotation matrix sRRQR : Strong Rank-Revealing QR factorization sRRQR_rank : sRRQR with prescribed rank sRRQR_tol : sRRQR with tolerance-based rank selection

Author: Benjamin Carrel, University of Geneva

low_rank_toolbox.cssp.utils.givens(x, y)[source]

Computes the complex Givens rotation matrix for a 2-element complex vector [x, y].

This function generalizes the real Givens rotation to the complex plane. The rotation is a unitary matrix G such that for a vector v = [x, y].T, the product G @ v is equal to [r, 0].T, where r is the real, non-negative value sqrt(|x|^2 + |y|^2).

The resulting matrix G is an element of SU(2) and has the form: [[c, s],

[-conj(s), conj(c)]]

where c and s are complex numbers satisfying |c|^2 + |s|^2 = 1. Specifically, the parameters are calculated as c = conj(x)/r and s = conj(y)/r. This implementation is numerically stable, avoiding overflow for large inputs.

Parameters:
Return type:

ndarray

Returns:

np.ndarray: A 2x2 complex unitary Givens rotation matrix.

low_rank_toolbox.cssp.utils.sRRQR(A, eta, mode, param)[source]

Dispatcher for Strong Rank-Revealing QR factorization.

This function automatically detects if the input matrix A is real or complex and calls the appropriate implementation.

Parameters:

  • (np.ndarray) (A)

  • (float) (eta)

  • (str) (mode)

  • float) (param (int or) –

    • If mode is ‘rank’, param is the desired rank k.

    • If mode is ‘tol’, param is the error tolerance.

  • A (ndarray)

  • eta (float)

  • mode (str)

  • param (float)

Return type:

tuple[ndarray, ndarray, ndarray]

Returns:

tuple[np.ndarray, np.ndarray, np.ndarray]:

  • Q (np.ndarray): Truncated unitary/orthogonal matrix $Q_1$.

  • R (np.ndarray): Truncated upper triangular matrix $[R_{11}, R_{12}]$.

  • p (np.ndarray): The column permutation vector.

low_rank_toolbox.cssp.utils.sRRQR_rank(A, eta, k)[source]

Strong Rank-Revealing QR factorization for real or complex matrices with a fixed rank ‘k’.

This function implements Algorithm 4 from: Gu, M., & Eisenstat, S. C. (1996). Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM Journal on Scientific Computing, 17(4), 848-869.

It computes a factorization $A P = Q R$ where $P$ is a permutation matrix, $Q$ is orthogonal (or unitary for complex matrices), and $R$ is upper triangular. The factorization is partitioned as: $$ A P = [Q_1, Q_2] begin{pmatrix} R_{11} & R_{12} \ 0 & R_{22} end{pmatrix} $$ such that the entries of $R_{11}^{-1} R_{12}$ are bounded by a factor $eta$.

Parameters:
Return type:

tuple[ndarray, ndarray, ndarray]

Returns:

tuple[np.ndarray, np.ndarray, np.ndarray]:

  • Q (np.ndarray): Truncated orthogonal/unitary matrix $Q_1$ (m x k).

  • R (np.ndarray): Truncated upper triangular matrix $[R_{11}, R_{12}]$ (k x n).

  • p (np.ndarray): The column permutation vector.

low_rank_toolbox.cssp.utils.sRRQR_tol(A, eta, tol)[source]

Strong Rank-Revealing QR for real or complex matrices with a tolerance ‘tol’.

This function implements Algorithm 5 from the Gu and Eisenstat paper. It determines the rank k such that the spectral norms of the columns of the $R_{22}$ block are all less than tol.

Parameters:
Return type:

tuple[ndarray, ndarray, ndarray]

Returns:

tuple[np.ndarray, np.ndarray, np.ndarray]:

  • Q (np.ndarray): Truncated orthogonal/unitary matrix $Q_1$ (m x k).

  • R (np.ndarray): Truncated upper triangular matrix $[R_{11}, R_{12}]$ (k x n).

  • p (np.ndarray): The column permutation vector.

Modules

givens(x, y)

Computes the complex Givens rotation matrix for a 2-element complex vector [x, y].

sRRQR(A, eta, mode, param)

Dispatcher for Strong Rank-Revealing QR factorization.