S-Estimators For High-Breakdown Scatter

Why Minimize a Robust Scale?

A classical scatter estimate can be driven by a single observation placed far from the rest: its squared distance keeps growing as the observation moves away. A robust scatter method should instead allow an extreme point to have limited influence on the criterion. S-estimation does this by choosing location and scatter to make a robust measure of radial spread as small as possible.

The method has two linked parts. A bounded loss limits how much any one large residual can contribute to a constraint. The determinant objective then selects a small-volume scatter matrix among the feasible choices. Both parts matter: bounded loss alone does not guarantee that every minimizing solution is stable or nonsingular.

Definition: The Constrained S-Estimator

Let \(x_1,\ldots,x_n\in\mathbb{R}^p\) be observations. For a candidate location \(T\in\mathbb{R}^p\) and a symmetric positive-definite scatter matrix \(S\), define the Mahalanobis distances \(d_i(T,S)=\{(x_i-T)'S^{-1}(x_i-T)\}^{1/2}\). Choose a nondecreasing function \(\rho:[0,\infty)\to[0,1]\) with \(\rho(0)=0\), and a constraint level \(b\in(0,1)\). The sample S-estimator is any global minimizer of the following constrained problem, when a minimizer exists:

\min_{T\in\mathbb{R}^p,\;S\succ0}\det(S) \quad\text{subject to}\quad \frac{1}{n}\sum_{i=1}^n \rho\!\left(d_i(T,S)\right)\le b.

Here \(S\succ0\) means that \(S\) is positive definite. The scale constraint requires the average transformed distance to remain small, while minimizing \(\det(S)\) chooses a feasible ellipsoid with small volume. In fact, the ellipsoid \(\{x:(x-T)'S^{-1}(x-T)\le1\}\) has volume proportional to \(\det(S)^{1/2}\), so minimizing \(\det(S)\) is equivalent to minimizing that volume.

Definition: A multivariate S-estimator is a location-scatter pair \((\hat T,\hat S)\) that globally minimizes \(\det(S)\) over positive-definite \(S\) and \(T\in\mathbb{R}^p\), subject to the specified robust-scale constraint. The choice of \(\rho\) and \(b\), along with the data, is part of the estimator's definition.

A common requirement for robustness is that \(\rho\) be bounded: once a distance is sufficiently large, increasing it further cannot increase its penalty without limit. Some choices of \(\rho\) reach the upper bound exactly; others approach it asymptotically. The constraint level \(b\) must be selected with the loss function and the intended calibration in mind. It is not a universal constant independent of \(\rho\).

Worked Example: Checking Feasibility With One Extreme Point

Take \(p=2\), five observations \(x_1=(1,0), x_2=(-1,0), x_3=(0,1), x_4=(0,-1), x_5=(100,100)\), and \(\rho(u)=\min(u^2,1)\). Use \(b=0.8\). Check whether \(T_0=(0,0)\), \(S_0=(4/3)I_2\) is feasible, and calculate its determinant.

Since \(S_0^{-1}=(3/4)I_2\), each of the first four observations has squared distance \(3/4\), hence distance \(\sqrt{3}/2\) and loss \(3/4\). The fifth observation has squared distance \((3/4)(100^2+100^2)=15{,}000\), which exceeds 1, so its loss is capped at 1. Therefore

\frac{1}{5}\sum_{i=1}^5\rho(d_i(T_0,S_0)) =\frac{4(3/4)+1}{5} =\frac{4}{5} =0.8.

The constraint is met exactly. The determinant is \(\det(S_0)=(4/3)^2=16/9\). This calculation establishes feasibility and the objective value of this candidate; it does not assert that the candidate is a global minimizer. If the loss were instead \(u^2\), the fifth observation alone would contribute 15,000, illustrating why an unbounded loss does not have the same protection against extreme distances.

First-Order Location and Scatter Equations

The estimating equations follow by differentiating the constraint and the log-determinant objective. The conditions below describe a regular interior solution; they are not a substitute for checking that a candidate is a global minimizer.

Regularity conditions for the equations: Assume \(\rho\) is differentiable at every distance \(d_i>0\), the constraint is active, and the constrained problem has a regular local minimizer with a positive Lagrange multiplier. Assume also the distances involved are positive. Write \(\psi(u)=\rho'(u)\) and \(w(u)=\psi(u)/u\) for \(u>0\). If a distance is zero, the corresponding weight must be defined by an appropriate finite limiting value, when that limit exists.

Write \(r_i=x_i-T\) and \(w_i=w(d_i)\). At a regular solution, the first-order equations are

\sum_{i=1}^n w_i r_i=0, \qquad S=\frac{p\sum_{i=1}^n w_i r_i r_i'}{\sum_{i=1}^n w_i d_i^2}, \qquad \frac{1}{n}\sum_{i=1}^n\rho(d_i)=b.

The location equation is a weighted-centering condition. The scatter equation combines weighted residual outer products and a normalization involving the distances. The last equation says that the robust-scale constraint is active. These equations must be used with the loss constraint: without it, their scale is not fixed.

Result: Under the stated regularity conditions, a constrained local minimizer with positive Lagrange multiplier satisfies the three equations above.

Derivation. It is convenient to minimize \(\log\det(S)\), which has the same minimizers as \(\det(S)\). Introduce a multiplier \(\lambda>0\) for the constraint, written as an average minus \(b\). For \(d_i>0\), differentiating with respect to \(T\) gives

\nabla_T d_i=-\frac{S^{-1}r_i}{d_i}, \qquad \nabla_T\!\left(\frac{1}{n}\sum_i\rho(d_i)\right) =-\frac{1}{n}\sum_i w_i S^{-1}r_i.

The derivative of \(\log\det(S)\) with respect to \(T\) is zero. Setting the derivative of the Lagrangian to zero therefore yields \(\sum_i w_iS^{-1}r_i=0\). Since \(S^{-1}\) is invertible, this is exactly \(\sum_iw_ir_i=0\).

For a symmetric perturbation \(dS\), the matrix differential of a distance is

d(d_i)=-\frac{1}{2d_i} \operatorname{tr}\!\left(S^{-1}r_i r_i'S^{-1}\,dS\right).

Thus the gradient of the constraint with respect to \(S\), represented using the trace inner product, is \(-\frac{1}{2n}S^{-1}(\sum_i w_i r_i r_i')S^{-1}\). The gradient of \(\log\det(S)\) is \(S^{-1}\). Stationarity of the Lagrangian gives

S^{-1}-\frac{\lambda}{2n}S^{-1} \left(\sum_iw_ir_ir_i'\right)S^{-1}=0.

Multiplying on the left and right by \(S\) shows that \(S=\frac{\lambda}{2n}\sum_iw_ir_ir_i'\). To eliminate the multiplier, multiply this identity by \(S^{-1}\), take traces, and use \(d_i^2=r_i'S^{-1}r_i\). The result is \(p=\frac{\lambda}{2n}\sum_iw_id_i^2\). Substitution yields the stated scatter equation. Finally, the constraint must be active: if it were strict, continuity would allow replacing \(S\) by \(cS\) for some \(c<1\) sufficiently close to 1, preserving feasibility while reducing \(\det(S)\). This contradicts local minimality. Hence the constraint equals \(b\), and the derivation is complete. \(\square\)

Worked Example: Verifying Equations at a Symmetric Candidate

Consider \(p=2\) and the four observations \((1,0),(-1,0),(0,1),(0,-1)\). Let \(\rho(u)=1-\exp(-u^2)\), set \(T_0=(0,0)\), and take \(S_0=2I_2\). Choose \(b=1-\exp(-1/2)\). Verify the constraint and the first-order equations at this candidate.

Each residual has squared distance \(1/2\), so every distance is \(1/\sqrt{2}\) and every loss is \(1-\exp(-1/2)=b\). The average loss is therefore \(b\). Here \(\psi(u)=2u\exp(-u^2)\), so \(w(u)=2\exp(-u^2)\). All four weights equal \(2\exp(-1/2)\). Opposite residuals cancel, giving \(\sum_iw_ir_i=0\).

The unweighted sum of residual outer products is \(2I_2\). Consequently, \(\sum_iw_ir_ir_i'=4\exp(-1/2)I_2\). Also, \(\sum_iw_id_i^2=4\exp(-1/2)\), since there are four terms, each equal to \(2\exp(-1/2)(1/2)\). The scatter equation's right-hand side is therefore

\frac{2\{4\exp(-1/2)I_2\}}{4\exp(-1/2)} =2I_2=S_0.

Thus the constraint and first-order equations hold at this candidate. First-order equations alone do not establish global minimality, so this calculation is a check of stationarity conditions, not a claim that \(S_0\) is an S-estimate for every possible choice of the optimization domain or data configuration.

Why Bounded Loss Supports High Breakdown

The central protection is visible directly in the constraint. Suppose \(\rho(u)\le1\), and \(m\) observations have been replaced. For any fixed candidate \((T_0,S_0)\), if each of the \(n-m\) retained observations has distance at most \(c\), then the average loss at that candidate is bounded above by

\frac{1}{n}\sum_{i=1}^n\rho(d_i(T_0,S_0)) \le \frac{(n-m)\rho(c)+m}{n}.

This bound does not depend on how far the replacements are moved: each contributes at most 1. If its right-hand side is no larger than \(b\), the candidate remains feasible, so a global minimizer has determinant no greater than \(\det(S_0)\).

Result: Under the conditions just stated, if \(\{(n-m)\rho(c)+m\}/n\le b\), then \((T_0,S_0)\) is feasible after any replacement of those \(m\) observations, provided the retained observations remain within distance \(c\) of the candidate. Any global minimizer consequently has determinant at most \(\det(S_0)\).

Proof. Each retained observation contributes at most \(\rho(c)\), because \(\rho\) is nondecreasing and its distance is at most \(c\). Each replacement contributes at most 1, because \(\rho\le1\). Summing these \(n-m\) and \(m\) bounds and dividing by \(n\) gives the displayed inequality. The assumed condition makes the candidate feasible. By global minimization, the minimizing determinant cannot exceed the determinant of any feasible candidate, including \(\det(S_0)\). \(\square\)

This argument explains a mechanism behind high-breakdown behavior: extreme replacements cannot make the loss of a fixed, well-fitting candidate grow without limit. But the result bounds the determinant only. It does not by itself bound every eigenvalue of \(\hat S\), guarantee a bounded \(\hat T\), or ensure a nonsingular solution. Those properties also depend on whether the retained observations constrain the location and all directions of scatter. Exact breakdown calculations require additional finite-sample geometry and are not implied by boundedness alone.

Worked Example: A Feasibility Bound for Several Replacements

Suppose \(n=10\), \(\rho(u)=\min(u^2,1)\), \(b=0.7\), and a fixed candidate has distance at most \(1/2\) for each of the eight retained observations. Two observations are replaced. Determine whether the candidate is guaranteed feasible regardless of the replacement values.

For each retained observation, \(\rho(d_i)\le\rho(1/2)=1/4\). Each replacement contributes at most 1. Therefore the average loss is at most

\frac{8(1/4)+2(1)}{10} =\frac{4}{10} =0.4.

Since \(0.4\le0.7\), the candidate is feasible for any values of the two replacements. If it has determinant \(D\), any global S-minimizer has determinant at most \(D\). This conclusion is about feasibility and the determinant comparison; it is not a complete breakdown calculation for the estimator.

Common Pitfall

Incorrect reasoning: “The loss is bounded, so no number or arrangement of outliers can make the S-estimator break down.”

Correction: Bounded loss caps each observation's contribution, but the estimator still minimizes a determinant over positive-definite matrices. If the uncontaminated observations do not constrain the location or some direction of scatter, feasible solutions may become singular or otherwise escape. The feasibility bound above shows why extreme distances have limited direct effect; it does not remove the need for enough well-positioned observations or prove a universal breakdown fraction. A breakdown claim must account for both the chosen loss level and the geometry of the sample.

Key takeaway: An S-estimator minimizes scatter volume subject to a bounded robust-scale constraint. Its first-order equations are weighted location and scatter conditions, while the high-breakdown mechanism comes from capping large residual penalties—not from bounded loss alone.

Check Your Understanding

Answer each question by referring to the constraint, objective, or conditions that apply.

Why does minimizing \(\det(S)\) correspond to choosing a small-volume ellipsoid?
State the regularity assumptions needed to derive the first-order location and scatter equations.
For a loss bounded above by 1, what is the largest possible contribution of one replaced observation to the average constraint?
Why does bounded \(\rho\) not, by itself, prove that every eigenvalue of the minimizing scatter matrix remains bounded?
In the symmetric four-point example, why do the location contributions cancel, and what does checking the scatter equation establish—and not establish?