Linear Solver Logs

LinSysSolverLog

Abstract supertype for logging information about a randomized linear system solver.

Note, all descendants that are mutable structs must have fields

• iterations::Int64, which tracks the number of iterations of the solver
• converged::Bool, which tracks whether the solver has converged to the solution (by some notion of convergence that is specified by the user).

LSLogOracle <: LinSysSolverLog

A mutable structure that stores information about a randomized linear solver's behavior. The log assumes that the true solution of the system is known and will be supplied. The goal of this log is usually for research, development, or testing.

Fields

• solution::AbstractVector, a solution to the given linear system.
• collection_rate::Int64, the frequency with which to record information to append to the remaining fields, starting with the initialization (i.e., iteration 0).
• error_hist::Vector{Float64}, retains a vector of numbers corresponding to the error between the iterates of the solver and the solution
• error_norm::Function, a function that accepts a single vector argument and returns a scalar. Used to compute the error size.
• resid_hist::Vector{Float64}, retains a vector of numbers corresponding to the residual (uses the whole system to compute the residual)
• resid_norm::Function, a function that accepts a single vector argument and returns a scalar. Used to compute the residual size.
• iterations::Int64, the number of iterations of the solver.
• converged::Bool, a flag to indicate whether the system has converged by some measure

Constructors

• Calling LSLogOracle(x_star::Vector{Float64}) sets solution = x_star, collection_rate = 1, error_hist = Float64[], error_norm = norm (Euclidean norm), resid_hist = Float64[], resid_norm = norm (Euclidean norm), iterations=-1, and converged = false.
• Calling LSLogOracle(x_star::Vector{Float64}, cr::Int64) sets the structure with the same parameters as for LSLogOracle(x_star) except collection_rate = cr.

LSLogFull <: LinSysSolverLog

A mutable structure that stores information about a randomized linear solver's behavior. The log assumes that the full linear system is available for processing. The goal of this log is usually for research, development or testing as it is unlikely that the entire residual vector is readily available.

Fields

• collection_rate::Int64, the frequency with which to record information to append to the remaining fields, starting with the initialization (i.e., iteration 0).
• resid_hist::Vector{Float64}, retains a vector of numbers corresponding to the residual (uses the whole system to compute the residual)
• resid_norm::Function, a function that accepts a single vector argument and returns a scalar. Used to compute the residual size.
• iterations::Int64, the number of iterations of the solver.
• converged::Bool, a flag to indicate whether the system has converged by some measure

Constructors

• Calling LSLogFull() sets collection_rate = 1, resid_hist = Float64[], resid_norm = norm (Euclidean norm), iterations = -1, and converged = false.
• Calling LSLogFull(cr::Int64) is the same as calling LSLogFull() except collection_rate = cr.

LSLogMA <: LinSysSolverLog

A mutable structure that stores information for tracking a randomized linear solver's progress. The log assumes that the entire linear system is not available for processing.

Fields

• collection_rate::Int64, the frequency with which to record information about progress estimators to append to the remaining fields, starting with the initialization (i.e., iterate 0).
• ma_info::MAInfo, MAInfo
• resid_hist::Vector{Float64}, contains an estimate of the progress of the randomized solver. These values are stored at iterates specified by collection_rate.
• iota_hist::Vector{Float64}, contains an estimate used for calculating the variability of the progress estimators. These values are stored at iterates specified by collection_rate.
• lambda_hist::Vector{Int64}, contains the widths of the moving average. These values are stored at iterates specified by collection_rate.
• resid_norm::Function, the desired norm used. The default constructor sets this to the Euclidean norm.
• iteration::Int64, the current iteration of the solver.
• converged::Bool, a flag to indicate whether the system has converged by some measure. By default this is false.
• dist_info::SEDistInfo, SEDistInfo

Constructors

• The keyword constructor is defined as

LSLogMA(collection_rate = 1, lambda1 = 1, lambda2 = 30, resid_norm = norm #(Euclidean norm), sigma2 = nothing, omega = nothing, eta = 1, )

For more information see:

• Pritchard, Nathaniel, and Vivak Patel. "Solving, tracking and stopping streaming linear inverse problems." Inverse Problems (2024). doi:10.1088/1361-6420/ad5583.
• Pritchard, Nathaniel, and Vivak Patel. “Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification.” SIAM/ASA J. Uncertainty Quantification 11 (2022): 996-1024. doi.org/10.1137/22M1515057

log_update!(
    log::LinSysSolverLog,
    sampler::LinSysSampler,
    x::AbstractVector,
    samp:s:Tuple,
    iter::Int64,
    A,
    b)

A common interface for specifying different strategies for updating the log with supertype LinSysSolverLog. A sampler of supertype LinSysSampler can be used to provide specific multiple implementations for the same log type. x is the iterate value. samp is the output generated by the sample function (see linears_samplers.jl). iter is the current iteration counter. A and b specify the linear system.

get_uncertainty(log::LSLogMA; alpha = 0.05)

A function that takes a LSLogMA type and a confidence level, alpha, and returns a (1-alpha)-credible intervals for every rho in the log, specifically it returns a tuple with (rho, Upper bound, Lower bound).

MAInfo

A mutable structure that stores information relevant to the moving average of the progress estimator.

Fields

• lambda1::Int64, the width of the moving average during the fast convergence phase of the algorithm. During this fast convergence phase, the majority of variation of the sketched estimator comes from improvement in the solution and thus wide moving average windows inaccurately represent progress.
• lambda2::Int64, the width of the moving average in the slower convergence phase. In the slow convergence phase, each iterate differs from the previous one by a small amount and thus most of the observed variation arises from the randomness of the sketched progress estimator, which is best smoothed by a wide moving average width.
• lambda::Int64, the width of the moving average at the current iteration. This value is not controlled by the user.
• flag::Bool, a boolean indicating which phase we are in, a value of true indicates slow convergence phase.
• idx::Int64, the index indcating what value should be replaced in the moving average buffer.
• res_window::Vector{Float64}, the moving average buffer.

For more information see:

• Pritchard, Nathaniel, and Vivak Patel. "Solving, tracking and stopping streaming linear inverse problems." Inverse Problems (2024). doi:10.1088/1361-6420/ad5583.
• Pritchard, Nathaniel, and Vivak Patel. “Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification.” SIAM/ASA J. Uncertainty Quantification 11 (2022): 996-1024. doi.org/10.1137/22M1515057

SEDistInfo

A mutable structure that stores information about a distribution (i.e., sampling method) in the sub-Exponential family.

Fields

• sampler::Union{DataType, Nothing}, the type of sampling method.
• dimension::Int64, the dimension that of the space that is being sampled.
• block_dimension::Int64, the dimension of the sample.
• sigma2::Union{Float64, Nothing}, the variance parameter in the sub-Exponential family. If not specified by the user, a value is selected from a table based on the sampler. If the sampler is not in the table, then sigma2 is set to 1.
• omega::Union{Float64, Nothing}, the exponential distrbution parameter. If not specified by the user, a value is selected from a table based on the sampler. If the sampler is not in the table, then omega is set to 1.
• eta::Float64, a parameter for adjusting the conservativeness of the distribution, higher value means a less conservative estimate. A recommended value is 1.
• scaling::Float64, a scaling parameter for the norm-squared of the sketched residual to ensure its expectation is the norm-squared of the residual.

For more information see:

• Pritchard, Nathaniel, and Vivak Patel. "Solving, tracking and stopping streaming linear inverse problems." Inverse Problems (2024). doi:10.1088/1361-6420/ad5583.
• Pritchard, Nathaniel, and Vivak Patel. “Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification.” SIAM/ASA J. Uncertainty Quantification 11 (2022): 996-1024. doi.org/10.1137/22M1515057

update_ma!(
    log::LSLogMA, 
    res::Union{AbstractVector, Real}, 
    lambda_base::Int64, 
    iter::Int64
)

Function that updates the moving average tracking statistic.

Inputs

• log::LSLogMA, the moving average log structure.
• res::Union{AbstractVector, Real}, the sketched residual for the current iteration.
• lambda_base::Int64, which lambda, between lambda1 and lambda2, is currently being used.
• iter::Int64, the current iteration.

Outputs

Updates the log datatype and does not explicitly return anything.

get_SE_constants!(log::LSLogMA, sampler::Type{T<:LinSysSampler})

A function that returns a default set of sub-Exponential constants for each sampling method. This function is not exported and thus the user does not have direct access to it.

Inputs

• log::LSLogMA, the log containing all the tracking information.
• sampler::Type{LinSysSampler}, the type of sampler being used.

Outputs

Performs an inplace update of the sub-Exponential constants for the log. Additionally, updates the scaling constant to ensure expectation of block norms is equal to true norm. If default is not a defined a warning is returned that sigma2 is set 1 and scaling is set to 1.