Minimum Volume Enclosing Ellipsoid

Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space.

Description

[A , c] = MinVolEllipse(P, tolerance)

Finds the minimum volume enclosing ellipsoid (MVEE) of a set of data points stored in matrix P. The following optimization problem is solved:

minimize log(det(A))
s.t. (P_i - c)'*A*(P_i - c)<= 1
         
in variables A and c, where P_i is the i-th column of the matrix P.
The solver is based on Khachiyan Algorithm, and the final solution is different from the optimal value by the pre-specified amount of 'tolerance'.
---------------------------
Outputs:

c : D-dimensional vector containing the center of the ellipsoid.

A : This matrix contains all the information regarding the shape of the ellipsoid. To get the radii and orientation of the ellipsoid take the Singular Value Decomposition ( svd function in matlab) of the output matrix A:
 
[U Q V] = svd(A);

the radii are given by:

r1 = 1/sqrt(Q(1,1));
r2 = 1/sqrt(Q(2,2));
...
rD = 1/sqrt(Q(D,D));

and matrix V is the rotation matrix that gives you the orientation of the ellipsoid.

For plotting in 2D or 3D, use MinVolEllipse_plot.m (see the link bellow)

• Acknowledgements: This submission has inspired the following:; Plot an ellipse in "center form", Approximate Lowner Ellipsoid
• MATLAB release: MATLAB 6.5 (R13)

[John D'Errico]

This could be useful IF you have small sets of data.

I tested this for several problems, in 1, 2 and 5 dimensions. All seemed to work. The only downside is data of even moderate size. The author gives an example with 100 points, solved fairly quickly. But expand that to only 500 points (in 2-d) and it takes 140 seconds to run on my computer.

[nima moshtagh]

For tolerance=0.01 in 2D here is how long it takes (approximatly) to find the covering ellipse on a 2.4GHz computer:

#point time(sec)
------ --------
100 0.03
500 1.24
1000 5.20
1500 13.26
2000 25.27

[Carl Miller]

Excellent stuff! This was exactly what I was looking for and works quite well. Although the math behind it all was a bit beyond me, the author was more than helpful in helping me make the most of what the code has to offer, thanks again Nima!

[M Doug k Vandenberg]

This is a very good program for doing minimum volume ellipsoids. it has been very helpful and the author has as well.

[Iram Weinstein]

I find that the run time can be radically improved by recognizing that the only points that determine the bounding ellipsoid are on the convex hull, as used by John D'Errico in his minboundsphere. Given points P, the following code finds the reduced set of points lying on the hull.

K=convhulln(P.');
K=unique(K(:));
Q=P(:,K);

for P=randn(3,500)
my computer runs MinVolEllipse(P, .001) in 12.54 seconds

and finds Q followed by MinVolEllipse(Q, .001) in 0.08 seconds

[Ondrej Danko]

"Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space"...

I would expect that resulting ellipsoid COVERS all points, I mean no points are outside of the resulting ellipsoid...

I had ran a small test if it is so... and surprisingly not all points are necessarily inside.

P = rand(3,N);
[A , C] = MinVolEllipse(P, t);
for j = 1:N
   if ((P(:,j)-C)'*A*(P(:,j)-C) > 1)
      disp('Point is outside...');
   end
end

I am missing something, or it is expected? If expected, any suggestions to modify the algorithm to output ellipsoid strictly covering all points?

[nima moshtagh]

Dear Ondrej Danko,
Thank you for bringing this point to my attention. The outcome that a number of points fall outside of the ellipsoid is expected, because we are truncating the algorithm before reaching its optimal value. The amount of error that we will get by doing this, is of the order of parameter 'tolerance', which represents the amount of error you can tolerate in the final result. For example for t=0.001 the average distance of an outside point is of the order of 10^-3.

[Santanu Ghorai]

Very good program. It has helped me a lot to do with the matlab. Thanks to Nima Moshtagh for submitting the code.

[Lien Kuqn Hua]

THank you

[Avinash Uppuluri]

Hello Nima Moshtagh, The code posted was very useful. Is there a way to add a weight to the points, giving the importance of each point to be included within the ellipse. (Instead of using the tolerance which excludes points through the periphery). With the idea that points that are of less significance need not be included in the ellipse. Where can I include such a weighing parameter. I can probably do it in the pre-processing stage but is there a way to include it within your code. Thanks!

[Avinash Uppuluri]

Can you also provide a good journal reference for this algorithm. Thanks!

[Nima Moshtagh]

Here is a paper describing the algorithm and math behind the code: http://www.seas.upenn.edu/~nima/papers/Mim_vol_ellipse.pdf
 

[Rashed]

Thanks a lot. I was looking for something like this.

[Rashed]

Hi,

I have a problem in 3D. Say, I have an 3D array of P(5,5,5) and how can I make this to work? Please suggest. Or, do I need to produce a matrix P containing the coordinates of the region?