SubspacePreservingSparsification.jl

Implementation of an algorithm, that takes a real Matrix M and finds a sparse approximation of the same size. The algorithm was developed by Chetan Jhurani under the name sparse spectral approximation (SSA). See https://github.com/cjhurani/txssa for more detailed documentation, also with regard to the mathematical background, and for implementations in C/C++ and in Matlab.

Installation

To install this package and its dependencies, open the Julia REPL and run

julia> ]add SubspacePreservingSparsification

API reference

SubspacePreservingSparsification.bin_sparse_matrix! — Method

bin_sparse_matrix!(M::AbstractArray, M_id::AbstractSparseMatrixCSC, max_num_bins::Integer)

Compute a Binning pattern in M_id from the sparsity pattern in M_id.

M_id is SparseMatrixCSC{Int64, Int64} with the same shape as M, when handed over it contains only 0 and 1. After usage it contains an Integer corresponding to a bin or 0. According to the Binning Pattern, similar valued entries can be considered the same.

M is the matrix which entries are used for binning. max_num_bins is the maximum number of bins and must be non-negative, if max_num_bins=0, no binning is performed and only the sparsity pattern in M_id is used then.

See also: sparsify, sparsity_pattern.

Examples

julia> bin_sparse_matrix!([4 1 4.01; 0.1 17.1 17; 0.2 4 29], sparse([1 0 1; 0 1 1; 0 0 1]), 200)
3×3 SparseMatrixCSC{Int64, Int64} with 5 stored entries:
 1  ⋅  1
 ⋅  2  2
 ⋅  ⋅  3

source

SubspacePreservingSparsification.binned_minimization — Method

binned_minimization(M_id::AbstractSparseMatrixCSC,
B::AbstractMatrix, C::AbstractMatrix, D::AbstractMatrix)

Solves a optimization problem of the from

\[Y A + B Y = D.\]

under the binning constraints given in the SparseMatrixCSC{Int64, Int64} M_id.

See also: sparsify.

Examples

julia> binned_minimization([16.99 65 64.96; 0.1 17.01 0.1], sparse([1 2 2; 0 1 0]), Matrix(I, 3, 3) , Matrix(I, 2, 2), Matrix(I, 2, 3))
2×3 SparseMatrixCSC{Float64, Int64} with 4 stored entries:
 0.5  0.0  0.0
  ⋅   0.5   ⋅

source

SubspacePreservingSparsification.pinv_qr — Method

pinv_M, rnull_optional, lnull_optional = pinv_qr(M::AbstractArray)

Computes Moore-Penrose pseudoinverse of M using a rank-revealing QR factorization and optionally returns an orthonormal basis for right and left null-space. This can be significantly faster than using SVD for computing the pseudoinverse. Moreover, A can be sparse or dense.

Examples

julia> pinv_qr([3 8 17; 2 1 4; 8 3 21])
([-0.10344827586206914 1.344827586206895 -0.17241379310344793;0.1149425287356321 0.8390804597701144 -0.2528735632183907;0.022988505747126506 -0.6321839080459762 0.1494252873563217], Matrix{Float64}(undef, 3, 0), Matrix{Float64}(undef, 3, 0))

source

SubspacePreservingSparsification.sparsify — Method

sparsify(M::AbstractArray, ratio::Real, p::Real, max_num_bins::Integer,
    impose_null_spaces=false::Bool)

Compute a SparseMatrixCSC{Float64, Int64} X for a matrix M, that is sparse and spectrally close to M, especially in the lower end of the singular value spectrum.

Wrapper function over all functionality.

Compute a sparse approximation for a matrix M. First the sparsity pattern is computed with a ratio in $[0,1]$ that determines the sparsity (0 means more sparse, 1 means less) and with p in $(0, \infty ]$ that determines which norm is used to find the sparsity pattern.

Next the sparsity pattern is used to find a binning pattern, the non-negative integer max_num_bins determines whats the maximum number of bins is (200-1000 is a reasonable choice). max_num_bins=0 means no binning is performed and can lead to significant slowdown.

Then an optimization problem, with constraints given by the binning pattern, is solved to find a sparse approximation X for M.

If impose_null_spaces=true, another optimization problem is solved that ensures that X and M have the same null space.

Examples

julia> sparsify([16.99 65; 0.1 17.01], 0.6, 2, 200)
2×2 SparseMatrixCSC{Float64, Int64} with 3 stored entries:
 16.8041  64.2499
   ⋅      16.8041

source

SubspacePreservingSparsification.sparsity_pattern — Function

sparsity_pattern(M::AbstractArray, ratio::Real, p::Real, min_per_row=0::Integer, min_per_col=0::Integer)

Compute a pattern matrix M_pat which is a p-norm sparsity pattern for M.

M_pat is a sparse SparseMatrixCSC{Int64, Int64} of the same shape as M and contains only 0 or 1.

ratio is a measure for how sparse the pattern is supposed to be and must be in $[0,1]$. p determines which norm is used and should be in $(0, \infty ]$. min_per_row is the minimum number of non-zeros needed per row and min_per_col is the minimum number of non-zeros needed per column, Defaults are 0.

See also: sparsify, bin_sparse_matrix!.

Examples

julia> sparsity_pattern([4 1; 0.1 17], 0.6, 2)
2×2 SparseMatrixCSC{Int64, Int64} with 2 stored entries:
 1  ⋅
 ⋅  1

source