`skerch`

skerch: Sketched matrix decompositions for PyTorch.

Consider a matrix or linear operator \(A \in \mathbb{R}^{M \times N}\), typically of intractable size and/or very costly measurement \(w = Av\), but of low-rank structure. A typical example of this are kernel matrices for Gaussian Processes or the Hessian matrices for Deep Learning.

Furthermore, consider its Singular Value Decomposition:

\[A := U \Sigma V^T\]

If \(A\) has rank \(k\), sketched methods allow us to approximate it while requiring only in the order of:

\(\mathcal{O}(\text{max}(M, N) \cdot k)\) memory
\(\mathcal{O}(\text{max}(M, N) \cdot k^2)\) arithmetic
\(\mathcal{O}(k)\) parallelizable measurements

This is in stark contrast with traiditional methods (e.g. QR-based, orthogonal iterations, Arnoldi…), which entail more memory requirements, arithmetic overhead, sequential measurements and/or numerical instability (see [HMT2009] for extensive discussion). With the help of sketched methods, explicit representation and SVD of otherwise intractable operators becomes now practical at unprecedented scales.

This package implements functionality to perform such sketched decompositions for any arbitrary matrix or linear operator \(A\). This includes non-square, non-PSD, and matrix-free operators. Furthermore, operations are implemented using PyTorch, which means that CPU/CUDA can be used in a device-agnostic way and automatic differentiation is available.

It also implements:

Efficient a priori methods to choose meaningful hyperparameters for the sketched algorithms
Efficient a posteriori methods to estimate the quality and rank of the sketched approximations
Matrix-free estimation of (sub-)diagonals for square linear operators
Matrix-free estimation of matrix-vector products for upper- and lower-triangular portions of square linear operators.

skerch

`skerch`