# Comparison of Stahel-Donoho and Minimum Covariance Determinant estimation

I am interested in detecting multivariate outliers in a low dimensional data set ($n>p$). Various high-breakdown robust methods for multivariate settings such as Stahel-Donoho and Minimum Covariance Determinant estimation is proposed in the literature. Can you give an advice and make a comparison than which estimator should be used and why?

I have just found out that, due to computationally intensive calculation of Stahel-Donoho, the MCD estimation is preferable. How can I realize the intensity of calculation? Is there other reason for the superiority of MCD?

## 1 Answer

Both algorithms have high quality implementations in a common environment so we can actually compare their running times. Check the CovSde and CovMcd functions in rrcov.

[Both algorithms have an argument nsamp which plays a similar role for both and impacts their computing times in a comparable way. Nevertheless, in the rrcov package the nsamp argument has different default values for the two algorithms, so in order for these comparisons to be fair, you'll need to make sure you are using the same values of nsamp when running both of them by setting it manually.]

To answer your question proper. Fixing the nsamp parameter to the same value, the running times of both algorithms now only depends on the size of the input matrix $\pmb X$. Denote $n$ ($p$) the numbers of rows (columns) of $\pmb X$.

The numerical complexity (and running times) of both algorithms scales roughly the same way as a function of $p$ (so the number of variables is not the culprit).

However, for large values of $n$, the running times of FastMCD scales less than linearly with $n$. This is due to the so called nested sub-sampling algorithm included in the FastMCD (section 3.3 of [0]) --CovSde has no comparable nested sub-sampling scheme.

The actual value at which the nested sub-sampling algorithm kicks in is set by the user but the default value is $n=600$. For large values of $n$, the nested sub-sampling algorithm can lead to substantial computational savings for FMCD.

You can see the effect of the nested sub-sampling algorithm by comparing the running times of both algorithms for $n<600$ (when neither uses nested sub-sampling):

library(rrcov)

n <- 600
p <- 8

nsamp <- 1000
x <- matrix(rnorm(n * p), nc = p)
system.time(CovMcd(x, nsamp = nsamp))
user  system elapsed
0.116   0.000   0.114
system.time(CovSde(x, nsamp = nsamp))
user  system elapsed
0.084   0.000   0.082


to their relative running times when $n>600$ and FastMCD's nested sub-sampling scheme kicks in:

n <- 6000
p <- 8

nsamp <- 1000
x <- matrix(rnorm(n * p), nc = p)
system.time(CovMcd(x, nsamp = nsamp))
user  system elapsed
0.160   0.016   0.170
system.time(CovSde(x, nsamp = nsamp))
user  system elapsed
1.188   0.012   1.197

• [0]: P. J. Rousseeuw and K. van Driessen (1999) A fast algorithm for the minimum covariance determinant estimator. Technometrics 41, 212--223.
• Thank you for the explanation. but is it possible to provide more clarification on this part It is however true that for large values of n, the running times of FastMCD scales less than linearly with n – user2802663 Jul 17 '16 at 13:21
• Which output of system.time function can be used as a comparison criteria? use, system or elapsed? – user2802663 Jul 17 '16 at 13:24
• See here. I'll pass by latter to add more clarification on that part. – user603 Jul 17 '16 at 13:59