Iterate and utility reference

SparseIterate([T = Float64,] n)
SparseIterate([T = Float64,] n, m)
SparseIterate(x::Union{SparseVector, SparseMatrixCSC, Array})

A vector or matrix that stores its nonzero entries in a compact list, so that reading or writing any entry is O(1) and multiplying by it costs O(nnz). Intended for coordinate-descent and active-set iterates that stay sparse. Its coordinates (see ncoordinates) are its entries, in linear order.

Setting an entry to zero keeps it in the list; call dropzeros! to remove stored zeros. The stored entries are the active coordinates (activecoordinates).

SymmetricSparseIterate([T = Float64,] p)
SymmetricSparseIterate(X::AbstractMatrix)

A sparse symmetric p × p matrix that stores only its lower triangle, with the same O(1) access as SparseIterate. It is an ordinary p × p matrix: x[r, c] and x[c, r] are the same entry, and linear indices, length(x) = p² and iteration follow the dense matrix, so that an off-diagonal entry is visited twice.

Writing x[r, c] writes x[c, r] too. Broadcasting into x, copyto!, fill!, rmul!, lmul!, axpy! and axpby! update each entry once, from the lower triangle of a source that is not symmetric. Other functions that update the entries of x one at a time, such as map! or mul! into x, would update an off-diagonal entry twice, and those that build a result that is not symmetric in similar(x), such as cumsum or circshift, need Matrix(x). triu, tril and sparse return a SparseMatrixCSC.

Its coordinates are the p(p+1)/2 entries of the lower triangle, numbered column by column (tril_index): prox_coordinate! updates them, ncoordinates counts them, activecoordinates lists the stored ones and coordinates is a vector view of them.

activate!(x::SparseIterate, i)
activate!(x::SymmetricSparseIterate, k)
activate!(x::AtomIterate, k)

Make coordinate i of x active, storing it as an explicit zero if it is not stored already, and return x. Assigning a zero does not store an entry, so this is how a coordinate joins the active set of an active-set solver; dropzeros! removes it again while it is zero. For an AtomIterate, make group k active, keeping its entries.

activecoordinates(x)

A vector of the active coordinates of x (see nactive), in the order in which they became active, except that dropzeros! moves the last ones into the places of those it removes. The vector is a view of the internal list: it does not grow when coordinates become active, so call activecoordinates again after changing the active set.

coordinates(x)

A vector view of the coordinates of x (see ncoordinates): x itself for a SparseIterate, whose coordinates are its entries in linear order, and the entries of the lower triangle for a SymmetricSparseIterate. Writing through the view writes x.

isactive(x, k)

Whether coordinate k of x is active (see nactive).

nactive(x)

The number of active coordinates of x: the stored entries of a SparseIterate or SymmetricSparseIterate, the active groups of an AtomIterate. Active-set solvers use them as the active set.

ncoordinates(x)

The number of coordinates of the iterate x that prox_coordinate! updates: the entries of a SparseIterate, the entries of the lower triangle of a SymmetricSparseIterate, the groups of an AtomIterate.

AtomIterate([T = Float64,] p, groups)
AtomIterate(x::AbstractVector, groups)
AtomIterate([T = Float64,] p, num_groups::Integer)
AtomIterate(x::AbstractVector, num_groups::Integer)

A vector of length p whose coordinates, for coordinate descent, are the groups ("atoms") x.groups[k], which partition 1:p. The groups are ranges such as 1:5 or vectors of indices such as [2, 7, 9], of any sizes; AtomIterate(p, num_groups) and AtomIterate(x, num_groups) split 1:p into num_groups equal contiguous groups.

As the stored entries of a SparseIterate do, a set of active groups serves as the active set of a solver, and the entries of the other groups are zero. Writing a nonzero entry activates its group, activate! activates a group, and dropzeros! deactivates the active groups whose entries are all zero; an iterate built from a vector x starts with the groups that hold a nonzero entry. Reading or writing an entry is O(1), and so is activating or deactivating a group. ncoordinates is the number of groups, nactive, activecoordinates and isactive give the active groups, and atom is a view of the entries of a group.

atom(x::AtomIterate, k)

A view of the entries of group k of x. Writing through it does not activate the group; see activate!.

norm_diff(A, B, p = 2)

‖A - B‖ without allocating A - B: the Euclidean (Frobenius) norm for p = 2, the largest absolute entry for p = Inf. The result is real, also for complex arrays.

opnorm2(X)

Estimate the squared spectral norm ‖X‖₂² by Lanczos iteration, using only products with X and its adjoint, without forming a Gram matrix or densifying a sparse matrix. The result has floating element type matching X.

This is a numerical estimate, not a certified upper bound: Lanczos can miss an eigenspace orthogonal to its deterministic starting vector. Algorithms requiring a guaranteed bound should use an independently known bound (for example opnorm(X, 1) * opnorm(X, Inf)) or a suitable line search.

shrink(v, c)

Soft thresholding: sign(v) ⋅ max(|v| - c, 0) for a threshold c ≥ 0, the proximal operator of c|⋅|. A NaN in v propagates.

tril_cartesian(p, k)

The entry (r, c), r ≥ c, of the lower triangle of a p × p matrix with linear index k, numbered column by column. Inverse of tril_index.

tril_index(p, r, c)

The linear index of entry (r, c), r ≥ c, of the lower triangle of a p × p matrix, numbered column by column: the coordinate of a SymmetricSparseIterate that holds the entry. Inverse of tril_cartesian.