Solvers

Solver

An abstract supertype for structures that contain the user-controlled parameters for methods that solve linear systems and least squares problems.

SolverRecipe

An abstract supertype specifying a solver method with pre-allocated data structures given a coefficient matrix and constant vector.

ColumnProjection <: Solver

A specification of a column projection solver, which is a generalization of (block) coordinate descent for least squares problems. These solvers iteratively update a solution by projecting the solution onto a compressed column space of the coefficient matrix.

Mathematical Description

Let $A$ be an $m \times n$ matrix and consider solving the linear least squares problem $\min_{x} \Vert b - Ax \Vert_2.$ Column projection methods refine a current iterate x by the update $x_{+} = x + Sv,$ where $S$ is a compression and $v$ is the minimum two-norm solution to $\min_{w} \Vert b - A(x + Sw) \Vert_2.$

Explicitly, the solution is $v = (S^\top A^\top A S)^\dagger (AS)^\top (b - Ax) = (S^\top A^\top)^\dagger (b - A x),$ which yields $x_{+} = x + S (S^\top A^\top)^\dagger (b - Ax).$

Here, we allow for an additional relaxation parameter, $\alpha$, which results in the update $x_{+} = x + \alpha S (S^\top A^\top)^\dagger (b - Ax).$

When the compression $S$ is a vector, the update simplifies to $x_{+} = x + \alpha S \frac{ (AS)^\top (b - Ax) }{\Vert AS \Vert^2}.$ Letting $r = b - Ax$, the residual $r_{+} = b - Ax_{+}$ can be computed by $r_{+} = r - \alpha (AS) v.$

Fields

• alpha::Float64, the over-relaxation parameter.
• compressor::Compressor, a technique for forming the compressed column space of the linear system.
• log::Logger, a technique for logging the progress of the solver.
• error::SolverError, a method for estimating the progress of the solver.
• sub_solver::SubSolver, a technique to perform the projection of the solution onto the compressed column space.

Constructor

ColumnProjection(;
    alpha::Float64 = 1.0,
    compressor::Compressor = SparseSign(cardinality=Right()), 
    error::SolverError = LSGradient(),
    log::Logger = BasicLogger(),
    sub_solver::SubSolver = QRSolver(), 
)

Keywords

• alpha::Float64, the over-relaxation parameter. By default this value is 1.
• compressor::Compressor, a technique for forming the compressed column space of the linear system. By default it is a SparseSign compressor.
• error::SolverError, a method for estimating the progress of the solver. By default it is the LSGradient error method.
• log::Logger, a technique for logging the progress of the solver. By default it is BasicLogger.
• sub_solver::SubSolver, a technique to perform the projection of the solution onto the compressed rowspace. When the compression_dim = 1 this is not used. For all other cases, the default is QRSolver.

Returns

• A ColumnProjection object.

ColumnProjectionRecipe{
    T<:Number, 
    V<:AbstractVector,
    M<:AbstractArray, 
    MV<:SubArray,
    C<:CompressorRecipe, 
    L<:LoggerRecipe,
    E<:SolverErrorRecipe, 
    B<:SubSolverRecipe
} <: SolverRecipe

A mutable structure containing all information relevant to the ColumnProjection solver. It is formed by calling the function complete_solver on a ColumnProjection object.

Fields

• compressor::CompressorRecipe, a technique for forming the compressed column space of the linear system.
• log::LoggerRecipe, a technique for logging the progress of the solver.
• error::SolverErrorRecipe, a method for estimating the progress of the solver.
• sub_solver::SubSolverRecipe, a technique to perform the projection of the solution onto the compressed column space.
• alpha::Float64, the over-relaxation parameter. It is multiplied by the update and can affect convergence.
• compressed_mat::AbstractMatrix, a matrix container for storing the compressed matrix. Will be set to be the largest possible block size.
• solution_vec::AbstractVector, a vector container for storing the current solution to the linear system.
• update_vec::AbstractVector, a vector container for storing the update to the solution.
• mat_view::SubArray, a container for storing a view of the compressed matrix container. Using views here allows for variable block sizes.
• residual_vec::AbstractVector, a vector container for storing the residual at each iteration.

IHS <: Solver

An implementation of the Iterative Hessian Sketch solver for solving over determined least squares problems [8].

Mathematical Description

Let $A \in \mathbb{R}^{m \times n}, m \gg n,$ and consider the least square problem $\min_x \|Ax - b \|_2^2$. If we let $S \in \mathbb{R}^{s \times m}$ be a compression matrix, then Iterative Hessian Sketch iteratively finds a solution to this problem by repeatedly updating $x_{k+1} = x_k + \alpha u_k$where $u_k$ is the solution to the convex optimization problem, $u_k \in \argmin_u \{\|S_k Au\|_2^2 - \langle A, b - Ax_k \rangle \}.$ This method has been to shown to converge geometrically at a rate $\rho \in (0, 1/2]$. Typically the required compression dimension needs to be 4-8 times the size of n for the algorithm to perform successfully.

Fields

• alpha::Float64, a step size parameter.
• compressor::Compressor, a technique for forming the compressed linear system.
• log::Logger, a technique for logging the progress of the solver.
• error::SolverError, a method for estimating the progress of the solver.

Constructor

function IHS(;
    compressor::Compressor = SparseSign(cardinality = Left()),
    log::Logger = BasicLogger(),
    error::SolverError = FullResidual(),
    alpha::Float64 = 1.0
)

Keywords

• compressor::Compressor, a technique for forming the compressed linear system.
• log::Logger, a technique for logging the progress of the solver.
• error::SolverError, a method for estimating the progress of the solver.
• alpha::Float64, a step size parameter.

Returns

• A IHS object.

IHSRecipe{
    Type<:Number, 
    LR<:LoggerRecipe,
    CR<:CompressorRecipe,
    ER<:ErrorRecipe,
    M<:AbstractArray, 
    MV<:SubArray, 
    V<:AbstractVector
} <: SolverRecipe

A mutable structure containing all information relevant to the Iterative Hessian Sketch solver. It is formed by calling the function complete_solver on a IHS solver, which includes all the user controlled parameters, the linear system A, and the constant vector b.

Fields

• log::LoggerRecipe, a technique for logging the progress of the solver.
• compressor::CompressorRecipe, a technique for compressing the matrix $A$.
• error::SolverErrorRecipe, a technique for estimating the progress of the solver.
• alpha::Float64, a step size parameter, by default is set to 1.
• compressed_mat::AbstractMatrix, a buffer for storing the compressed matrix.
• mat_view::SubArray, a container for storing a view of the compressed matrix buffer.
• residual_vec::AbstractVector, a vector that contains the residual of the linear system $Ax-b$.
• gradient_vec::AbstractVector, a vector that contains the gradient of the least squares problem, $A^\top(b-Ax)$.
• buffer_vec::AbstractVector, a buffer vector for storing intermediate linear system solves.
• solution_vec::AbstractVector, a vector storing the current IHS solution.
• R::UpperTriangular, a container for storing the upper triangular portion of the R factor from a QR factorization of mat_view. This is used to solve the IHS sub-problem.

Kaczmarz <: Solver

An implementation of a Kaczmarz solver. Specifically, it is a solver that iteratively updates an iterate by projecting the iterate onto (a subspace of) the row space of a consistent linear system.

Mathematical Description

Let $A$ be an $m \times n$ matrix and consider the consistent linear system $Ax=b$. We can view the solution to this linear system as lying at the intersection of the row hyperplanes, $\cap_{i \in \{1, \ldots, m\}}\{u \in \mathbb{R}^{n} : A_{i \cdot} u = b_i \}$, where $A_{i \cdot}$ represents the $i^\text{th}$ row of $A$. One way to find this interesection is to iteratively project some abritrary point, $x$ from one hyperplane to the next, through $x_{+} = x + \alpha \frac{b_i - A_{i\cdot}^\top x}{\| A_{i\cdot} \|_2^2}$ Doing this with random permutation of $i$ can lead to a geometric convergence [9]. Here $\alpha$ is viewed as an over-relaxation parameter and can improve convergence. One can also generalize this procedure to blocks by considering the $S$ being a $s \times n$ random matrix. If we let $\tilde A = S A$ and $\tilde b = Sb$ then we can perform block kaczmarz as described by [10] with $x_{+} = x + \alpha \tilde A^\top (\tilde A \tilde A^\top)^\dagger (\tilde b - \tilde A x).$ While, S is often random, in reality, whether S is deterministic or random is quite flexible see [3] for more details.

Fields

• alpha::Float64, the over-relaxation parameter. It is multiplied by the update and can affect convergence.
• compressor::Compressor, a technique for forming the compressed rowspace of the linear system.
• log::Logger, a technique for logging the progress of the solver.
• error::SolverError, a method for estimating the progress of the solver.
• sub_solver::SubSolver, a technique to perform the projection of the solution onto the compressed rowspace.

Constructor

Kaczmarz(;
    compressor::Compressor = SparseSign(), 
    log::Logger = BasicLogger(),
    error::SolverError = FullResidual(),
    sub_solver::SubSolver = LQSolver(),
    alpha::Float64 = 1.0
)

Keywords

• compressor::Compressor, a technique for forming the compressed rowspace of the linear system.
• log::Logger, a technique for logging the progress of the solver.
• error::SolverError, a method for estimating the progress of the solver.
• sub_solver::SubSolver, a technique to perform the projection of the solution onto the compressed rowspace. When the compression_dim = 1 this is not used.
• alpha::Float64, the over-relaxation parameter. It is multiplied by the update and can affect convergence. By default this value is 1.

Returns

• A Kaczmarz object.

KaczmarzRecipe{
    T<:Number, 
    V<:AbstractVector,
    M<:AbstractMatrix, 
    VV<:SubArray,
    MV<:SubArray,
    C<:CompressorRecipe, 
    L<:LoggerRecipe,
    E<:SolverErrorRecipe, 
    B<:SubSolverRecipe
} <: SolverRecipe

A mutable structure containing all information relevant to the Kaczmarz solver. It is formed by calling the function complete_solver on Kaczmarz solver, which includes all the user controlled parameters, and the linear system matrix A and constant vector b.

Fields

• compressor::CompressorRecipe, a technique for forming the compressed rowspace of the linear system.
• log::LoggerRecipe, a technique for logging the progress of the solver.
• error::SolverErrorRecipe, a method for estimating the progress of the solver.
• sub_solver::SubSolverRecipe, a technique to perform the projection of the solution onto the compressed rowspace.
• alpha::Float64, the over-relaxation parameter. It is multiplied by the update and can affect convergence.
• compressed_mat::AbstractMatrix, a matrix container for storing the compressed matrix. Will be set to be the largest possible block size.
• compressed_vec::AbstractVector, a vector container for storing the compressed constant vector. Will be set to be the largest possible block size.
• solution_vec::AbstractVector, a vector container for storing the solution to the linear system.
• update_vec::AbstractVector, a vector container for storing the update to the linear system.
• mat_view::SubArray, a container for storing a view of compressed matrix container. Using views here allows for variable block sizes.
• vec_view::SubArray, a container for storing a view of the compressed vector container. Using views here allows for variable block sizes.

complete_solver(solver::Solver, x::AbstractVector, A::AbstractMatrix, b::AbstractVector)

A function that generates a SolverRecipe given the arguments.

Arguments

• solver::Solver, a user-specified solver method.
• x::AbstractVector, a vector for the proposed solution.
• A::AbstractMatrix, a coefficient matrix.
• b::AbstractVector, a constant vector.

Outputs

• A SolverRecipe object.

rsolve!(
    solver::SolverRecipe, 
    x::AbstractVector, 
    A::AbstractMatrix, 
    b::AbstractVector
)

A function that solves a linear system given the arguments.

Arguments

• solver::SolverRecipe, a fully initialized realization for a solver method for a specific linear system.
• x::AbstractVector, a vector for the proposed solution.
• A::AbstractMatrix, a coefficient matrix.
• b::AbstractVector, a constant vector.

Outputs

• Returns nothing. Updates the SolverRecipe and x in place.

rsolve!(
    solver::Solver, 
    x::AbstractVector, 
    A::AbstractMatrix, 
    b::AbstractVector
)

A function that solves a linear system given the arguments.

Arguments

• solver::Solver, a user-specified solver method.
• x::AbstractVector, a vector for the proposed solution.
• A::AbstractMatrix, a coefficient matrix.
• b::AbstractVector, a constant vector.

Outputs

• x::AbstractVector, a proposed solution to a linear system or least squares problem.
• A SolverRecipe object.

colproj_update!(solver::ColumnProjectionRecipe)

A function that performs the column projection update when the compression dimension is one. If $a = AS$ is the resulting compression of the transpose of the coefficient matrix, and $r = b - Ax$ is the current residual, this function computes $x_{+} = x + \alpha S \frac{ a^\top (b-Ax) }{\Vert a \Vert_2^2},$ and $r_{+} = r_{-} - \alpha a \frac{ a^\top r}{\Vert a \Vert_2^2}.$

Arguments

• solver::ColumnProjectionRecipe, the solver information required for performing the update.

Outputs

• returns nothing

colproj_update_block!(solver::ColumnProjectionRecipe)

A function that performs the column projection update when the compression dimension is greater than 1. If $S$ is the compression matrix, the compressed matrix is $\tilde A = A S$, and the residual is $r = b - A x$, this function computes $v = (\tilde A^\top \tilde A)^\dagger \tilde A^\top r$ and stores it in solver.update_vec; $x_+ = x + \alpha S v;$ and stores it in solver.solution_vec; and $r_+ = r - \alpha \tilde A v$ and stores it in solver.residual_vec.

Arguments

• solver::ColumnProjectionRecipe, the solver information required for performing the update.

Outputs

• returns nothing

kaczmarz_update!(solver::KaczmarzRecipe)

A function that performs the Kaczmarz update when the compression dimension is one. If $a$ is the resulting compression of the coefficient matrix, and $c$ is the resulting compression of the constant vector, then we perform the update: $x = x - \alpha (a^\top x -c) / \|a\|_2^2$.

Arguments

• solver::KaczmarzRecipe, the solver information required for performing the update.

Outputs

• returns nothing

kaczmarz_update_block!(solver::KaczmarzRecipe)

A function that performs the kaczmarz update when the compression dim is greater than 1. In the block case where the compressed matrix $\tilde A$, and the compressed contant vector $\tilde b$, we perform the updated: $x = x - \alpha \tilde A^\top (\tilde A \tilde A^\top)^\dagger (\tilde Ax-\tilde b)$.

Arguments

• solver::KaczmarzRecipe, the solver information required for performing the update.

Outputs

• returns nothing

dotu(a::AbstractArray, b::AbstractArray)

A function that computes the non conjugate dot product between two vectors. It is equivalent to calling dot(conj(a), b).

Arguments

• a::AbstractArray, a vector being dot producted (is labeled as a array to allow for views).
• b::AbstractArray, a vector being dot producted (is labeled as a array to allow for views).

Returns

• A scalar that is the non-conjugated dot product between two vectors.