Definition
The Minimum Covariance Determinant (MCD) estimator looks for the out of points whose sample covariance has the smallest determinant, and reports their mean and (rescaled) covariance as the location and scatter of the data. Because it only ever uses the most concentrated half of the points, up to roughly half of the data can be arbitrarily bad without dragging the estimate away.
At a glance
- Task
- Robust estimation of location and scatter ; the basis of outlier detection with Mahalanobis distances
- Input → output
- data → , , and a robust distance for every point
- Objective
- — the tightest -point ellipsoid
- Algorithm
- FAST-MCD: random starts + C-steps (each step never increases the determinant), then consistency correction and reweighting
- Breakdown point
- up to , versus for the sample mean and covariance
- Hyperparameter
- (scikit-learn:
support_fraction); default - Equivariance
- affine equivariant: rescaling, rotating or shifting the features transforms the estimate the same way — no standardization needed
- Assumes
- the bulk is roughly elliptical (Gaussian-like), or so, and the data are not concentrated on a lower-dimensional subspace
The problem: outliers hide themselves
The standard way to find multivariate outliers is the Mahalanobis distance: fit a mean and covariance, then measure how many "standard deviations" each point is from the centre, in the shape of the data. Under a Gaussian model the squared distance follows a distribution, so anything above, say, its 97.5% quantile is suspicious.
- estimated mean vector and covariance matrix
- chi-square distribution with degrees of freedom ( = number of features)
- for (its CDF is , so the quantile is )
The catch is circular: and are estimated from the same data that contains the outliers. A small group of outliers pulls the mean toward itself and stretches the covariance in its own direction. The ellipse grows to swallow them, their distances shrink, and they stop looking unusual. This is called masking. Its mirror image, swamping, is when the distorted ellipse pushes perfectly ordinary points outside the cutoff.
The MCD estimator
Rousseeuw's idea (1984): instead of fitting all points, find the subset of points that is most tightly concentrated and fit only those. "Tight" is measured by the determinant of the subset's covariance, which is proportional to the squared volume of its tolerance ellipsoid.
- a subset of point indices (the "support")
- generalized variance of the subset; the ellipsoid has volume
- the raw MCD location and scatter: plain mean and covariance of the chosen subset
- subset size; this choice maximizes the breakdown point
- finite-sample breakdown point: the smallest fraction of points that, replaced by arbitrary values, can make the estimate useless
- contaminating this many points forces at least one into every h-subset
- a subset needs more than p good points to keep a non-degenerate covariance
Why does it resist outliers? As long as fewer than points are bad, there exists an -subset made only of good points, and any subset that includes far-away points has a much larger determinant — so the minimizer avoids them. For our example (, ): and . Five arbitrary outliers can't break it; the sample covariance is broken by one.
| h | Breakdown point | Efficiency on clean Gaussian data | When |
|---|---|---|---|
| ≈ 50% (maximum) | lowest: uses only half the points | contamination unknown, could be large | |
| ≈ 25% | noticeably better | you know contamination is modest | |
| (none) | best (it is the classical estimate) | no outliers — then why bother? |
The C-step: a descent move on subsets
There are subsets — 792 for our toy problem, astronomically many for real data — so exhaustive search is out. The key tool is the concentration step (C-step) of Rousseeuw & Van Driessen (1999): given any -subset, compute its mean and covariance, measure every point's distance under that fit, and take the closest points as the new subset.
- current subset, with mean and covariance
- squared Mahalanobis distance of every point (all n, not just the subset) under the current fit
Proof sketch
- 1Old points average to . For any set, . Because takes the smallest , .
- 2Re-centring only helps. The mean minimizes the sum of any quadratic form over , so measuring around instead of can only lower it: .
- 3AM–GM on eigenvalues. Let be the eigenvalues of . Then .
- 4Conclude. . Equality needs every , i.e. .
The C-step is to MCD what the assign/update loop is to k-means: a monotone descent that is guaranteed to stop, but only at a local minimum. Where it ends depends on where it starts.
FAST-MCD
FAST-MCD (Rousseeuw & Van Driessen, 1999)
- 1Many cheap starts. Draw a random -subset (the smallest set with a non-singular covariance; enlarge it if its determinant is 0). Fit and take the closest points as . Small starts matter: a random -subset almost surely contains outliers when contamination is high, but a 3-point start is often clean.
- 2Two C-steps each, then keep only the ~10 subsets with the lowest determinant.
- 3Iterate the survivors to convergence and keep the overall winner: the raw MCD .
- 4Large n: split the data into disjoint groups of ~300, run the above inside each group, pool the best candidates on a merged sample of ~1500, then finish on the full data. Cost is roughly linear in .
- 5Correct and reweight (next section).
Consistency correction and reweighting
The raw MCD covariance is too small. By construction it is computed from the most central points, so it estimates the covariance of a truncated Gaussian. Two fixes follow.
- consistency factor: makes the estimate unbiased for Σ when the data really are Gaussian
- the quantile of : the squared radius that contains a fraction of a Gaussian
- arises because for
- median of ; for . scikit-learn uses this median rule
The median rule asks: after rescaling, does the median point have the median distance a Gaussian would give it? It is robust (the median ignores outliers), adapts to finite samples, and is what scikit-learn uses. The asymptotic formula (Croux & Haesbroeck, 1999) is what R's robustbase uses, together with an extra small-sample factor.
- hard weight: 1 if the point looks regular under the corrected MCD, 0 if it is flagged
- reweighted (final) estimates: ordinary mean and covariance of every non-flagged point
Reweighting recovers efficiency. The raw MCD threw away points even if they were perfectly good; reweighting brings back every point that the robust fit says is regular, keeping the high breakdown point while using far more data. The final robust distances are then compared with the same cutoff. (Strictly, the reweighted covariance should also be inflated slightly, since it is fitted to points inside a 97.5% ellipse; scikit-learn skips this, R applies it.)
Worked example: 12 points, 3 outliers
Nine points rise from lower-left to upper-right (correlation ). Three outliers sit together at the lower right. , , so and the cutoff is .
| Point | x₁ | x₂ | Point | x₁ | x₂ |
|---|---|---|---|---|---|
| P1 | 0.5 | 2 | P7 | 4 | 5 |
| P2 | 2 | 1 | P8 | 4.5 | 4 |
| P3 | 2 | 3 | P9 | 5 | 5 |
| P4 | 2.5 | 2 | P10 | 8 | 1 |
| P5 | 3 | 4.5 | P11 | 9 | 2 |
| P6 | 4.5 | 3.5 | P12 | 9 | 0 |
Classical fit. All 12 points give and , . Three outliers have flipped the sign of the correlation, from to . The largest classical is P12's , well under : no point is flagged. P1, an ordinary inlier, has a larger distance () than outlier P10 ().
| Step | Subset H (7 points) | Outliers in H | μ_H | Σ_H (σ₁₁, σ₁₂, σ₂₂) | det Σ_H |
|---|---|---|---|---|---|
| H₀ (start J) | P2, P5, P12 | 1 | (4.67, 1.83) | (9.56, −3.39, 3.72) | 24.08 |
| H₁ | P2, P3, P4, P6, P8, P10, P12 | 2 | (4.64, 2.07) | (6.98, −1.80, 1.89) | 9.95 |
| H₂ | P2, P3, P4, P5, P6, P8, P10 | 1 | (3.79, 2.71) | (3.92, −0.53, 1.70) | 6.40 |
| H₃ | P2, P3, P4, P5, P6, P7, P8 | 0 | (3.21, 3.29) | (1.06, 0.90, 1.70) | 0.99 |
| H₄ | P3, P4, P5, P6, P7, P8, P9 | 0 | (3.64, 3.86) | (1.12, 0.70, 1.05) | 0.691 |
| H₅ | = H₄ → converged | 0.691 |
Check the theorem on step : under the fit, the seven points chosen for have ; then and . The outliers leave one at a time. Once the subset is clean, the ellipse snaps onto the inlier cloud, and the outliers' jump from single digits to 65–104.
| Step | Subset H | Outliers in H | μ_H | det Σ_H |
|---|---|---|---|---|
| H₀ (start J) | P2, P8, P11 | 1 | (5.17, 2.33) | 12.68 |
| H₁ | P2, P3, P4, P6, P8, P10, P11 | 2 | (4.64, 2.36) | 8.03 |
| H₂ | P1, P3, P4, P6, P8, P10, P11 | 2 | (4.43, 2.50) | 7.11 |
| H₃ | = H₂ → converged (local minimum) | 7.11 |
This is why FAST-MCD uses many starts: , so start A wins. Brute force over all subsets confirms with is the global MCD. Its raw covariance is .
Correction and reweighting
- 1Raw distances under : inliers – (P1 = 8.82 and P2 = 7.87 are outside the subset and look extreme because the raw ellipse is too small), outliers .
- 2Consistency factor (median rule): the median of the 12 raw is , so . (The asymptotic formula would give .) Corrected distances: P1 , P2 ; outliers .
- 3Weights: the 9 inliers are under , the 3 outliers are over it.
- 4Reweighted fit on the 9 inliers: , , correlation , (the classical one was , so the 97.5% ellipse is smaller in area).
| Point | Classical d² | Robust d² (final) | Flag (robust) |
|---|---|---|---|
| P1 | 3.14 | 3.81 | |
| P2 | 2.97 | 3.56 | |
| P3 | 0.87 | 0.90 | |
| P4 | 1.09 | 1.19 | |
| P5 | 1.25 | 1.96 | |
| P6 | 0.24 | 1.85 | |
| P7 | 2.05 | 1.72 | |
| P8 | 0.68 | 1.11 | |
| P9 | 2.41 | 1.91 | |
| P10 | 2.20 | 55.16 | outlier |
| P11 | 2.76 | 56.59 | outlier |
| P12 | 4.35 | 89.64 | outlier |
- 1classical: μ, Σ ← mean, cov of all n
- 2for each random start J, |J| = p+1:
- 3 μ, Σ ← mean, cov of J
- 4 repeat: dᵢ² ← (xᵢ−μ)ᵀ Σ⁻¹ (xᵢ−μ)
- 5 H ← the h points with smallest dᵢ²
- 6 μ, Σ ← mean, cov of H # det ↓
- 7 until H stops changing
- 8keep the H with the smallest det Σ
- 9Σ ← Σ · median(d²) / χ²₂(0.5)
- 10w ← [d² ≤ χ²₂(0.975)]; refit on w
Classical fit on all 12 points. The 3 outliers drag the mean to (4.50, 2.75) and tilt the ellipse: correlation -0.31 although the bulk rises at +0.75. Largest d² is P12's 4.35 < 7.38, so nothing is flagged — masking.
In code
1import numpy as np2from scipy.stats import chi234X = np.array([[0.5, 2], [2, 1], [2, 3], [2.5, 2], [3, 4.5], [4.5, 3.5], [4, 5],5 [4.5, 4], [5, 5], [8, 1], [9, 2], [9, 0]])6n, p = X.shape7h = (n + p + 1) // 2 # 789def fit(S):10 mu = X[S].mean(axis=0)11 cov = np.cov(X[S].T, bias=True) # divide by |S|, like sklearn12 return mu, cov1314def mahal2(mu, cov):15 D = X - mu16 return np.einsum("ij,jk,ik->i", D, np.linalg.inv(cov), D)1718def c_steps(start, max_iter=100):19 S = np.sort(start)20 mu, cov = fit(S)21 history = [(S, np.linalg.det(cov))]22 for _ in range(max_iter):23 d2 = mahal2(mu, cov)24 S_new = np.sort(np.argsort(d2, kind="stable")[:h]) # h closest points25 if np.array_equal(S_new, S):26 break # fixed point27 S = S_new28 mu, cov = fit(S)29 history.append((S, np.linalg.det(cov))) # det never increases30 return S, mu, cov, history3132def fast_mcd(n_starts=200, seed=0):33 rs = np.random.default_rng(seed)34 best = None35 for _ in range(n_starts):36 J = rs.choice(n, size=p + 1, replace=False)37 if np.linalg.det(fit(J)[1]) < 1e-12:38 continue # collinear start39 S, mu, cov, _ = c_steps(J)40 if best is None or np.linalg.det(cov) < np.linalg.det(best[2]):41 best = (S, mu, cov)42 S, mu, cov = best43 # consistency correction (sklearn's empirical median rule)44 cov = cov * np.median(mahal2(mu, cov)) / chi2.ppf(0.5, p)45 # reweighting at the 97.5% chi-square quantile46 keep = mahal2(mu, cov) <= chi2.ppf(0.975, p)47 mu, cov = fit(np.where(keep)[0])48 return mu, cov, mahal2(mu, cov), S4950for S, d in c_steps([1, 4, 11])[3]: # start A = {P2, P5, P12}51 print(S + 1, round(d, 4)) # dets 24.08, 9.95, 6.40, 0.99, 0.6915253mu, cov, d2, S = fast_mcd()54print("raw subset", S + 1) # [3 4 5 6 7 8 9]55print("mu", mu.round(3)) # [3.111 3.333]56print("robust d2", d2.round(2)) # ... 55.16 56.59 89.641import numpy as np2from scipy.stats import chi23from sklearn.covariance import EmpiricalCovariance, MinCovDet45X = np.array([[0.5, 2], [2, 1], [2, 3], [2.5, 2], [3, 4.5], [4.5, 3.5], [4, 5],6 [4.5, 4], [5, 5], [8, 1], [9, 2], [9, 0]])78classical = EmpiricalCovariance().fit(X)9mcd = MinCovDet(support_fraction=7 / 12, random_state=0).fit(X)1011print("raw support:", np.where(mcd.raw_support_)[0] + 1) # [3 4 5 6 7 8 9]12print("raw location:", mcd.raw_location_.round(3)) # [3.643 3.857] (uncorrected)13print("final location:", mcd.location_.round(3)) # [3.111 3.333] (reweighted)14print("final covariance:\n", mcd.covariance_.round(3)) # [[1.988 1.435] [1.435 1.833]]1516cut = chi2.ppf(0.975, df=X.shape[1]) # 7.3817d2_classical = classical.mahalanobis(X) # squared distances18d2_robust = mcd.mahalanobis(X) # == mcd.dist_19print("classical flags:", np.where(d2_classical > cut)[0] + 1) # []20print("robust flags: ", np.where(d2_robust > cut)[0] + 1) # [10 11 12]Use when
- +The bulk of the data is roughly elliptical and you suspect contamination you can't describe in advance — MCD tolerates up to ~50% of it.
- +Outliers may come in groups (a faulty sensor batch, a fraud ring): the masking that defeats classical distances is exactly what MCD handles.
- +You need robust inputs for other methods: robust PCA, robust regression diagnostics, robust correlation matrices.
- +Features are on different scales or correlated: MCD is affine equivariant, so no standardization is needed and correlations are respected.
Avoid when
- −Dimension is high: you need and in practice ; FAST-MCD gets slow and unstable as grows past a few dozen. Use regularized variants (MRCD) or robust PCA first.
- −The regular data are multimodal or curved (clusters, manifolds): a single ellipse is the wrong shape. Use LOF, Isolation Forest or a mixture model.
- −Data are discrete or heavily tied: many h-subsets become singular (det = 0) and the minimum is meaningless.
- −You need maximum efficiency on clean data: the raw MCD wastes almost half the sample (reweighting recovers much, not all).
Where it's used
Multivariate outlier detection
Robust Mahalanobis distances with a χ² cutoff in quality control, sensor monitoring and fraud screening; the engine of Elliptic Envelope.
Finance
Robust covariance matrices for portfolio risk, less distorted by crash days and data errors.
Chemometrics & spectroscopy
Robust PCA (ROBPCA) and robust calibration, where a few bad samples otherwise dominate the components.
Regression diagnostics
Distance–distance and robust leverage plots separate good leverage points from bad ones (MCD on the predictors).
Check yourself
Why did the classical Mahalanobis distance fail to flag P10–P12 in the worked example?
Check yourself
With n = 12, p = 2 and h = 7, what is the MCD's finite-sample breakdown point?
Check yourself
A C-step replaces subset H₁ by the 7 points closest under H₁'s fit. What can you guarantee about H₂?
Check yourself
Why is the raw MCD covariance multiplied by a consistency factor c > 1?
Remember
- ✓Classical mean and covariance have a breakdown point of 1/n: a cluster of outliers inflates the ellipse and masks itself.
- ✓MCD fits the points with the smallest covariance determinant, giving a breakdown point close to 50%.
- ✓The C-step (refit, then keep the closest points) never increases . Proof: trace , then AM–GM. It converges to a local minimum, so FAST-MCD uses many random starts.
- ✓Raw MCD is too small: rescale it by a consistency factor (median rule: ), then reweight with the points under to regain efficiency.
- ✓Robust distances vs the cutoff expose outliers the classical distance hides. Compare the two in a distance–distance plot.
- ✓Use it for elliptical, moderate-dimensional data. For high , multimodal or curved data, reach for regularized MCD, robust PCA, or non-parametric detectors.