Linear map (LinearMap)

LinearMap{N, S<:LazySet{N}, NM, MAT<:AbstractMatrix{NM}}
    <: AbstractAffineMap{N, S}

Type that represents a linear transformation $M⋅X$ of a set $X$.

Fields

• M – matrix/linear map
• X – set

Notes

This type is parametric in the elements of the linear map, NM, which is independent of the numeric type of the wrapped set (N). Typically NM = N, but there may be exceptions, e.g., if NM is an interval that holds numbers of type N, where N is a floating point number type such as Float64.

The linear map preserves convexity: if X is convex, then any linear map of X is convex as well.

Examples

For the examples we create a $3×2$ matrix and a two-dimensional unit square.

julia> M = [1 2; 1 3; 1 4]; X = BallInf([0, 0], 1);

The function $*$ can be used as an alias to construct a LinearMap object.

julia> lm = LinearMap(M, X)
LinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, Matrix{Int64}}([1 2; 1 3; 1 4], BallInf{Int64, Vector{Int64}}([0, 0], 1))

julia> lm2 = M * X
LinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, Matrix{Int64}}([1 2; 1 3; 1 4], BallInf{Int64, Vector{Int64}}([0, 0], 1))

julia> lm == lm2
true

For convenience, M does not need to be a matrix; we also allow to use vectors (interpreted as an $n×1$ matrix) and UniformScalings resp. scalars (interpreted as a scaling, i.e., a scaled identity matrix). Scaling by $1$ is ignored.

julia> using LinearAlgebra: I

julia> Y = BallInf([0], 1);  # one-dimensional interval

julia> [2, 3] * Y
LinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, Matrix{Int64}}([2; 3;;], BallInf{Int64, Vector{Int64}}([0], 1))

julia> lm3 = 2 * X
LinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, SparseArrays.SparseMatrixCSC{Int64, Int64}}(sparse([1, 2], [1, 2], [2, 2], 2, 2), BallInf{Int64, Vector{Int64}}([0, 0], 1))

julia> 2I * X == lm3
true

julia> 1I * X == X
true

Applying a linear map to a LinearMap object combines the two maps into a single LinearMap instance. Again we can make use of the conversion for convenience.

julia> B = transpose(M); B * lm
LinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, Matrix{Int64}}([3 9; 9 29], BallInf{Int64, Vector{Int64}}([0, 0], 1))

julia> B = [3, 4, 5]; B * lm
LinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, Matrix{Int64}}([12 38], BallInf{Int64, Vector{Int64}}([0, 0], 1))

julia> B = 2; B * lm
LinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, Matrix{Int64}}([2 4; 2 6; 2 8], BallInf{Int64, Vector{Int64}}([0, 0], 1))

The application of a LinearMap to a ZeroSet or an EmptySet is simplified automatically.

julia> M * ZeroSet{Int}(2)
ZeroSet{Int64}(3)

julia> M * EmptySet{Int}(2)
EmptySet{Int64}(3)

    *(M::Union{AbstractMatrix, UniformScaling, AbstractVector, Real},
      X::LazySet)

Alias to create a LinearMap object.

Input

• M – linear map
• X – set

Output

A lazy linear map, i.e., a LinearMap instance.

dim(lm::LinearMap)

Return the dimension of a linear map.

Input

• lm – linear map

Output

The ambient dimension of the linear map.

ρ(d::AbstractVector, lm::LinearMap; kwargs...)

Evaluate the support function of the linear map.

Input

• d – direction
• lm – linear map
• kwargs – additional arguments that are passed to the support function algorithm

Output

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M⋅S$, where $M$ is a matrix and $S$ is a set, it follows that $ρ(d, L) = ρ(M^T d, S)$ for any direction $d$.

σ(d::AbstractVector, lm::LinearMap)

Return a support vector of the linear map.

Input

• d – direction
• lm – linear map

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M⋅S$, where $M$ is a matrix and $S$ is a set, it follows that $σ(d, L) = M⋅σ(M^T d, S)$ for any direction $d$.

∈(x::AbstractVector, lm::LinearMap)

Check whether a given point is contained in a linear map.

Input

• x – point/vector
• lm – linear map

Output

true iff $x ∈ lm$.

Algorithm

Note that $x ∈ M⋅S$ iff $M^{-1}⋅x ∈ S$. This implementation does not explicitly invert the matrix: instead of $M^{-1}⋅x$ it computes $M \ x$. Hence it also works for non-square matrices.

Examples

julia> lm = LinearMap([2.0 0.0; 0.0 1.0], BallInf([1., 1.], 1.));

julia> [5.0, 1.0] ∈ lm
false
julia> [3.0, 1.0] ∈ lm
true

An example with non-square matrix:

julia> B = BallInf(zeros(4), 1.);

julia> M = [1. 0 0 0; 0 1 0 0]/2;

julia> [0.5, 0.5] ∈ M*B
true

an_element(lm::LinearMap)

Return some element of a linear map.

Input

• lm – linear map

Output

An element in the linear map. It relies on the an_element function of the wrapped set.

vertices_list(lm::LinearMap; prune::Bool=true)

Return the list of vertices of a (polytopic) linear map.

Input

• lm – linear map
• prune – (optional, default: true) if true, we remove redundant vertices

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polytopic and compute the vertices of X. The result is just the linear map applied to each vertex.

constraints_list(lm::LinearMap)

Return the list of constraints of a (polyhedral) linear map.

Input

• lm – linear map

Output

The list of constraints of the linear map.

Notes

We assume that the underlying set X is polyhedral, i.e., offers a method constraints_list(X).

Algorithm

We fall back to a concrete set representation by applying linear_map.

linear_map(M::AbstractMatrix, lm::LinearMap)

Return the linear map of a lazy linear map.

Input

• M – matrix
• lm – linear map

Output

A set representing the linear map.

project(S::LazySet{N}, block::AbstractVector{Int}, set_type::Type{LM},
        [n]::Int=dim(S); [kwargs...]) where {N, LM<:LinearMap}

Project a high-dimensional set to a given block by using a lazy linear map.

Input

• S – set
• block – block structure - a vector with the dimensions of interest
• LinearMap – used for dispatch
• n – (optional, default: dim(S)) ambient dimension of the set S

Output

A lazy LinearMap representing the projection of the set S to block block.

Projection(X::LazySet{N}, variables::AbstractVector{Int}) where {N}

Return a lazy projection of a set.

Input

• X – set
• variables – variables of interest

Output

A lazy LinearMap that corresponds to projecting X along the given variables variables.

Examples

The projection of a three-dimensional cube into the first two coordinates:

julia> B = BallInf([1.0, 2, 3], 1.0)
BallInf{Float64, Vector{Float64}}([1.0, 2.0, 3.0], 1.0)

julia> Bproj = Projection(B, [1, 2])
LinearMap{Float64, BallInf{Float64, Vector{Float64}}, Float64, SparseArrays.SparseMatrixCSC{Float64, Int64}}(sparse([1, 2], [1, 2], [1.0, 1.0], 2, 3), BallInf{Float64, Vector{Float64}}([1.0, 2.0, 3.0], 1.0))

julia> isequivalent(Bproj, BallInf([1.0, 2], 1.0))
true