FAST-MCD, the C-step algorithm for the minimum covariance determinant

Rousseeuw, P. J. and Van Driessen, K. (1999), "A fast algorithm for the minimum covariance determinant estimator", Technometrics 41(3), 212-223. The algorithm and its key theorem were read from Hubert, Debruyne and Rousseeuw (2018), "Minimum Covariance Determinant and Extensions", arXiv:1709.07045, section "COMPUTATION", which restates them verbatim: take H1 of size h, put mu1 and S1 the empirical mean and covariance of the data in H1; if |S1| is not 0 define d1(i) = d(x_i, mu1, S1); take H2 to be the h observations with the smallest distances and compute mu2, S2 on H2; then |S2| <= |S1|, with equality if and only if mu2 = mu1 and S2 = S1.

Usage

Fastm(X, h = NULL, n_starts = 500L, max_iter = 100L, n_keep = 10L)

Arguments

X

n-by-p data matrix.

h

subset size; defaults to [(n + p + 1)/2].

n_starts

how many lexicographic elemental subsets to start from.

max_iter

cap on the C-steps for each retained subset.

n_keep

how many best subsets to iterate to convergence; the paper uses 10.

Value

list: estimate, center, cov_raw, cov, factor, subset, dets, n_starts_used, h, n, p, method.

Details

That is the C-step, C for concentration. The determinant never increases along the iteration, which is what makes it terminate, and that monotonicity is asserted directly as an anchor rather than taken on trust.

The published schedule, same section: apply only TWO C-steps to each initial subset, keep the ten with the lowest determinants, and iterate only those to convergence. Initial subsets are grown from elemental (p+1)-subsets.

DETERMINISM. The paper draws its elemental subsets at random. This implementation enumerates them in lexicographic order and takes the first n_starts, so both language arms visit the same candidates in the same sequence and return the same numbers, not merely numbers of equal quality.

Examples

# \donttest{
set.seed(1)
X <- cbind(rnorm(40), rnorm(40))
X[1:4, ] <- X[1:4, ] + 8   # four outliers
Fastm(X)$estimate
#> [1] 0.05523981
# }