Minimum Volume Enclosing Ellipsoids

1.6k Views Asked by At

suppose we have a simplex in $R^{n}$. the vertices of this simplex is permuted a point in $R^{n}$. for example in $R^{3}$, the vertices are $(a,b,c)$ , $(c,a,b)$, $(b,c,a)$. and we know that there are linearly independent so form a simplex.

my question is that what is the equation of the ellipsoid which contains described simplex and which has minimal volume with this property.

1

There are 1 best solutions below

6
On

Finding the minimum volume ellipsoid for a set of $m$ points in $R^{n}$ is a problem that has been extensively studied. There isn't a closed form formula, but rather optimization algorithms are used to find a minimum volume ellipsoid. See the recent book

Michael J. Todd, Minimum-Volume Ellipsoids: Theory and Algorithms, SIAM 2016.

Todd's book includes MATLAB codes to implement the methods discussed in the book.

In your case, the $n$ points lie in an $n-1$ dimensional hyperplane in $R^{n}$, so the minimum volume ellipsoid is not actually attained as a full $n$-dimensional ellipsoid. You can create arbitrarily thin (in the direction perpendicular to the hyperplane) ellipsoids around the points with volumes that approach 0. In this degenerate case, there are a couple of things that you could do:

if you want a full $n$-dimensional ellipsoid in the original space, simply add a point to make the set full-dimensional by taking the average of the $n$ points and then adding a small displacement orthogonal to the hyperplane to get a point outside of the hyperplane.

You could also reduce the dimension of the problem by 1 and find a minimum volume $n-1$ dimensional ellipsoid in the $n-1$ dimensional hyperplane defined by the points.

To do this, start with points $x^{(1)}$, $\ldots$, $x^{(n)}$, and define $n-1$ vectors

$y^{(i)}=x^{(i)}-x^{(n)},\;\; i=1, 2, \ldots, n-1$.

Then any vector $z$ in the hyperplane defined by the $n$ points can be written as

$z=x^{(n)}+\sum_{i=1}^{n-1} \alpha_{i} y^{(i)}$

Using your favorite orthogonalization method (something better than Gram-Schmidt!) construct an orthonormal basis for the $y^{(i)}$ vectors,

$w^{(1)}, w^{(2)}, \ldots, w^{(n-1)}$

Now, any point $z$ in the hyperplane can be expressed as

$z=x^{(n)}+\sum_{i=1}^{n-1} \beta_{i} w^{(i)}$

The coordinate transformation $y^{(j)} \rightarrow \beta^{(j)}$ then gives you a set of $n-1$ vectors in $R^{n-1}$. Add the $0$ vector to this set to represent the base point $x^{(n)}$. Now, find an $n-1$ dimensional ellipsoid of minimum volume enclosing the $n$ points

$0, \beta^{(1)}, \beta^{(2)}, \ldots, \beta^{(n-1)}$.