Exponential map

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

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

Fields

• spmexp – sparse matrix exponential
• X – set

Notes

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

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 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(100)
∅(100)

dim(em::ExponentialMap)

Return the dimension of an exponential map.

Input

• em – exponential map

Output

The ambient dimension of the exponential map.

ρ(d::AbstractVector, em::ExponentialMap;
  [backend]=get_exponential_backend())

Evaluate the support function of the exponential map.

Input

• d – direction
• em – exponential map
• backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

The evaluation of the support function in the given direction.

Notes

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

σ(d::AbstractVector, em::ExponentialMap;
  [backend]=get_exponential_backend())

Return a support vector of an exponential map.

Input

• d – direction
• em – exponential map
• backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

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

Notes

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

∈(x::AbstractVector, em::ExponentialMap;
  [backend]=get_exponential_backend())

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

Input

• x – point/vector
• em – exponential map of a set
• backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

true iff $x ∈ em$.

Algorithm

This implementation exploits that $x ∈ \exp(M)⋅X$ iff $\exp(-M)⋅x ∈ X$. 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)

Check whether an exponential map is bounded.

Input

• em – exponential map

Output

true iff the exponential map is bounded.

vertices_list(em::ExponentialMap; [backend]=get_exponential_backend())

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

Input

• em – polytopic exponential map
• backend – (optional; default: get_exponential_backend()) exponentiation backend

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.

SparseMatrixExp{N}

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

Fields

• M – sparse square matrix

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 ExponentialUtilities

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 yields a 1x100 matrix

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

Notes

This type is provided for use with large and sparse matrices. The evaluation of the exponential matrix action over vectors relies on external packages such as ExponentialUtilities or Expokit. Hence, you will have to install and load such an optional dependency to have access to the functionality of SparseMatrixExp.

    *(spmexp::SparseMatrixExp, X::LazySet)

Alias to create an ExponentialMap object.

Input

• spmexp – sparse matrix exponential
• X – set

Output

The exponential map of the set.

get_row(spmexp::SparseMatrixExp{N}, i::Int;
        [backend]=get_exponential_backend()) where {N}

Return a single row of a sparse matrix exponential.

Input

• spmexp – sparse matrix exponential
• i – row index
• backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

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

Notes

This implementation 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.

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

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

Fields

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

Notes

The exponential projection preserves convexity: if X is convex, then any exponential projection of X is convex as well.

Examples

We use a random sparse projection matrix of dimensions $6 × 6$ with occupation probability $0.5$ and apply it to the 2D unit ball in the infinity norm:

julia> using SparseArrays

julia> R = sparse([5, 6], [1, 2], [1.0, 1.0]);

julia> L = sparse([1, 2], [1, 2], [1.0, 1.0], 2, 6);

julia> using ExponentialUtilities

julia> A = sprandn(6, 6, 0.5);

julia> E = SparseMatrixExp(A);

julia> M = ProjectionSparseMatrixExp(L, E, R);

julia> B = BallInf(zeros(2), 1.0);

julia> X = ExponentialProjectionMap(M, B);

julia> dim(X)
2

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, eprojmap::ExponentialProjectionMap;
  [backend]=get_exponential_backend())

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

Input

• d – direction
• eprojmap – projection of an exponential map
• backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

A 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$.

ρ(d::AbstractVector, eprojmap::ExponentialProjectionMap;
  [backend]=get_exponential_backend())

Evaluate the support function of a projection of an exponential map.

Input

• d – direction
• eprojmap – projection of an exponential map
• backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

Evaluation of the support function 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) = ρ(R^T⋅M^T⋅L^T⋅d, X)$ for any direction $d$.

isbounded(eprojmap::ExponentialProjectionMap)

Check whether a projection of an exponential map is bounded.

Input

• eprojmap – projection of an exponential map

Output

true iff the projection of an exponential 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 LazySets._isbounded_unit_dimensions.

ProjectionSparseMatrixExp{N, MN1<:AbstractSparseMatrix{N},
                             MN2<:AbstractSparseMatrix{N},
                             MN3<:AbstractSparseMatrix{N}}

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)

Alias to create an ExponentialProjectionMap object.

Input

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

Output

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