The Open UniversitySkip to content

RelaxMCD: Smooth optimisation for the Minimum Covariance Determinant estimator

Critchley, F.; Schyns , M. and Haesbroeck, G. (2010). RelaxMCD: Smooth optimisation for the Minimum Covariance Determinant estimator. Computational Statistics and Data Analysis, 54(4) pp. 843–857.

DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


The Minimum Covariance Determinant (MCD) estimator is a highly robust procedure for estimating the centre and shape of a high dimensional data set. It consists of determining a subsample of h points out of n which minimises the generalised variance. By definition, the computation of this estimator gives rise to a combinatorial optimisation problem, for which several approximate algorithms have been developed. Some of these approximations are quite powerful, but they do not take advantage of any smoothness in the objective function. Recently, in a general framework, an approach transforming any discrete and high dimensional combinatorial problem of this type into a continuous and low-dimensional one has been developed and a general algorithm to solve the transformed problem has been designed. The idea is to build on that general algorithm in order to take into account particular features of the MCD methodology. More specifically, two main goals are considered: (a) adaptation of the algorithm to the specific MCD target function and (b) comparison of this ‘tuned’ algorithm with the usual competitors for computing MCD. The adaptation focuses on the design of ‘clever’ starting points in order to systematically investigate the search domain. Accordingly, a new and surprisingly efficient procedure based on a suitably equivariant modification of the well-known k-means algorithm is constructed. The adapted algorithm, called RelaxMCD, is then compared by means of simulations with FASTMCD and the Feasible Subset Algorithm, both benchmark algorithms for computing MCD. As a by-product, it is shown that RelaxMCD is a general technique encompassing the two others, yielding insight into their overall good performance.

Item Type: Journal Item
Copyright Holders: 2010 Elsevier
ISSN: 0167-9473
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 26086
Depositing User: Frank Critchley
Date Deposited: 08 Jan 2011 11:57
Last Modified: 04 Oct 2016 10:54
Share this page:


Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU