README.md

MatrixCovers

This package computes covers of matrices: non-negative vectors a and b such that a[i] * b[j] >= abs(A[i, j]) for all i, j. Covers are the natural scale-covariant representation of a matrix, making them a useful building block for scale-invariant numerical analysis. In particular, $\hat A = A ./ (a b^T)$ is scale-invariant, and because $|\hat A[i, j]| \le 1$ for all i and j, this simple construct finds applications that range from statistical normalization of data to the design of well-behaved numerical algorithms (thanks, e.g., to bounds on $\hat A$'s eigenvalues).

The package provides O(mn) heuristics (symcover, cover), soft covers that penalize violations (soft_symcover, soft_cover), and objective-minimal hard covers (symcover_min, cover_min). Penalties are functions of the log slack z = log(a[i]*b[j]) - log|A[i,j]| of each nonzero entry. The defaults, the ℓ₂ penalty AbsLog{2} (z^2) for hard covers and the power-mean penalty PowerMean{2} for soft covers, use built-in solvers; other penalties use JuMP with HiGHS or Ipopt.

Installation

julia> using Pkg; Pkg.add("MatrixCovers")

Example

julia> using MatrixCovers, LinearAlgebra

julia> A = [4.0 2.0; 2.0 16.0];

julia> a = symcover(A)      # a[i] * a[j] >= abs(A[i, j])
2-element Vector{Float64}:
 2.0
 4.0

julia> a * a'               # dominates A entrywise
2×2 Matrix{Float64}:
 4.0   8.0
 8.0  16.0

julia> iscover(a, A)
true

Covers are scale-covariant:

julia> D = Diagonal([10.0, 0.5]);

julia> symcover(D * A * D) ≈ D * a
true

For nonsymmetric matrices, cover returns separate row and column scales. cover_min minimizes a penalty subject to the coverage constraint:

julia> M = [1.0 2.0 3.0; 6.0 5.0 4.0];

julia> a, b = cover(M);

julia> iscover(a, b, M)
true

julia> aq, bq = cover_min(AbsLog{2}(), M);

julia> cover_objective(AbsLog{2}(), aq, bq, M) <= cover_objective(AbsLog{2}(), a, b, M)
true

See the documentation for the algorithm guide and API reference.