MinimumVolumeEllipsoids.jl

MinimumVolumeEllipsoids.jl is a Julia module which implements algorithms to compute Minimum-Volume Ellipsoids (MVE) from given data. The algorithms are implemented as defined in Minimum-volume ellipsoids: Theory and algorithms by Michael J. Todd. The code has been adapted from the original Matlab implementation supplied with the book. For the original code see here: http://archive.siam.org/books/mo23/

In addition to computing the MVE this module also includes a function to sample uniformly over the ellipsoid using an algorithm proposed by Dezert & Musso.

Usage

To compute the minimum-volume enclosing ellipsoid centered at the origin for a set of four points run the following code:

using MinimumVolumeEllipsoids

X = [
    -1 -1  1 2
     1 -1 -1 2
]

ϵ = minimum_volume_ellipsoid(X, centered=true)

This results in an ellipsoid with the center ϵ.x

2-element Vector{Float64}:
 0.0
 0.0

and the shape matrix ϵ.H

2×2 PDMat{Float64, Matrix{Float64}}:
  0.625  -0.375
 -0.375   0.625

To relax the centered condition an compute the optimal minimum-volume enclosing ellipsoid simply omit the centered keyword

ϵ = minimum_volume_ellipsoid(X)

To create uniform random samples over either ellipsoid simply run

U = rand(ϵ, 1000)

References

Dezert, J., & Musso, C. (2001). An efficient method for generating points uniformly distributed in hyperellipsoids. In Proceedings of the Workshop on Estimation, Tracking and Fusion: A Tribute to Yaakov Bar-Shalom.

Todd, M. J. (2016). Minimum-volume ellipsoids: Theory and algorithms. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974386