Distributions

Distributions

Abstract Types

RandLinearAlgebra.Distribution — Type

Distribution

An abstract supertype for structures specifying distribution for indices in sampling methods.

source

RandLinearAlgebra.DistributionRecipe — Type

DistributionRecipe

An abstract supertype for structures with pre-allocated memory for distribution function sampling methods.

source

Distribution Structures

RandLinearAlgebra.Uniform — Type

Uniform <: Distribution

Uniform distribution over the row/column index set of a matrix.

Mathematical Description

During the sampling, the uniform distribution is defined on the domain of row/column indices. If it's compressing from the left, then it means every row index has the same probability weight. If it's compressing from the right, then it means every column index has the same probability weight.

Fields

cardinality::Cardinality, the direction the compression matrix is intended to be applied to a target matrix or operator. Values allowed are Left() or Right() or Undef().
replace::Bool, if true, then the sampling occurs with replacement; if false, then the sampling occurs without replacement.

Constructor

Uniform(;cardinality=Undef(), replace = false)

Returns

A Uniform object.

source

RandLinearAlgebra.UniformRecipe — Type

UniformRecipe <: DistributionRecipe

The recipe containing all allocations and information for the uniform distribution.

Fields

cardinality::C where C<:Cardinality, the cardinality of the compressor. The value is either Left() or Right() or Undef().
replace::Bool, an option to replace or not during the sampling process based on the given weights.
state_space::Vector{Int64}, the row/column index set.
weights::ProbabilityWeights, the weights of each element in the state space.

source

RandLinearAlgebra.L2Norm — Type

L2Norm <: Distribution

Distribution where the probability of selecting a row (or column) is proportional to its squared Euclidean norm, as proposed by Strohmer and Vershynin [10].

Mathematical Description

During the sampling, the distribution is defined on the domain of row/column indices based on their norms. If it's compressing from the left, the probability $p_i$ of selecting row $i$ is: $p_i = \frac{\|A_{i,:}\|_2^2}{\|A\|_F^2}$; If it's compressing from the right, the probability $p_j$ of selecting column $j$ is: $p_j = \frac{\|A_{:,j}\|_2^2}{\|A\|_F^2}$.

Fields

cardinality::Cardinality, the direction the compression matrix is intended to be applied to a target matrix or operator. Values allowed are Left() or Right() or Undef(). The default value is Undef().
replace::Bool, if true, then the sampling occurs with replacement; if false, then the sampling occurs without replacement. The default value is false.

Constructor

L2Norm(;cardinality=Undef(), replace = false)

Returns

A L2Norm object.

source

RandLinearAlgebra.L2NormRecipe — Type

L2NormRecipe <: DistributionRecipe

The recipe containing all allocations and information for the Strohmer-Vershynin distribution.

Fields

cardinality::C where C<:Cardinality, the cardinality of the compressor. The value is either Left() or Right() or Undef().
replace::Bool, an option to replace or not during the sampling process based on the given weights.
state_space::Vector{Int64}, the row/column index set.
weights::ProbabilityWeights, the probability of each element in the state space, calculated as the squared Euclidean norms.

source

RandLinearAlgebra.Agmon — Type

Agmon <: Distribution

Agmon sampling distribution, implementing Agmon's maximal residual selection method as proposed by Agmon [11]. See Patel et al. [6] (Supplement SM1.6) for a concise summary, and Haddock and Ma [12] for analysis in the context of Sampling Kaczmarz–Motzkin.

Mathematical Description

During sampling, the Agmon distribution scores indices of $Ax = b$ ($A \in \mathbb{R}^{m\times n}$, $x \in \mathbb{R}^{n}$, $b \in \mathbb{R}^{m}$) by residual magnitude and selects the highest-scoring one(s):

Left() cardinality: score row $i$ by $r_i = |A_{i,:}x - b_i|$.
Right() cardinality: score column $j$ by $c_j = |A_{:,j}^T(Ax - b)|$.

The candidate set depends on $β$ (subset size, $1 ≤ β ≤ d$, where $d$ is the active dimension: $d = m$ for Left(), $d = n$ for Right()):

$β = 1$: Select one index uniformly at random.
$β = d$: Select greedily over the full index set (pure Agmon).
$1 < β < d$: Sample $β$ indices at random, then select the index with the highest residual within the sampled subset.

Fields

cardinality::Cardinality: the direction the compression matrix is intended to be applied to a target matrix or operator. Values allowed are Left(), Right(), or Undef(). The default value is Undef().
replace::Bool: if true, then the sampling occurs with replacement; if false, then the sampling occurs without replacement. The default value is false.
beta::Int: the subset size for sampling ($1 ≤ β ≤ d$), where $d$ is the active sampling dimension ($m$ for Left(), $n$ for Right()). When $β = 1$, this reduces to uniform random selection. When $β = d$, this becomes pure greedy Agmon selection. The default value is 1.

Constructor

Agmon(; cardinality::Cardinality = Undef(), replace::Bool = false, beta::Int = 1)

Keywords

cardinality::Cardinality: the direction of index selection. Must be Left() or Right(). The default value is Undef().
replace::Bool: if true, sampling occurs with replacement. The default value is false.
beta::Int: subset size for sampling ($1 ≤ β ≤ d$). The default value is 1.

Returns

An Agmon object.

Throws

ArgumentError if beta < 1.

source

RandLinearAlgebra.AgmonRecipe — Type

AgmonRecipe <: DistributionRecipe

The recipe containing all allocations and information for the Agmon distribution.

Fields

cardinality::C where C<:Cardinality: the cardinality of the compressor. For Agmon, this should be Left() or Right().
replace::Bool: if true, then sampling is done with replacement; if false, then sampling is done without replacement.
beta::Int: the subset size for sampling ($1 ≤ β ≤ d$), where $d$ is the active sampling dimension ($m$ for Left(), $n$ for Right()).
state_space::Vector{Int64}: the active row/column index set.
sample_buffer::Vector{Int64}: workspace to store the randomly sampled subset of $β$ indices.
A::AbstractMatrix: reference to the coefficient matrix.
b::AbstractVector: reference to the constant vector.
x::AbstractVector: reference to the current solution iterate (updated each iteration).
r::Union{Nothing, AbstractVector}: the residual vector $Ax - b$. Starts as nothing; set by update_distribution!. If nothing when sample_distribution! is called, residuals are computed on-the-fly for the sampled candidates only.

Determining Compression Subset

In general, the $β$ candidates are selected uniformly with or without replacement depending on the value of replace.

For Left(), the compression subset (whose size is determined by the argument passed to sample_distribution!) is selected by taking the top absolute residuals, stored in r, from the candidates.

For Right(), the compression subset (whose size is determined by the argument passed to sample_distribution!) is selected by taking the top absolute residuals of the normal system. The residuals of the normal system are calculated by computing the coefficient matrix columns of the candidate subset and taking an inner product with the residuals, stored in r.

Developer note

We intentionally keep update_distribution! deterministic and perform all randomization in sample_distribution!. This keeps update semantics clean, and matches user expectations in iterative usage, where repeated sampling calls should produce fresh samples each time.

source

Exported Functions

RandLinearAlgebra.complete_distribution — Function

complete_distribution(distribution::Distribution, A::AbstractMatrix)

A function that generates a DistributionRecipe given the arguments.

Arguments

distribution::Distribution, a user-specified distribution function for sampling.
A::AbstractMatrix, a coefficient matrix.

Returns

A DistributionRecipe object.

Throws

ArgumentError if no method for completing the distribution exists for the given distribution type.

source

complete_distribution(distribution::Uniform, A::AbstractMatrix)

Creates a UniformRecipe for the given uniform distribution and matrix.

Arguments

distribution::Uniform: The uniform distribution specification.
A::AbstractMatrix: Coefficient matrix.

Returns

UniformRecipe: A recipe containing all necessary allocations.

Throws

ArgumentError if cardinality is Undef().

source

complete_distribution(distribution::L2Norm, A::AbstractMatrix)

Creates an L2NormRecipe for the given distribution and matrix.

Arguments

distribution::L2Norm: The L2Norm distribution specification.
A::AbstractMatrix: Coefficient matrix.

Returns

L2NormRecipe: A recipe containing all necessary allocations.

Throws

ArgumentError if cardinality is Undef().

source

complete_distribution(
    distribution::Agmon,
    x::AbstractVector,
    A::AbstractMatrix,
    b::AbstractVector
)

Creates an AgmonRecipe for the given Agmon distribution and linear system $Ax = b$.

Arguments

distribution::Agmon: The Agmon distribution specification.
x::AbstractVector: Current solution iterate of length $n$ (columns of A).
A::AbstractMatrix: Coefficient matrix.
b::AbstractVector: Constant vector of length $m$ (rows of A).

Returns

AgmonRecipe: A recipe containing all necessary allocations and references to A, b, x.

Throws

ArgumentError if cardinality is Undef().
DimensionMismatch if vector dimensions don't match the active cardinality layout.
ArgumentError if $β$ > number of rows (Left()) or columns (Right()) in A.

source

RandLinearAlgebra.update_distribution! — Function

update_distribution!(distribution::DistributionRecipe, A::AbstractMatrix)

A function that updates the DistributionRecipe in place given arguments.

Arguments

distribution::DistributionRecipe, a fully initialized realization of distribution.
A::AbstractMatrix, a coefficient matrix.

Returns

Modifies the DistributionRecipe in place and returns nothing.

Throws

ArgumentError if no method for updating the distribution exists for the given distribution type.

source

update_distribution!(ingredients::UniformRecipe, A::AbstractMatrix)

Updates the uniform distribution recipe with the current matrix.

Arguments

ingredients::UniformRecipe: The recipe to update.
A::AbstractMatrix: Coefficient matrix.

Returns

Modifies ingredients in place and returns nothing.

Throws

ArgumentError if cardinality is Undef().

source

update_distribution!(ingredients::L2NormRecipe, A::AbstractMatrix)

Updates the L2Norm distribution recipe with the current matrix.

Arguments

ingredients::L2NormRecipe: The recipe to update.
A::AbstractMatrix: Coefficient matrix.

Returns

Modifies ingredients in place and returns nothing.

Throws

ArgumentError if cardinality is Undef().

source

update_distribution!(
    ingredients::AgmonRecipe,
    x::AbstractVector,
    A::AbstractMatrix,
    b::AbstractVector;
    r::Union{Nothing, AbstractVector} = nothing
)

Updates the Agmon distribution recipe with the current solution iterate x and optionally the residual vector.

Arguments

ingredients::AgmonRecipe: The recipe to update.
x::AbstractVector: Current solution iterate of length $n$ (columns of A).
A::AbstractMatrix: Coefficient matrix.
b::AbstractVector: Constant vector of length $m$ (rows of A).
r::Union{Nothing, AbstractVector}: Optional residual vector. If nothing (default), recomputes $Ax - b$ and stores it in the recipe. If provided, stores it as-is, allowing the caller to maintain r incrementally (e.g. $r \mathrel{{-}{=}} A S_k V_k$) to avoid a full recompute.

Returns

Modifies ingredients in place and returns nothing.

Throws

DimensionMismatch if vector dimensions don't match matrix dimensions.
ArgumentError if $β$ > number of rows (Left()) or columns (Right()) in A.

source

RandLinearAlgebra.sample_distribution! — Function

sample_distribution!(indices::AbstractVector, distribution::DistributionRecipe)

A function that in place updates indices by given DistributionRecipe info.

Arguments

indices::AbstractVector, an abstract vector to store the sampled indices.
distribution::DistributionRecipe, a fully initialized realization of distribution.

Returns

Modifies indices in place by sampling that follows the weights and replacement given by

DistributionRecipe.

Throws

ArgumentError if no method for sampling from the distribution exists for the given distribution type.

source

sample_distribution!(indices::AbstractVector, distribution::UniformRecipe)

Samples indices according to the uniform distribution.

Arguments

indices::AbstractVector: Output vector to store selected indices.
distribution::UniformRecipe: The recipe containing sampling parameters.

Returns

Modifies indices in place with the selected indices and returns nothing.

source

sample_distribution!(indices::AbstractVector, distribution::L2NormRecipe)

Samples indices according to the L2Norm distribution.

Arguments

indices::AbstractVector: Output vector to store selected indices.
distribution::L2NormRecipe: The recipe containing sampling parameters.

Returns

Modifies indices in place with the selected indices and returns nothing.

source

sample_distribution!(indices::AbstractVector, distribution::AgmonRecipe)

Samples indices according to the Agmon distribution.

Residual strategy is controlled via update_distribution! and the stored distribution.r field:

On-the-fly (distribution.r === nothing, default): computes residuals only for the $β$ sampled candidates — O($β$·n) for Left(). Best for small $β$.
Stored exact (call update_distribution! without r): residuals read from the stored $r = Ax - b$ updated each iteration. O($β$) per sample; O(mn) paid once in update_distribution!.
Stored incremental (call update_distribution! with r): residuals read from r maintained by the caller via $r \mathrel{{-}{=}} A S_k V_k$. Cheaper update cost; may accumulate drift over iterations.

Design note

The optional r argument lives in update_distribution! to keep this function's contract simple: use distribution.r if available, fall back to on-the-fly if nothing. Discuss with advisor which strategy should be the default.

Arguments

indices::AbstractVector: Output vector to store selected index/indices.
distribution::AgmonRecipe: The recipe containing sampling parameters.

Returns

Modifies indices in place with the selected index/indices and returns nothing.

Implementation note

This function returns the top-k selected indices where k = length(indices). Ties are broken deterministically by selecting smaller indices first. The selection within the sampled subset is deterministic.

Throws

ArgumentError if length(indices) >β``.
ArgumentError if cardinality is not Left() or Right().

source

Distributions

Abstract Types

Distribution Structures

Exported Functions

Internal Functions