Linear map (LinearMap)

LazySets.LinearMapType
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)
source
Base.:*Method
    *(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.

source
LazySets.API.dimMethod
dim(lm::LinearMap)

Return the dimension of a linear map.

Input

  • lm – linear map

Output

The ambient dimension of the linear map.

source
LazySets.API.ρMethod
ρ(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$.

source
LazySets.API.σMethod
σ(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$.

source
Base.:∈Method
∈(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
source
LazySets.API.an_elementMethod
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.

source
LazySets.API.vertices_listMethod
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.

source
LazySets.API.constraints_listMethod
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.

source
LazySets.API.linear_mapMethod
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.

source
LazySets.API.projectMethod
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.

source

Inherited from LazySet:

Inherited from AbstractAffineMap:

The lazy projection of a set can be conveniently constructed using Projection.

LazySets.ProjectionFunction
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
source