Linear Samplers

LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting components of a linear system.

Aliases

• LinSysSketch
• LinSysSelect

LinSysVecRowSampler <: LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting a row space element from a linear system.

Aliases

• LinSysVecRowSketch
• LinSysVecRowSelect

LinSysVecColSampler <: LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting a column space element from a linear system.

Aliases

• LinSysVecColSketch
• LinSysVecColSelect

LinSysBlkRowSampler <: LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting a collection of row space elements from a linear system.

Aliases

• LinSysBlkRowSketch
• LinSysBlkRowSelect

LinSysBlkColSampler <: LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting a collection of column space elements from a linear system.

Aliases

• LinSysBlkColSketch
• LinSysBlkColSelect

LinSysVecRowDetermCyclic <: LinSysVecRowSelect

An immutable structure without any fields. Specifies deterministic cycling through the equations of a linear system.

LinSysVecRowHopRandCyclic <: LinSysVecRowSelect

A mutable structure that specifies a cycling through the rows of a linear system, where the cycling order is determined randomly once the current cycling order has been used hop number of times. The solver randomly chooses the cycling order whenever necessary.

Fields

• order::Union{Vector{Int64},Nothing}
• hop::Int64

Constructors

• LinSysVecRowHopRandCyclic() defaults to setting the order to nothing and the hop to 5 (i.e., each ordering is used five times before sampling a new ordering).
• LinSysVecRowHopRandCyclic(hop::Int64) defaults to setting the order to nothing and the hop to whatever is specified by the argument.

LinSysVecRowOneRandCyclic <: LinSysVecRowSelect

A mutable structure with a field to store a cycling order. Randomly specifies a cycling order over the equations of a linear system. Once this ordering is specified, the ordering is kept fixed.

Fields

• order::Union{Vector{Int64},Nothing}

Calling LinSysVecRowOneRandCyclic() defaults to setting order to nothing. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysVecRowPropToNormSampler{T} <: LinSysVecRowSampler where T <: Categorical

A parametric mutable structure that specifies sampling from the rows of the equation where the probability of selecting a given equation is proportional to the sum of squares of the coefficients of the given equation. The solver will appropriately initialize the distribution.

See Strohmer, T., Vershynin, R. A Randomized Kaczmarz Algorithm with Exponential Convergence. J Fourier Anal Appl 15, 262 (2009). https://doi.org/10.1007/s00041-008-9030-4

Aliases

• LinSysVecRowSVSampler

Fields

• dist::T, a categorical probability distribution.

Calling LinSysVecRowPropToNormSampler() or LinSysVecRowSVSampler() defaults dist to Categorical(1.0).

LinSysVecRowRandCyclic <: LinSysVecRowSelect

A mutable structure with a field to store a cycling order. Randomly specifies a cycling order the equations of a linear system. Once this ordering is exhausted by the solver, a new random ordering is specified. This process is repeated

Fields

• order::Union{Vector{Int64},Nothing}

Calling LinSysVecRowOneRandCyclic() defaults to setting order to nothing. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysVecRowUnidSampler <: LinSysVecRowSampler

An immutable structure without fields that specifies randomly cycling from the rows of a linear system with uniform probability and with replacement.

LinSysVecRowUnifSampler <: LinSysVecRowSampler

An immutable structure without fields that specifies taking a linear combination of all equations with the coefficients being independent uniform random variables.

LinSysVecRowSparseUnifSampler <: LinSysVecRowSelect

A mutable structure that specifies sampling a proporition of the rows of a linear system, scaling each using independent uniform random variables, and then taking their sum. The proportion of rows sampled without replacement is given by (at most) sparsity which must be between 0 and 1 (not inclusive).

Fields

• sparsity::Float64

Constructors

• LinSysVecRowSparseUnifSampler() defaults the sparsity level to 0.2.

LinSysVecRowGaussSampler <: LinSysVecRowSampler

An immutable structure without fields that specifies taking a linear combination of all equations with the coefficients being independent Gaussian random variables.

LinSysVecRowSparseGaussSampler <: LinSysVecRowSelect

A mutable structure that specifies sampling a proporition of the rows of a linear system, scaling each using independent Gaussian random variables, and then taking their sum. The proportion of rows sampled without replacement is given by (at most) sparsity which must be between 0 and 1 (not inclusive).

Fields

• sparsity::Float64

Constructors

• LinSysVecRowSparseUnifSampler() defaults the sparsity level to 0.2.

LinSysVecRowMaxResidual <: LinSysVecRowSelect

An immutable structure without fields that specifies choosing the linear equation in a system with the largest absolute residual at the current iterate.

LinSysVecRowResidCyclic <: LinSysVecRowSelect

A mutable structure with a field to store a cycling order. When the ordering is not specified, the ordering is filled by looking at the residuals at the current iterate and ordering by decreasing residual. Once the order is exhausted a new order is selected.

Fields

• order::Vector{Int64}

Calling LinSysVecRowResidCyclic() defaults to setting order to an empty array. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysVecRowMaxDistance <: LinSysVecRowSelect

An immutable structure without fields that specifies choosing the linear equation in a system with the largest distance between the current iterate and the hyperplane specified by the equation.

LinSysVecRowDistCyclic <: LinSysVecRowSelect

A mutable structure with a field to store a cycling order. When the ordering is not specified, the ordering is filled in two steps. First, the distances between the current iterate and all hyperplanes as specified by the equations of the system. Then, the ordering is the indices of these distances in decreasing order.

Fields

• order::Vector{Int64}

Calling LinSysVecRowDistCyclic() defaults to setting order to an empty array. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysVecColDetermCyclic <: LinSysVecColSelect

An immutable structure without any fields. Specifies deterministic cycling through the columns of a linear system.

LinSysVecColOneRandCyclic <: LinSysVecColSelect

A mutable structure with a field to store a cycling order. Randomly specifies a cycling order over the equations of a linear system. Once this ordering is specified, the ordering is kept fixed.

Fields

• order::Vector{Int64}

Calling LinSysVecColOneRandCyclic() defaults to setting order to nothing. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysBlkRowCountSketch <: LinSysVecRowSelect

A mutable structure that represents the CountSketch algorithm for rows. The assumption is that A is fully known (that is, the sampling procedure is not used in a streaming context).

See Kenneth L. Clarkson and David P. Woodruff. 2017. "Low-Rank Approximation and Regression in Input Sparsity Time." J. ACM 63, 6, Article 54 (February 2017), 45 pages. https://doi.org/10.1145/3019134

The explicit sketch matrix is mentioned in Section 1.2 - Techniques (row version) of the aforementioned paper. See this website for a visual explanation of the column version.

Fields

• block_size::Int64, is the number of rows in the sketched matrix S * A.
• S::Union{Matrix{Int64}, Nothing}, buffer matrix for storing the sampling matrix S.

Additional Constructors:

Calling LinSysBlkRowCountSketch(block_size) defaults to LinSysBlkRowCountSketch(block_size, nothing). Calling LinSysBlkRowCountSketch() defaults to LinSysBlkRowCountSketch(2, nothing).

!!! Remark "Implementation Note" Current implementation does not take advantage of sparse matrix data structures or operations.

LinSysBlkRowGaussSampler <: LinSysBlkRowSampler

A mutable structure with fields to handle Guassian row sketching where a Gaussian matrix is multiplied by the matrix A from the left.

Fields

• block_size::Int64, specifies the size of each block.
• sketch_matrix::Union{AbstractMatrix, Nothing}, the buffer for storing the Gaussian sketching matrix.
• scaling::Float64, the standard deviation of the sketch, is set to be sqrt(block_size/numberOfRows).

Constructors

Calling LinSysBlkRowGaussSampler() defaults to setting block_size to 2.

LinSysBlkRowReplace <: LinSysBlkRowSampler

A mutable structure with fields to store information for a sampling method that forms a new block by uniformly sampling rows of A without replacement, also known as vanilla block randomized Kaczmarz.

Necoara, Ion. “Faster Randomized Block Kaczmarz Algorithms.” SIAM J. Matrix Anal. Appl. 40 (2019): 1425-1452.

Fields

• block_size::Int64, specifies the size of each block.
• block::Vector{Int64}, the list of all the rows in each block.

Constructors

Calling LinSysBlkRowReplace() defaults to setting block_size to 2. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysBlkRowRandCyclic <: LinSysBlkRowSampler

A mutable structure with fields to handle randomly permuted block sampling. After all blocks are called, a new random ordering is created.

Fields

• n_blocks::Int64, Variable that contains the number of blocks overall.
• order::Union{Vector{Int64}, Nothing}, The order that the blocks will be used to generate updates.
• blocks::Union{Vector{Vector{Int64}}, Nothing}, The list of all the row in each block.

Constructors

Calling LinSysBlkColRandCyclic() defaults to setting n_blocks to 2 and blocks to be sequentially ordered. These values can be changed using the respective keyword arguments. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysBlkRowSelectWoReplacement <: LinSysVecRowSelect

A mutable struct that represents sampling rows from A without replacement using an arbitrary weight/probability vector.

Fields

• block_size::Int64, number of rows sampled (i.e., number of rows in S * A).
• probability::Union{Weights, Vector{Float64}, Nothing}, vector that represents a probability distribution over the rows of A. Requirements are that the probabilities sum to 1, are non-negative, probability has the same length as number of rows in A, and probability has at least as many positive entries as block_size. If probability is unspecified in the constructor, sample will default to a uniform distribution over rows of A.
• population::Union{Vector{Int64}, Nothing}, buffer array to hold collect(1:size(A)[1]) used in sample.
• rows_sampled::Union{Vector{Int64}, Nothing}, buffer array to hold index of rows sampled from A.
• S::Union{Matrix{Int64}, Nothing}, buffer array to hold sketched matrix S.

Calling LinSysBlkRowSelectWoReplacement() defaults to LinSysBlkRowSelectWoReplacement(2, nothing, nothing, nothing, nothing).

An additional constructor is provided with keyword arguments block_size and probability.

LinSysBlkRowFJLT <: LinSysBlkRowSampler

A mutable structure with fields to handle FJLT row sketching. At each iteration, this procedure generates a matrix of the form S = G H D where G is sparse matrix with the non-zero entries being drawn from a gaussian distribution, H is a Hadamard matrix, and D is a diagonal matrix with a rademacher vector on the diagonal.

Fields

• block_size::Int64, the size of the sketching dimension
• sparsity::Float64, the sparsity of the sampling matrix
• padded_size::Int64, the size of the matrix when padded
• sampling_matrix::Union{SparseMatrixCSC, Nothing}, storage for sparse sketching matrix
• hadamard::Union{AbstractMatrix, Nothing}, storage for the hadamard matrix.
• Ap::Union{AbstractMatrix, Nothing}, storage for padded matrix
• bp::Union{AbstractMatrix, Nothing}, storage for padded vector
• scaling::Float64, storage for the scaling of the sketches.

Calling LinSysBlkRowFJLT() defaults to setting sparsity to .3 and the blocksize to 2.

Ailon, Nir, and Bernard Chazelle. "The fast Johnson–Lindenstrauss transform and approximate nearest neighbors." SIAM Journal on computing 39.1 (2009): 302-322. https://doi.org/10.1137/060673096

LinSysBlkRowSRHT <: LinSysBlkRowSampler

A mutable structure with fields to handle SRHT row sketching. At each iteration, this procedure generates a matrix of the form S = R H D where R is a subset of the identity matrix, H is a Hadamard matrix, and D is a diagonal matrix with a rademacher vector on the diagonal.

Fields

• block_size::Int64, the size of blocks being chosen
• padded_size::Int64, the size of the matrix when padded
• block::Union{Vector{Int64}, Nothing}, storage for block indices
• hadamard::Union{AbstractMatrix, Nothing}, storage for the hadamard matrix.
• Ap::Union{AbstractMatrix, Nothing}, storage for padded matrix
• bp::Union{AbstractMatrix, Nothing}, storage for padded vector
• scaling::Float64, storage for the scaling of the sketches.

Calling LinSysBlkRowSRHT() defaults to setting block_size to 2.

Nguyen, Nam H., Thong T. Do, and Trac D. Tran. "A fast and efficient algorithm for low-rank approximation of a matrix." Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009. https://doi.org/10.1145/1536414.1536446

LinSysBlkColCountSketch <: LinSysVecColSelect

A mutable structure that represents the CountSketch algorithm for columns. The assumption is that A is fully known (that is, the sampling procedure is not used in a streaming context).

See Kenneth L. Clarkson and David P. Woodruff. 2017. "Low-Rank Approximation and Regression in Input Sparsity Time." J. ACM 63, 6, Article 54 (February 2017), 45 pages. https://doi.org/10.1145/3019134

The explicit sketch matrix is mentioned in Section 1.2 - Techniques (row version) of the aforementioned paper. See this website for a visual explanation of the column version.

Fields

• block_size::Int64, is the number of columns in the sketched matrix A * S
• S::Union{Matrix{Int64}, Nothing}, buffer matrix for storing the sampling matrix S.

Additional Constructors:

Calling LinSysBlkColCountSketch(block_size) defaults to LinSysBlkColCountSketch(block_size, nothing). Calling LinSysBlkColCountSketch() defaults to LinSysBlkColCountSketch(2, nothing).

!!! Remark "Implementation Note" Current implementation does not take advantage of sparse matrix data structures or operations.

LinSysBlkColGaussSampler <: LinSysBlkColSampler

A mutable structure with fields to handle Guassian column sketching where a Gaussian matrix is multiplied by the matrix A from the right.

Fields

• block_size::Int64, specifies the size of each block.
• sketch_matrix::Union{AbstractMatrix, Nothing}, the buffer for storing the Gaussian sketching matrix.
• scaling::Float64, the standard deviation of the sketch, is set to be sqrt(block_size/numberOfColumns).

Constructors

Calling LinSysBlkColGaussSampler() defaults to setting block_size to 2.

LinSysVecBlkColReplace <: LinSysBlkColSampler

A mutable structure with fields to store information for a sampling method that forms a new block by uniformly sampling columns of A without replacement.

Fields

• block_size::Int64, specifies the size of each block.
• block::Vector{Int64}, the list of all the rows in each block.

Constructors

Calling LinSysBlkColReplace() defaults to setting block_size to 2. The sample function will handle the initialization of the fields once the system is provided.

LinSysBlkColRandCyclic <: LinSysBlkColSampler

A mutable structure with fields to handle randomly permuted block sampling. After all blocks are called, a new random ordering is created.

Fields

• n_blocks::Int64, Variable that contains the number of blocks overall.
• order::Vector{Int64}, The order that the blocks will be used to generate updates.
• blocks::Vector{Vector{Int64}}, The vector containing all the groupings of column indices.

Constructors

Calling LinSysBlkColRandCyclic() defaults to setting n_blocks to 2 and blocks to be sequentially ordered. These values can be changed using the respective keyword arguments. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysBlkColSelectWoReplacement <: LinSysVecColSelect

A mutable struct that represents sampling columns from A without replacement using an arbitrary weight/probability vector.

Fields

• block_size::Int64, number of columns sampled (i.e., number of columns in A * S)
• probability::Union{Weights, Vector{Float64}, Nothing}, vector that represents a probability distribution over the columns of A. Requirements are that the probabilities sum to 1, are non-negative, probability has the same length as number of columns in A, and probability has at least as many positive entries as block_size. If probability is unspecified in the constructor, sample will default to a uniform distribution over columns of A.
• population::Union{Vector{Int64}, Nothing}, buffer array to hold the vector collect(1:size(A)[2]) in the sample function.
• col_sampled::Union{Vector{Int64}, Nothing}, buffer array to hold index of columns sampled from A.
• S::Union{Matrix{Int64}, Nothing}, buffer array to hold sketching matrix S.

Calling LinSysBlkColSelectWoReplacement() defaults to LinSysBlkColSelectWoReplacement(2, nothing, nothing, nothing, nothing).

An additional constructor is provided with the keyword arguments block_size and probability.

LinSysBlkColFJLT <: LinSysBlkColSampler

A mutable structure with fields to handle FJLT column sketching. At each iteration, this procedure generates a matrix of the form S = D H G where G is sparse matrix with the non-zero entries being drawn from a gaussian distribution, H is a Hadamard matrix, and D is a diagonal matrix with a rademacher vector on the diagonal.

Fields

• block_size::Int64, the size of the sketching dimension
• sparsity::Float64, the sparsity of the sampling matrix, should be between 0 and 1
• padded_size::Int64, the size of the matrix when padded
• sampling_matrix::Union{SparseMatrixCSC, Nothing}, storage for sparse sketching matrix
• hadamard::Union{AbstractMatrix, Nothing}, storage for the hadamard matrix.
• Ap::Union{AbstractMatrix, Nothing}, storage for padded matrix
• bp::Union{AbstractMatrix, Nothing}, storage for padded vector
• scaling::Float64, storage for the scaling of the sketches.

Calling LinSysBlkColFJLT() defaults to setting sparsity to .3 and the blocksize to 2.

Ailon, Nir, and Bernard Chazelle. "The fast Johnson–Lindenstrauss transform and approximate nearest neighbors." SIAM Journal on computing 39.1 (2009): 302-322. https://doi.org/10.1137/060673096

LinSysBlkColSRHT <: LinSysBlkColSampler

A mutable structure with fields to handle SRHT column sketching. At each iteration, this procedure generates a matrix of the form S = D H R where R is a subset of the identity matrix, H is a Hadamard matrix, and D is a diagonal matrix with a rademacher vector on the diagonal.

Fields

• block_size::Int64, the size of blocks being chosen
• padded_size::Int64, the size of the matrix when padded
• block::Union{Vector{Int64}, Nothing}, storage for block indices
• hadamard::Union{AbstractMatrix, Nothing}, storage for the hadamard matrix.
• Ap::Union{AbstractMatrix, Nothing}, storage for padded matrix
• signs::Union{Vector{Bool}, Nothing}, storage for random sign flips.
• scaling::Float64, storage for the scaling of the sketches.

Calling LinSysBlkColSRHT() defaults to setting block_size to 2.

Nguyen, Nam H., Thong T. Do, and Trac D. Tran. "A fast and efficient algorithm for low-rank approximation of a matrix." Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009. https://doi.org/10.1145/1536414.1536446

sample(type::T where T<:LinSysSampler,
    A::AbstractArray,
    b::AbstractVector,
    x::AbstractVector,
    iter::Int64)

A common interface for specifying different strategies for sampling, selecting or sketching a linear system specified by A and b. The type argument is used to select the an appropriately defined strategy. The argument x is the current iterate value for the solution. The arguent iter is the iteration counter.

The value(s) returned by sample depend on the subtype of LinSysSampler being used. Specifically,

• For T<:LinSysVecRowSampler, a vector in the row space of A and constant are returned
• For T<:LinSysVecColSampler, a vector of length(x), the matrix A, and a scalar-valued residual are returned.

init_blocks_cyclic!(type::Union{LinSysBlkColRandCyclic,LinSysBlkRowRandCyclic}, dim::Int64)

This function intializes the blockSize, n_blocks, and order values for the LinSysBlkColRandCyclic and LinSysBlkRowRandCyclic data structures. If a set of blocks is already defined by the user then it warns the user which block indices are unused. If the blocks are not premade, it simply allocates block indices sequentially with a size that is floor(n_blocks/dim).

fwht!(x::AbstractVector; signs=ones(Bool, size(x)), scaling = 1)

Performs a Fast Walsh Hadamard Transform (FWHT), modifying the vector x. This means that if you want an unmodified version of x you should copy it before calling this function. signs allows the user to input a boolean vector that flips the signs of the entries of the vector x before applying the transform. scaling allows the user to scale the result of the transform. Choosing a scaling of 1/sqrt{size(x)} will result in the FWHT being an orthogonal transform.

!!! Note: To avoid log computation at every call the function does not check that the dimension is a power of 2. This must be done by a separate function at an earlier point.