Inverse linear map (InverseLinearMap)

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

Given a linear transformation $M$, this type represents the linear transformation $M⁻¹⋅X$ of a set $X$ without actually computing $M⁻¹$.

Fields

• M – matrix (typically invertible, which can be checked in the constructor)
• X – set

Notes

Many set operations avoid computing the inverse of the matrix.

In principle, the matrix does not have to be invertible (it can for instance be rectangular) for many set operations.

This type is parametric in the elements of the inverse 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 type such as Float64.

Examples

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

julia> A = [1 2 3; 2 3 1; 3 1 2];

julia> X = BallInf([0, 0, 0], 1);

julia> ilm = InverseLinearMap(A, X)
InverseLinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, Matrix{Int64}}([1 2 3; 2 3 1; 3 1 2], BallInf{Int64, Vector{Int64}}([0, 0, 0], 1))

Applying an inverse linear map to a InverseLinearMap object combines the two maps into a single InverseLinearMap instance.

julia> B = transpose(A); ilm2 = InverseLinearMap(B, ilm)
InverseLinearMap{Int64, BallInf{Int64, Vector{Int64}}, Int64, Matrix{Int64}}([14 11 11; 11 14 11; 11 11 14], BallInf{Int64, Vector{Int64}}([0, 0, 0], 1))

julia> ilm2.M == A*B
true

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

julia> InverseLinearMap(A, ZeroSet{Int}(3))
ZeroSet{Int64}(3)

dim(ilm::InverseLinearMap)

Return the dimension of an inverse linear map.

Input

• ilm – inverse linear map

Output

The ambient dimension of the inverse linear map.

σ(d::AbstractVector, ilm::InverseLinearMap)

Return a support vector of a inverse linear map.

Input

• d – direction
• ilm – inverse 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^{-1}⋅X$, where $M$ is a matrix and $X$ is a set, since (M^T)^{-1}=(M^{-1})^T, it follows that $σ(d, L) = M^{-1}⋅σ((M^T)^{-1} d, X)$ for any direction $d$.

ρ(d::AbstractVector, ilm::InverseLinearMap)

Evaluate the support function of the inverse linear map.

Input

• d – direction
• ilm – inverse linear map

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^{-1}⋅X$, where $M$ is a matrix and $X$ is a set, it follows that $ρ(d, L) = ρ((M^T)^{-1} d, X)$ for any direction $d$.

∈(x::AbstractVector, ilm::InverseLinearMap)

Check whether a given point is contained in the inverse linear map of a set.

Input

• x – point/vector
• ilm – inverse linear map of a set

Output

true iff $x ∈ ilm$.

Algorithm

This implementation does not explicitly invert the matrix since it uses the property $x ∈ M^{-1}⋅X$ iff $M⋅x ∈ X$.

Examples

julia> ilm = LinearMap([0.5 0.0; 0.0 -0.5], BallInf([0., 0.], 1.));

julia> [1.0, 1.0] ∈ ilm
false

julia> [0.1, 0.1] ∈ ilm
true

an_element(ilm::InverseLinearMap)

Return some element of an inverse linear map.

Input

• ilm – inverse linear map

Output

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

vertices_list(ilm::InverseLinearMap; prune::Bool=true)

Return the list of vertices of a (polyhedral) inverse linear map.

Input

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

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polyhedral. Then the result is just the inverse linear map applied to the vertices of X.

constraints_list(ilm::InverseLinearMap)

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

Input

• ilm – inverse linear map

Output

A list of constraints of the inverse linear map.

Algorithm

We fall back to a concrete set representation and apply linear_map_inverse.

linear_map(M::AbstractMatrix, ilm::InverseLinearMap)

Return the linear map of a lazy inverse linear map.

Input

• M – matrix
• ilm – inverse linear map

Output

The set representing the linear map of the lazy inverse linear map of a set.

Notes

This implementation is inefficient because it computes the concrete inverse of $M$, which is what InverseLinearMap is supposed to avoid.