Inverses#

Classes and associated functionality to approximate regularised inverses of matrices.

Given a matrix \(A\in\mathbb{R}^{n\times n}\) and some regularisation parameter \(\lambda\in\mathbb{R}_{\ge 0}\), the regularised inverse of \(A\) is \((A + \lambda I_n)^{-1}\) where \(I_n\) is the \(n\times n\) identity matrix.

Coreset algorithms which use the regularised inverse of large kernel matrices can become prohibitively expensive as the data size increases. To reduce this computational cost, this regularised inverse can be approximated by various methods, depending on the acceptable levels of error.

The RegularisedInverseApproximator in this module provides the functionality required to approximate the regularised inverse of matrices. Furthermore, this class allows for “block-inversion” where given an invertible matrix \(B\), the block array

\[\begin{split}A = \begin{bmatrix}B & 0 & \dots & 0 \\ 0 & 0 & \dots & 0 \\ \vdots & \ddots & \dots & \vdots \\ 0 & 0 & \dots & 0\end{bmatrix},\end{split}\]

where only the top-left block contains non-zero elements can be “inverted” to give

\[\begin{split}A^{-1} := \begin{bmatrix}B^{-1} & 0 & \dots & 0 \\ 0 & 0 & \dots & 0 \\ \vdots & \ddots & \dots & \vdots \\ 0 & 0 & \dots & 0\end{bmatrix}.\end{split}\]

This functionality allows iterative coreset algorithms which require inverting growing arrays to have fully static array shapes and thus be JIT-compatible.

To compute these “inverses” in JAX, we require the identity array passed in approximate() to be a matrix of zeros except for ones on the diagonal up to the dimension of the non-zero block.

class coreax.inverses.RegularisedInverseApproximator(random_key)[source]#

Base class for methods which approximate the regularised inverse of an array.

Computing the regularised inverse of large arrays can become prohibitively expensive as size increases. To reduce this computational cost, this quantity can be approximated, depending on the acceptable levels of error.

Parameters:: random_key (ArrayLike) – Key for random number generation

abstract approximate(array, regularisation_parameter, identity)[source]#

Approximate the regularised inverse of an array.

Note

The function is designed to invert blocked arrays where only the top-left block contains non-zero elements. We return a block array, the same size as the input array, where each block has only zero elements except for the top-left block, which is the inverse of the non-zero input block. To compute these “inverses” in JAX, we require the identity array to be a matrix of zeros except for ones on the diagonal up to the dimension of the non-zero block.

Parameters:

array (Array) – \(n \times n\) array
regularisation_parameter (float) – Regularisation parameter for stable inversion of array, negative values will be converted to positive
identity (Array) – Block identity matrix

Return type:

Array

Returns:

Approximation of the kernel matrix inverse

approximate_stack(arrays, regularisation_parameter, identity)[source]#

Approximate the regularised inverses of a horizontal stack of kernel matrices.

Parameters:

array – Horizontal stack of \(n \times n\) arrays
regularisation_parameter (float) – Regularisation parameter for stable inversion of array, negative values will be converted to positive
identity (Array) – Block identity matrix
arrays (Array) –

Return type:

Array

Returns:

Approximation of the kernel matrix inverses

class coreax.inverses.LeastSquareApproximator(random_key, rcond=None)[source]#

Approximate the regularised inverse of an array by solving a least-squares problem.

Note that this approximator does not give time savings and instead acts as a default option useful for comparing other approximators to.

Parameters:

random_key (ArrayLike) – Key for random number generation
rcond (Optional[float]) – Cut-off ratio for small singular values of ‘array’. For the purposes of rank determination, singular values are treated as zero if they are smaller than rcond times the largest singular value of ‘array’. The default value of None will use the machine precision multiplied by the largest dimension of the array. An alternate value of -1 will use machine precision.

approximate(array, regularisation_parameter, identity)[source]#

Approximate the regularised inverse of an array.

Note

Parameters:

array (Array) – \(n \times n\) array
regularisation_parameter (float) – Regularisation parameter for stable inversion of array, negative values will be converted to positive
identity (Array) – Block identity matrix

Return type:

Array

Returns:

Approximation of the kernel matrix inverse

coreax.inverses.randomised_eigendecomposition(random_key, array, oversampling_parameter=25, power_iterations=1)[source]#

Approximate the eigendecomposition of Hermitian matrices.

Using Algorithm 4.4. and 5.3 from [halko2009randomness] we approximate the eigendecomposition of a matrix. The parameters oversampling_parameter and power_iterations present a trade-off between speed and approximation quality. See [halko2009randomness] for discussion on choosing sensible parameters, the defaults chosen here are cautious.

Given the matrix \(A \in \mathbb{R}^{n\times n}\) and \(r=``oversampling_parameter\) we return a diagonal array of eigenvalues \(\Lambda \in \mathbb{R}^{r \times r}\) and a rectangular array of eigenvectors \(U\in\mathbb{R}^{n\times r}\) such that we have \(A \approx U\Lambda U^T\).

Parameters:

random_key (ArrayLike) – Key for random number generation
array (Array) – Array to be decomposed
oversampling_parameter (int) – Number of random columns to sample; the larger the oversampling_parameter, the more accurate, but slower the method will be
power_iterations (int) – Number of power iterations to do; the larger the power_iterations, the more accurate, but slower the method will be

Return type:

tuple[Array, Array]

Returns:

Eigenvalues and eigenvectors that approximately decompose the target array

class coreax.inverses.RandomisedEigendecompositionApproximator(random_key, oversampling_parameter=25, power_iterations=1, rcond=None)[source]#

Approximate regularised inverse of a Hermitian array via random eigendecomposition.

Computing the regularised inverse of large arrays can become prohibitively expensive as size increases. To reduce this computational cost, this quantity can be approximated by various methods. RandomisedEigendecompositionApproximator is a class that does such an approximation using the randomised eigendecomposition of the input array.

Parameters:

random_key (ArrayLike) – Key for random number generation
oversampling_parameter (int) – Number of random columns to sample; the larger the oversampling_parameter, the more accurate, but slower the method will be
power_iterations (int) – Number of power iterations to do; the larger the power_iterations, the more accurate, but slower the method will be
rcond (Optional[float]) – Cut-off ratio for small singular values of the array. For the purposes of rank determination, singular values are treated as zero if they are smaller than rcond times the largest singular value of a. The default value of None will use the machine precision multiplied by the largest dimension of the array. An alternate value of -1 will use machine precision.

approximate(array, regularisation_parameter, identity)[source]#

Approximate the regularised inverse of an array.

Note

Parameters:

array (Array) – \(n \times n\) array
regularisation_parameter (float) – Regularisation parameter for stable inversion of array, negative values will be converted to positive
identity (Array) – Block identity matrix

Return type:

Array

Returns:

Approximation of the kernel matrix inverse