Approximators

Approximator

An abstract supertype for structures that store user-controlled parameters corresponding to techniques that form low-rank approximations of the matrix A.

ApproximatorRecipe

An abstract supertype for structures that store user-controlled parameters, linear system dependent parameters and preallocated memory corresponding to techniques that form low-rank approximations of the matrix A.

ApproximatorAdjoint{S<:ApproximatorRecipe} <: ApproximatorRecipe

A structure for the adjoint of an ApproximatorRecipe.

Fields

• Parent::ApproximatorRecipe, the approximator that we compute the adjoint of.

RangeApproximator

An abstract type for the structures that contain the user-controlled parameters corresponding to the Approximator methods that produce an orthogonal approximation to the range of a matrix A. This includes methods like the RandomizedSVD and randomized rangefinder.

RangeApproximatorRecipe

An abstract type for the structures that contain the user-controlled parameters, linear system information, and preallocated memory for methods corresponding to the Approximator methods that produce an orthogonal approximation to the range of a matrix A. This includes methods like the RandomizedSVD and randomized rangefinder.

RangeFinder

A struct that implements the Randomized Range Finder technique which uses compression from the right to form an low-dimensional orthogonal matrix $Q$ that approximates the range of $A$. See [9] for additional details.

Mathematical Description

Suppose we have a matrix $A \in \mathbb{R}^{m \times n}$ of which we wish to form a low rank approximation that approximately captures the range of $A$. Specifically, we wish to find an Orthogonal matrix $Q$ such that $QQ^\top A \approx A$.

A simple way to find such a matrix is to choose a ``k`` representing the number of 
vectors we wish to have in the subspace. Then we can generate a compression matrix 
``S\in\mathbb{R}^{n \times k}`` and compute ``Q = \text{qr}(AS)``. 
With high probability we will have ``\|A - QQ^\top A\|_2 \leq
(k+1) \sigma_{k+1}``, where ``\sigma_{k+1}`` is the ``k+1^\text{th}`` singular value 
of A. This bound is often conservative when the singular values of ``A`` decay quickly. 
In the case where the singular values decay slowly, by computing the qr factorization of
``(AA^\top)^q AS``, this is known as taking ``q`` power iterations. Power iterations 
drive the ``k+1`` constant in front of ``\sigma_{k+1}`` in the bound closer to 1, 
leading to more accurate approximations. One can also improve the stability of these 
power iterations be orthogonalizing each matrix in what is known as the random subspace 
iteration.

Fields

• compressor::Compressor, the technique that will compress the matrix from the right.
• power_its::Int64, the number of power iterations that should be performed.
• rand_subspace::Bool, a boolean indicating whether the power_its should be performed with orthogonalization.

RangeFinderRecipe

A struct that contains the preallocated memory and completed compressor to form a RangeFinder approximation to the matrix $A$.

Fields

• compressor::CompressorRecipe, the compressor to be applied from the right to $A$.
• power_its::Int64, the number of power iterations that should be performed.
• rand_subspace::Bool, a boolean indicating whether the power_its should be performed with orthogonalization.
• range::AbstractMatrix, the orthogonal matrix that approximates the range of $A$.

complete_approximator(approximator::Approximator, A::AbstractMatrix)

A function that generates an ApproximatorRecipe given arguments.

Arguments

• approximator::Approximator, a data structure containing the user-defined parameters associated with a particular low-rank approximation.
• A::AbstractMatrix, a target matrix for approximation.

Outputs

• An ApproximatorRecipe object.

rapproximate(approximator::Approximator, A::AbstractMatrix)

A function that computes a low-rank approximation of the matrix A using the information in the provided Approximator data structure.

Arguments

• approximator::Approximator, a data structure containing the user-defined parameters associated with a particular low-rank approximation.
• A::AbstractMatrix, a target matrix for approximation.

Outputs

• An ApproximatorRecipe object.

rapproximate!(approximator::ApproximatorRecipe, A::AbstractMatrix)

A function that computes a low-rank approximation of the matrix A using the information in the provided Approximator data structure.

Arguments

• approximator::ApproximatorRecipe, a fully initialized realization for a low rank approximation method for a particular matrix.
• A::AbstractMatrix, a target matrix for approximation.

Outputs

• An ApproximatorRecipe object.

rand_power_it(approx::RangeFinderRecipe, A::AbstractMatrix)

Function that performs the randomized rangefinder procedure presented in Algortihm 4.3 of [9].

Arguments

• approx::RangeFinderRecipe, a RangeFinderRecipe structure that contains the compressor

recipe.

• A::AbstractMatrix, the matrix being approximated.

Returns

• Q::AbstractMatrix, an economical Q approximating the range of A.

rand_subspace_it(approx::RangeFinderRecipe, A::AbstractMatrix)

Function that performs the randomized rangefinder procedure presented in Algortihm 4.4 of [9].

Arguments

• approx::RangeFinderRecipe, a RangeFinderRecipe structure that contains the compressor

recipe.

• A::AbstractMatrix, the matrix being approximated.

Returns

• Q::AbstractMatrix, an economical Q approximating the range of A.