7
$\begingroup$

As far as I understand,

  • the Minimum Covariance Determinant (MCD) estimator looks for the subset of h data points whose covariance matrix has the smallest determinant.
  • the Minimum Volume Ellipsoid (MVE) searches for the ellipsoid with the smallest volume that covers h data points.

Once either subset is found, the robust estimate of the covariance matrix is given by that of those h points.

Can you explain me the conceptual difference between the MCD and MVE? Isn't the determinant related to the volume?

EDIT

User603 have argued that both estimators are solutions to different optimisation problems. Even if I do not understand everything in its answer, I do trust him. But then, what about this formula for the volume of the ellipsoid $(x-v)'A^{-1}(x-v)=1$ $$V = \frac{4}{3}\pi\sqrt{\det(A)}$$ according to which minimising V is equivalent to minimising $\det(A)$...

$\endgroup$
  • $\begingroup$ yes, for an ellipsoid! (see the last paragraph in my comment, about the strong relation between both problems in the case of symmetrically distributed $x$'s). Also, you really don't need to trust user603 -- it's quiet well spelled out in the linked paper. $\endgroup$ – user603 Jan 29 '12 at 16:04
  • $\begingroup$ do you mean that in the multinormal case, both estimators are equivalent? $\endgroup$ – user7064 Jan 29 '12 at 16:06
  • $\begingroup$ no:> even in multi-dimension, they are solution to different (but related) problems. Both belong to the class of minimum-volume estimators (together with the S and $\tau$ estimators). $\endgroup$ – user603 Jan 29 '12 at 17:41
  • $\begingroup$ What is the purpose of MCD and MVE? $\endgroup$ – Ben Aug 8 '19 at 7:40
5
$\begingroup$

First off, it is easier to start by answering your question in the uni variate case because then both estimators have an explicit solution as a function of the series of sorted observations $x_{(1)}\leq x_{(2)}\leq,...,x_{(n-1)}\leq x_{(n)}$.

The uni-variate version of the MVE is also known as the short estimator and is the solution to

$\underset{1\leq i\leq(n-h+1)}{\arg.\min.}\;\;\;x_{(i+h-1)}-x_{(i)}\;\;\;[1]$

The uni-variate version of the MCD is also known as the truncated likelihood estimator and is the solution to:

$\underset{1\leq i\leq(n-h+1)}{\arg.\min.}\;\;\;\displaystyle\frac{1}{h}\displaystyle\sum_{j=1}^{i+h-1}x_{(j)}^2-\left(\frac{1}{h}\displaystyle\sum_{j=1}^{i+h-1}x_{(j)}\right)^2\;\;\;[2]$

Now, for symmetrical distribution, the functional corresponding to $[2]$ is proportional to that corresponding to $[1]$ (the likelihood of elliptical distribution computed over the $h$ most central observations).

You will find more details on this in this very clear paper:

  • Maxbias Curves of Robust Location Estimators based on Subranges, Croux and Haesbroeck, Metrika, 2001

So these estimators are solutions to different problems, with the definitions above it is easy to show that the solution to equation [1] does in general not equal the solution to equation [2]. 

Turning to the multivariate setting now (when $p$, the number of variables is greater than 1), the MVE looks for an ellipse through $p+1$ data points that contains $h$ data points, with smallest volume (this is just the multivariate generalization to elliptical distributions of the range for uni-modal distribution on the line). The MCD looks for the ellipse that contains $h$ data points and that has the smallest volume. By analogy to the univariate setting, in the case of the MCD, the ellipse does not in general pass through $p+1$ data points (just as the mean does not in general correspond to any observed value in the sample).

Note that these are for the estimators (to which the O.P. specifically refers), not about the differences between the respective algorithms (FastMVE and FastMCD).

$\endgroup$
  • $\begingroup$ Thanks for your answer. I do not get everything yet... mainly because I do not manage to make the link between my definitions and yours. Moreover, I thought that minimising the volume of the ellipsoid was equivalent to minimising the determiant... $\endgroup$ – user7064 Jan 29 '12 at 15:20
  • $\begingroup$ for the mcd: for a scalar $a$, $\det(a)=a$, so you could add a $\det$. These are not 'my' definitions btw. Where did you get 'your' definition from? Check out the linked the paper also (it avail. online ungated), it compares both estimators in greater lengths. $\endgroup$ – user603 Jan 29 '12 at 15:41
  • $\begingroup$ it would make things easier if you could explain what part(s) you didn't get. $\endgroup$ – user603 Jan 30 '12 at 1:06
2
$\begingroup$

Setting: We are given points $\{x_i\}_{i = 1}^n$ each lying in $\mathbb{R}^p$. We set $h$ to be a number between $n/2$ and $n$, exclusive.

MVE: The MVE seeks an ellipsoid of minimal volume with two constraints-- (1) That the ellipsoid must contain $h$ points in its interior union its boundary, and (2) the ellipsoid must contain at least $p+1$ points on its boundary.

MCD: The MCD is mathematically equivalent to finding an ellipsoid of minimal volume with only one constraint, namely, That the ellipsoid must contain $h$ points in its interior unions its boundary.

These are indeed different problems, that is, not mathematically equivalent, as given by the example in @user603's answer.

To see the equivalence of the MCD with finding the ellipsoid with minimal volume that covers at least $h$ of the given $n$ points, first note that we can denote an ellipsoid as $E = \{x: (x-c)^t Q (x-c) \leq 1\}$ where $c$ is the center point, and $Q$ a positive definite matrix. Next, the vol$(E) = a \det(Q)^{-.5} = a \det(Q^{-1})^{.5} $ for some constant $a$ (e.g., see this paper). So minimizing the volume of $E$ corresponds to minimizing the determinant of $\Sigma: = Q^{-1}$, which is the covariance matrix of the Gaussian described by that ellipsoid.

For details of this calculation: write $Q = UDU^*$ for unitary $U$ and diagonal with positive entries $D$. We can see that $UD^{.5}U^*$ indeed equals $Q^{.5}$. Further, since $Q$ is positive definite $Q^{.5}$ is invertible. It follows that $\det(Q)^{-.5} = \det(Q^{-1})^{.5}$. Setting $\Sigma = Q^{-1}$, and $\mu = c $ (the center of the ellipsoid, we can see that the ellipsoid $E$ is the one characterized by the Gaussian with mean $\mu$ and covariance $\Sigma$. Lastly, the vol$(E) = a*\det(\Sigma)^{.5}$

$\endgroup$
  • 1
    $\begingroup$ Welcome to the site, travelingbones. Please do not try to contact another user in your answers. Eg, @user603 will not have been notified of your answer. You will be able to comment anywhere when your reputation is >50. Since you're new here, why not take our tour, which has information for new users? $\endgroup$ – gung - Reinstate Monica Jan 20 '16 at 1:00

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.