`skerch`

Sketched linear operations for PyTorch.

Consider a matrix or linear operator \(A \in \mathbb{C}^{M \times N}\), typically of intractable size and/or very costly measurements \(v \to Av\).

In many cases, such large operators feature a much smaller but hidden sub-structure (such as low-rank or banded), which allows for an approximation \(\hat{A}\) of scalable size. Typical examples of this are kernel matrices for large datasets, Hessian matrices for deep learning, large-scale datasets and the throughput of high-resolution simulations.

But obtaining \(\hat{A}\) through traditional compression methods is not feasible, since we would need to fully store or scan \(\hat{A}\) first. Instead, we directly obtain \(\hat{A}\) from just a few random \(y_i = A v_i\) measurements, or sketches (i.e. \(v_i\) follows some random distribution). Luckily, this is possible for a variety of \(\hat{A}\) structures, and the \(A v_i\) measurements are typically parallelizable, allowing us to work at large scales.

From an operational point of view, sketched methods only require the ability to draw a few matrix-vector measurements in the form \(Av, vA\). In Python, and for finite dimensions, this means providing an A.shape attribute and implementing the matrix-multiplication @ operation.

One core advantage of skerch is that this is the only requirement that \(A\) needs to fulfill (unlike other libraries which require A to implement more attributes and/or operations). In code, we just need to ensure that A satisfies the following interface:

class MyLinOp:
 def __init__(self, shape):
     self.shape = shape

 def __matmul__(self, x):
     return "... implement A @ x ..."

 def __rmatmul__(self, x):
     return "... implement x @ A ..."

Any operator implementing this interface will run on skerch routines such as diagonalizations, operator norms and triangular approximations. Other advantages of skerch:

Built on top of PyTorch, naturally supports CPU and CUDA, as well as complex datatypes. Very few dependencies otherwise
Rich API for matrix-free linear operators, including matrix-free noise sources (Rademacher, Gaussian, SSRFT…)
Efficient parallelized and distributed computations
Support for out-of-core operations via HDF5
A-posteriori verification tools to test accuracy of sketched approximations modular and extendible design, for easy adaption to new settings and operations
Modular and extendible design

See the API docs and examples for illustrations of the above points.

skerch

`skerch`