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:
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.
See also
The contents of this repository are based on the following publications:
[HMT2009]: Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp. 2011. “Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions”. SIAM Review, 53 (2): 217-288.
[TYUC2019]: Joel A. Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. 2019. “Streaming Low-rank Matrix Approximation with an Application to Scientific Simulation”. SIAM Journal on Scientific Computing 41 (4): A2430–63.
[BN2022]: Robert A. Baston and Yuji Nakatsukasa. 2022. “Stochastic diagonal estimation: probabilistic bounds and an improved algorithm”. CoRR abs/2201.10684.
- skerch package
- skerch Subpackages
- skerch Submodules
- skerch.a_posteriori module
- skerch.a_priori module
- skerch.decompositions module
- skerch.distributed_decompositions module
- skerch.distributed_measurements module
- skerch.linops module
- skerch.ssrft module
- skerch.subdiagonals module
- skerch.synthmat module
- skerch.triangles module
- skerch.utils module