Exponential map

ExponentialMap{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the action of an exponential map on a convex set.

Fields

• spmexp – sparse matrix exponential
• X – convex set

Examples

The ExponentialMap type is overloaded to the usual times * operator when the linear map is a lazy matrix exponential. For instance,

julia> using SparseArrays

julia> A = sprandn(100, 100, 0.1);

julia> E = SparseMatrixExp(A);

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

julia> M = E * B; # represents the image set: exp(A) * B

julia> M isa ExponentialMap
true

julia> dim(M)
100

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

julia> E * ZeroSet(100)
ZeroSet{Float64}(100)

julia> E * EmptySet()
EmptySet{Float64}()

dim(em::ExponentialMap)

Return the dimension of an exponential map.

Input

• em – an ExponentialMap

Output

The ambient dimension of the exponential map.

ρ(d::AbstractVector{N}, em::ExponentialMap{N}) where {N<:Real}

Return the support function of the exponential map.

Input

• d – direction
• em – exponential map

Output

The support function in the given direction.

Notes

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

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

σ(d::AbstractVector{N}, em::ExponentialMap{N}) where {N<:Real}

Return the support vector of the exponential map.

Input

• d – direction
• em – exponential map

Output

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

Notes

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

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

∈(x::AbstractVector{N}, em::ExponentialMap{N}) where {N<:Real}

Check whether a given point is contained in an exponential map of a convex set.

Input

• x – point/vector
• em – exponential map of a convex set

Output

true iff $x ∈ em$.

Algorithm

This implementation exploits that $x ∈ \exp(M)⋅S$ iff $\exp(-M)⋅x ∈ S$. This follows from $\exp(-M)⋅\exp(M) = I$ for any $M$.

Examples

julia> using SparseArrays

julia> em = ExponentialMap(
        SparseMatrixExp(sparse([1, 2], [1, 2], [2.0, 1.0], 2, 2)),
        BallInf([1., 1.], 1.));

julia> [-1.0, 1.0] ∈ em
false
julia> [1.0, 1.0] ∈ em
true

isbounded(em::ExponentialMap)

Determine whether an exponential map is bounded.

Input

• em – exponential map

Output

true iff the exponential map is bounded.

isempty(em::ExponentialMap)

Return if an exponential map is empty or not.

Input

• em – exponential map

Output

true iff the wrapped set is empty.

vertices_list(em::ExponentialMap{N}) where {N<:Real}

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

Input

• em – exponential map

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polytopic. Then the result is just the exponential map applied to the vertices of X.

ExponentialProjectionMap{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the application of a projection of a sparse matrix exponential to a convex set.

Fields

• spmexp – projection of a sparse matrix exponential
• X – convex set

dim(eprojmap::ExponentialProjectionMap)

Return the dimension of a projection of an exponential map.

Input

• eprojmap – projection of an exponential map

Output

The ambient dimension of the projection of an exponential map.

σ(d::AbstractVector{N},
  eprojmap::ExponentialProjectionMap{N}) where {N<:Real}

Return the support vector of a projection of an exponential map.

Input

• d – direction
• eprojmap – projection of an exponential map

Output

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

Notes

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

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

isbounded(eprojmap::ExponentialProjectionMap)

Determine whether an exponential projection map is bounded.

Input

• eprojmap – exponential projection map

Output

true iff the exponential projection map is bounded.

Algorithm

We first check if the left or right projection matrix is zero or the wrapped set is bounded. Otherwise, we check boundedness via isbounded_unit_dimensions.

isempty(eprojmap::ExponentialProjectionMap)

Return if an exponential projection map is empty or not.

Input

• eprojmap – exponential projection map

Output

true iff the wrapped set is empty.

SparseMatrixExp{N}

Type that represents the matrix exponential, $\exp(M)$, of a sparse matrix.

Fields

• M – sparse matrix; it should be square

Examples

Take for example a random sparse matrix of dimensions $100 × 100$ and with occupation probability $0.1$:

julia> using SparseArrays

julia> A = sprandn(100, 100, 0.1);

julia> using Expokit

julia> E = SparseMatrixExp(A);

julia> size(E)
(100, 100)

Here E is a lazy representation of $\exp(A)$. To compute with E, use get_row and get_column resp. get_rows and get_columns. These functions return row and column vectors (or matrices). For example:

julia> get_row(E, 10); # compute E[10, :]

julia> get_column(E, 10); # compute E[:, 10]

julia> get_rows(E, [10]); # same as get_row(E, 10) but a 1x100 matrix is returned

julia> get_columns(E, [10]); # same as get_column(E, 10) but a 100x1 matrix is returned

Notes

This type is provided for use with very large and very sparse matrices. The evaluation of the exponential matrix action over vectors relies on the Expokit package. Hence, you will have to install and load this optional dependency to have access to the functionality of SparseMatrixExp.

    *(spmexp::SparseMatrixExp{N}, X::LazySet{N}) where {N<:Real}

Return the exponential map of a convex set from a sparse matrix exponential.

Input

• spmexp – sparse matrix exponential
• X – convex set

Output

The exponential map of the convex set.

get_row(spmexp::SparseMatrixExp{N}, i::Int) where {N}

Return a single row of a sparse matrix exponential.

Input

• spmexp – sparse matrix exponential
• i – row index

Output

A row vector corresponding to the ith row of the matrix exponential.

Notes

This function uses Julia's transpose function to create the result. The result is of type Transpose; in Julia versions older than v0.7, the result was of type RowVector.

ProjectionSparseMatrixExp{N<:Real}

Type that represents the projection of a sparse matrix exponential, i.e., $L⋅\exp(M)⋅R$ for a given sparse matrix $M$.

Fields

• L – left multiplication matrix
• E – sparse matrix exponential
• R – right multiplication matrix

    *(projspmexp::ProjectionSparseMatrixExp, X::LazySet)

Return the application of a projection of a sparse matrix exponential to a convex set.

Input

• projspmexp – projection of a sparse matrix exponential
• X – convex set

Output

The application of the projection of a sparse matrix exponential to the convex set.