Module rusty_compression::random_sampling

source · [−]
Expand description

Random sampling of matrices

This module defines traits for the randomized sampling of the range of a linear operator and the associated computation of randomized QR and Singular Value Decompositions.

In many applications we want to complete an approximate low-rank approximation of a linear operator but do not have access to the whole matrix, or computing the full QR or SVD of a matrix is too expensive. In these cases techniques from randomized linear algebra can be used to compute approximate low-rank decompositions.

Assume we have an operator $A$. We have two conditions on $A$.

  1. We need to be able to compute $y=Ax$ for a given vector $x$.
  2. We need to be able to compute $y=A^Hx$ for a given vector $x$.

These abilities are implemented through the traits MatVec and ConjMatVec. Implementing these traits also automatically implements the corresponding traits MatMat and ConjMatMat, which are the corresponding versions for multiplications with a matrix $X$ instead of a vector $x$. The routines in this module use the latter traits. For performance reasons it may sometimes be preferable to directly implement MatMat and ConjMatMat instead of relying on the corresponding vector versions.

In the following we describe the traits in more detail.

  • SampleRange: This trait can be used to randomly sample the range of an operator by specifying a target rank. It only requires the MatMat trait.
  • SampleRangePowerIteration: This trait is an improved version of [`SampleRange’]. It uses a power iteration to give a more precise result but requires the ConjMatMat trait to be implemented.
  • AdaptiveSampling: This trait samples the range of an operator adaptively through specifying a target tolerance. The error tolerance is checked probabilistically.

Once we have sampled the range of an operator we can use the method compute_from_range_estimate of the QRTraits to obtain an approximate QR Decomposition of the operator, from which we can for example compute an interpolative decomposition. Alternatively, we can use the corresponding method to compute an approximate Singular Value Decomposition of the operator.

Traits

AdaptiveSampling

This trait defines the adaptive sampling of the range of an operator.

MaxColNorm

Trait defining the maximum column norm of an operator

SampleRange

Randomly sample the range of an operator

SampleRangePowerIteration

Randomly sample the range of an operator through a power iteration