low_rank_toolbox.cssp.arp

Adaptive Randomized Pivoting (ARP) algorithm.

Author: Benjamin Carrel, University of Geneva, 2024

Functions

ARP(U[, seed, return_projector, return_inverse])

Implements the Adaptive Randomized Pivoting (ARP) algorithm for Column Subset Selection Problem (CSSP).
low_rank_toolbox.cssp.arp.ARP(U, seed=None, return_projector=False, return_inverse=False, **extra_args)[source]

Implements the Adaptive Randomized Pivoting (ARP) algorithm for Column Subset Selection Problem (CSSP).

Reference: ADAPTIVE RANDOMIZED PIVOTING FOR COLUMN SUBSET SELECTION, DEIM, AND LOW-RANK APPROXIMATION by Cortinovis and Kressner.

Note: The algorithm is similar to Osinsky’s algorithm for the CSSP. The randomization step allows for better error bounds (in expectation). (See Algorithm 2.1)

Parameters:

  • U (ndarray) – An (n x r) matrix with orthonormal columns.

  • seed (int, optional) – Random seed for reproducibility.

  • return_projector (bool, optional) – If True, return also the matrix U @ inv(U[S, :])

  • return_inverse (bool, optional) – If True, return also the inverse matrix inv(U[S, :])

Return type:

ndarray | tuple

Returns:

  • J (ndarray) – Selection of r row indices.

  • P_U (ndarray (n x r) (optional)) – Matrix U @ inv(U[J, :]) where U[J, :] is the (r x r) submatrix. Only returned if return_projector=True.

  • inv_U (ndarray (r x r) (optional)) – Matrix inv(U[J, :]). Only returned if return_inverse=True (requires return_projector=True).