Exact iterative computation of the robust multivariate minimum volume ellipsoid estimator

A widely used procedure for robust estimation of the scatter matrix of multivariate data is the 'minimum volume ellipsoid' or MVE estimator. This seeks to find the ellipsoid of minimum volume which covers at least half of the data. Not only is the MVE used in its own right, it is also the starting point for most other high breakdown estimators of multivariate location and scatter. To date however, no exact algorithm for computing the MVE has been defined. This deficiency makes the MVE method, and all other methods using the MVE as a starting point, irreproducible. This paper gives an exact algorithm for computing the MVE and uses this exact algorithm to evaluate the performance of the approximate algorithm currently used in most MVE implementations.