A Deterministic Algorithm for Robust Location and Scatter

Most algorithms for highly robust estimators of multivariate location and scatter start by drawing a large number of random subsets. For instance, the FASTMCD algorithm of Rousseeuw and Van Driessen starts in this way, and then takes so-called concentration steps to obtain a more accurate approximation to the MCD. The FASTMCD algorithm is affine equivariant but not permutation invariant. In this article, we present a deterministic algorithm, denoted as DetMCD, which does not use random subsets and is even faster. It computes a small number of deterministic initial estimators, followed by concentration steps. DetMCD is permutation invariant and very close to affine equivariant. We compare it to FASTMCD and to the OGK estimator of Maronna and Zamar. We also illustrate it on real and simulated datasets, with applications involving principal component analysis, classification, and time series analysis. Supplemental material (Matlab code of the DetMCD algorithm and the datasets) is available online.