The C-Step Algorithm For The MCD

Why the MCD Uses a Concentration Step

The minimum covariance determinant (MCD) seeks a subset of a prescribed size whose covariance determinant is small. Searching every subset can be computationally demanding, so a useful algorithmic operation is to start from one subset, measure how far every observation lies from its fitted center and scatter, and keep the observations closest to that fit. This is the concentration step, or C-step.

A C-step is more than a convenient heuristic: under standard nonsingularity conditions, it cannot increase the determinant of the subset covariance. Repeated steps therefore give a controlled way to improve a candidate subset. They do not, by themselves, guarantee that the final subset is the globally optimal MCD subset; the algorithm can converge to a local solution.

Definition of the C-Step

Let \(x_1,\ldots,x_n\) be observations in \(\mathbb{R}^p\), and fix a subset size \(h\). For an index set \(H\) with \(|H|=h\), define its mean and its covariance with divisor \(h\) by

The MCD raw objective compares \(\det(C_H)\) across subsets of size \(h\). The divisor \(h\) is used consistently here; replacing it with another fixed divisor changes every subset determinant by the same factor and does not change which subset minimizes it.

For the determinant comparison and finite-termination result below, assume \(n\ge h\ge p+1\), and assume every subset of size \(h\) being considered has positive-definite covariance. This condition ensures both that the distances are defined at each step and that the updated determinant is positive. When a candidate subset is singular, the inverse-based step is not defined for that candidate; singular subsets must be handled separately rather than silently applying the result below.

Why the Updated Covariance Has Controlled Spread

The key calculation compares the new subset using the old subset’s distance scale. For any set \(G\) of \(h\) observations, let \(\bar{x}_G\) and \(C_G\) denote its mean and covariance. Expanding each observation around \(\bar{x}_H\) gives

To verify the identity, write \(x_i-\bar{x}_H=(x_i-\bar{x}_G)+(\bar{x}_G-\bar{x}_H)\). The two cross terms sum to zero because \(\sum_{i\in G}(x_i-\bar{x}_G)=0\). The remaining centered quadratic terms sum to \(h\operatorname{tr}(C_H^{-1}C_G)\), by the definition of \(C_G\) and the trace identity \(u^TAu=\operatorname{tr}(Auu^T)\).

For \(G=H\), the left side is \(p\): its value is \(\operatorname{tr}(C_H^{-1}C_H)=p\), and the mean-difference term is zero. Since \(H^+\) contains the \(h\) smallest distances among all observations, its total distance under the old fit cannot exceed the total for \(H\). Consequently,

The second term is nonnegative, so \(\operatorname{tr}(C_H^{-1}C_{H^+})\le p\). This trace bound is what leads to the determinant guarantee.

The C-Step Determinant Theorem

Proof. The matrix \(C_H^{-1/2}C_{H^+}C_H^{-1/2}\) is positive definite. Let its positive eigenvalues be \(\lambda_1,\ldots,\lambda_p\). Their sum is \(\operatorname{tr}(C_H^{-1}C_{H^+})\le p\), and their product is \(\det(C_{H^+})/\det(C_H)\). The arithmetic-geometric mean inequality therefore gives

Both determinants are positive, so multiplying by \(\det(C_H)\) proves the claim. \(\square\)

The argument also identifies the equality case. If the determinants are equal, the inequalities force every \(\lambda_j=1\), so \(C_{H^+}=C_H\). The earlier trace bound must also be an equality, which forces \(\bar{x}_{H^+}=\bar{x}_H\), since \(C_H^{-1}\) is positive definite. Thus equal determinant after a C-step entails equal subset mean and covariance, not merely an accidental equality of determinant values.

Finite Convergence and What It Guarantees

There are only finitely many subsets of size \(h\). For a rigorous termination statement, use a fixed deterministic rule to resolve ties at every step. If a step strictly lowers the determinant, that exact subset cannot recur later: every later determinant is no larger, whereas a return to that subset would restore its original determinant. If a step changes the subset but leaves the determinant equal, the equality case above shows that the mean and covariance are unchanged. The distances and tie rule are then unchanged as well, so the next C-step selects the same updated subset again. Hence the iteration reaches a fixed subset in finitely many steps.

This is a finite termination result, not a global optimality result. A fixed subset is one that is reproduced by its C-step; it need not minimize \(\det(C_G)\) over every size-\(h\) subset \(G\). In practice, multiple initial subsets can be used to reduce dependence on initialization, and the resulting candidates can be compared by determinant.

Common Pitfalls and Practical Meaning

• Claiming the global MCD has been found. A C-step gives a nonincreasing determinant and reaches a fixed subset under the stated conditions. It does not prove that no other subset has a smaller determinant.
• Using an inconsistent covariance convention. The proof and examples use divisor \(h\) for every subset covariance. A different fixed divisor can be used, but it must be applied consistently.
• Treating ties as irrelevant. Ties can make the next subset depend on the tie rule. A deterministic rule makes the iteration reproducible and supports the finite-termination argument.
• Assuming a singular subset has usable Mahalanobis distances. If its covariance is singular, its inverse does not exist. The C-step theorem as stated applies only when the covariances used in the iteration are positive definite.

The practical value of the C-step is that it turns a candidate subset into a subset more concentrated relative to its own location and scatter, while providing a mathematical guarantee on the raw determinant. That guarantee supports iterative search; careful initialization and comparison of candidate solutions remain necessary when the goal is a good approximation to the global MCD.