Given three vectors in $\mathbb{R}^{512}$, my task is to compute a Minimum Volume Enclosing Ellipsoid (MVEE). I have tried Kachiyan's algorithm, but it requires at least as many vectors as there are dimensions, which I do not have at my disposal (attempts to create synthetic vectors resulted in useless ellipsoids).

Thus far, the most accurate and useful method I have found is to formulate the problem as a semidefinite program.

$$\min\; -\operatorname{logdet}(A) \\ \text{s.t. } A \geq 0 \\ (x_{i} - c)^{T}A(x_{i} - c) \leq 1$$

In the above formulation, $c$ is the specified center of the ellipsoid, $A\geq 0$ is the positive semi-definiteness constraint, and $x_{i}$ is the $i$th vector in $\mathbb{R}^{512}$.

This method works very well but is too slow for my application (10+ seconds using SCS with very few iterations, all other SDP methods I've tried are glacial by comparison). Is there a faster method for finding an MVEE for a small number of points in a high number of dimensions? I understand that said MVEE will not be unique due to the small number of points, as long as the volume is minimal or close to minimal and the points are enclosed).

  • $\begingroup$ By vector do you mean point in $\mathbb{R}^{512}$ or oriented lines? $\endgroup$ – nicoguaro Feb 14 '20 at 3:05
  • $\begingroup$ A point in $\mathbb{R}^{512}$. $\endgroup$ – nick.schachter Feb 14 '20 at 14:11
  • $\begingroup$ I think that you can use the circumcircle as an upper bound, can't you? $\endgroup$ – nicoguaro Feb 14 '20 at 14:15
  • $\begingroup$ I could, but the bound seems too loose - I'm using the hyperellipsoid as an estimate of a separating space for classification (which works very well when I calculate the hyperellipsoid via SDP). $\endgroup$ – nick.schachter Feb 14 '20 at 14:28
  • 1
    $\begingroup$ As the dimension grows the volume of the space goes to $0$. Thus I do not get why exactly you are trying to have a volume based solution to your problem. Maybe if you can elaborate a little on the application people could come up with better solutions. $\endgroup$ – Tolga Birdal Feb 16 '20 at 1:53

You don't need SDP for an easy task like this. $X$ are your points. Do a PCA on $Y Y', Y = X - \operatorname{mean}(X)$, reduce dimension to 2-dimensions (others dimensions are zeros). 3 points on the canonical plane, axis of ellipse are 1st and 2nd Principal Components.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.