Affine-Equivariant Breakdown Bounds

Why Affine Equivariance Limits Breakdown

Robustness asks how much contamination an estimator can withstand. In multivariate problems, affine equivariance adds a geometric constraint: changing coordinates by an invertible affine transformation must change the estimate in the corresponding way. This property is useful, but it prevents location and scatter estimators from being arbitrarily robust at every finite sample size. The limits depend on both the number of observations and the dimension.

The bounds below are upper bounds, not claims that every affine-equivariant estimator attains them. Their proofs use a finite-sample geometric result, the affine-frame lemma. Its key conclusion is stronger than saying that some observations can be moved far away: it identifies a sample and a hyperplane for which the estimate has a nonzero component normal to that hyperplane. That nonzero component is essential when an affine stretch is used to force breakdown.

Finite-Sample Replacement Breakdown

Definition: Let $x=(x_1,\ldots,x_n)$, with $x_i\in\mathbb{R}^p$, be a fixed data set. The replacement distance from $x$ to $y=(y_1,\ldots,y_n)$ is the number of indices $i$ for which $x_i\ne y_i$. For a location estimator $T$, its finite-sample replacement breakdown number at $x$ is the smallest $m$ such that $$ \sup_{\text{replacement distance}(x,y)\le m}\|T(y)\|=\infty. $$ For a scatter estimator $S$, breakdown occurs if replacements can make the largest eigenvalue of $S(y)$ arbitrarily large or the smallest eigenvalue arbitrarily close to zero. The corresponding breakdown fraction is the breakdown number divided by $n$.

This is a worst-case definition: the replacements may be chosen adversarially. A location estimate breaks down by escaping every bounded region. A scatter estimate can break down either by exploding in some direction or by becoming arbitrarily close to singular. We consider affine-equivariant estimators that are defined on the samples used in the argument; scatter estimates on those samples are assumed positive definite.

Affine equivariance: For every nonsingular $p\times p$ matrix $A$ and every $b\in\mathbb{R}^p$, a location estimator and a scatter estimator are affine-equivariant if $$ T(Ax_1+b,\ldots,Ax_n+b)=AT(x_1,\ldots,x_n)+b $$ and $$ S(Ax_1+b,\ldots,Ax_n+b)=AS(x_1,\ldots,x_n)A^\mathsf{T}. $$ We also require permutation invariance: reordering the observations does not change either estimate.

The Affine-Frame Lemma and the Bounds

The following finite-sample geometric lemma is the ingredient that makes the bounds work. It is stated here as an established affine-frame result; its conclusion should not be inferred merely from moving points far away. In particular, the location conclusion explicitly guarantees the nonzero normal component that the stretching argument requires.

Lemma (finite-sample affine-frame lemma): Suppose $n\ge p+1$, $q=n-p+1$, and an estimator $T$ is permutation invariant and affine-equivariant. There exist a full-dimensional sample $x$ and an affine hyperplane $H$ such that at least $n-r_L$ observations lie in $H$, while $T(x)\notin H$, where $$ r_L=\left\lceil\frac{q}{2}\right\rceil. $$ For a positive-definite affine-equivariant scatter estimator, there is a full-dimensional sample and a hyperplane containing at least $n-r_S$ observations, where $$ r_S=\left\lfloor\frac{q}{2}\right\rfloor. $$ The location statement is the paired-sample form of the affine-frame lemma: its pairing and affine-frame argument guarantees an estimate outside the anchor hyperplane, not merely a sample with outliers on one side. The scatter statement requires no analogous nonzero-location conclusion; positive definiteness supplies positive variance normal to every hyperplane.

The lemma is a geometric input about affine-equivariant procedures, not a consequence of affine equivariance applied to an arbitrary chosen sample. We now prove the breakdown bounds from its stated conclusions. In both arguments, choose coordinates so that $H=\{z\in\mathbb{R}^p:z_p=0\}$, and use the linear map $$ A_a=\operatorname{diag}(1,\ldots,1,a),\qquad a>0. $$ Every observation in $H$ is fixed by this map. Thus transforming the sample changes only observations outside $H$, of which there are at most the relevant $r_L$ or $r_S$.

Theorem (finite-sample affine-equivariant breakdown bounds): Under the conditions of the affine-frame lemma, the worst-case replacement breakdown fractions of affine-equivariant location and positive-definite scatter estimators satisfy $$ \varepsilon^*_L\le \frac{\left\lceil(n-p+1)/2\right\rceil}{n}, \qquad \varepsilon^*_S\le \frac{\left\lfloor(n-p+1)/2\right\rfloor}{n}. $$ Equivalently, no such estimator can have a worst-case replacement breakdown number greater than the corresponding integer numerator.

Proof for location. Take the sample $x$ and hyperplane $H$ supplied by the location part of the lemma. Write $T(x)=(t_1,\ldots,t_p)^\mathsf{T}$. Since $T(x)\notin H$, $t_p\ne0$. The transformed sample $A_ax$ differs from $x$ in at most $r_L$ positions, because all observations in $H$ are fixed. By affine equivariance, $$ T(A_ax)=A_aT(x)=(t_1,\ldots,t_{p-1},a t_p)^\mathsf{T}. $$ Therefore $$ \|T(A_ax)\|\ge a|t_p|\longrightarrow\infty \quad\text{as }a\longrightarrow\infty. $$ At most $r_L$ replacements suffice to make the location estimate unbounded, proving the stated location bound.

Proof for scatter. Take the full-dimensional sample from the scatter part of the lemma and write $S(x)$ for its positive-definite scatter estimate. Let $e_p=(0,\ldots,0,1)^\mathsf{T}$. Positive definiteness gives $e_p^\mathsf{T}S(x)e_p>0$. The transformed sample differs in at most $r_S$ positions, and affine equivariance yields $S(A_ax)=A_aS(x)A_a^\mathsf{T}$. The largest eigenvalue is at least the quadratic form in the unit direction $e_p$, so $$ \lambda_{\max}(S(A_ax)) \ge e_p^\mathsf{T}A_aS(x)A_a^\mathsf{T}e_p =a^2e_p^\mathsf{T}S(x)e_p \longrightarrow\infty. $$ Thus at most $r_S$ replacements suffice to break scatter, proving the scatter bound. $\square$

Worked Examples: Reading the Integer Bounds

Worked Example: A Three-Dimensional Sample of Size 17

Suppose $p=3$ and $n=17$. Then $q=n-p+1=17-3+1=15$. The location numerator is $\lceil15/2\rceil=8$, while the scatter numerator is $\lfloor15/2\rfloor=7$. Hence the bounds are $$ \varepsilon^*_L\le \frac{8}{17}\approx0.471, \qquad \varepsilon^*_S\le \frac{7}{17}\approx0.412. $$ The different integer counts matter: the location bound rounds upward and the scatter bound downward. These are upper bounds on worst-case robustness, not guarantees that a particular estimator will withstand that many replacements.

Worked Example: Changing Dimension at Fixed Sample Size

Compare $n=12$ observations in dimensions $p=2$ and $p=5$. In dimension 2, $q=12-2+1=11$, so the bounds are $r_L=\lceil11/2\rceil=6$ and $r_S=\lfloor11/2\rfloor=5$. In dimension 5, $q=12-5+1=8$, giving $r_L=4$ and $r_S=4$. Thus the location and scatter fractions are bounded by $6/12,5/12$ in dimension 2, but by $4/12,4/12$ in dimension 5. The smaller bounds in higher dimension reflect the greater geometric constraints imposed by affine equivariance.

Worked Example: An Odd Value of the Dimension-Adjusted Count

Let $n=10$ and $p=4$. Then $q=10-4+1=7$, an odd integer. Consequently $r_L=\lceil7/2\rceil=4$ and $r_S=\lfloor7/2\rfloor=3$, so $$ \varepsilon^*_L\le \frac{4}{10}, \qquad \varepsilon^*_S\le \frac{3}{10}. $$ Using $q/2=3.5$ as though it were an exact replacement count would be incorrect. Replacement counts are integers, and the two bounds use different roundings.

What the Bounds Do—and Do Not—Say

These results do not identify the exact breakdown fraction of every affine-equivariant estimator. They rule out worst-case performance above the stated limits. An estimator may break down earlier, and attaining a bound requires a separate argument for that estimator. The dimension adjustment $n-p+1$ also matters: reporting only an asymptotic “one-half” breakdown point hides finite-sample differences, including the distinct rounding for location and scatter.

The stretching argument is valuable because it converts geometry into breakdown. A hyperplane containing most observations supplies points that remain fixed under a normal stretch; affine equivariance then determines how the estimate transforms. For location, the lemma must ensure that the estimate starts with a nonzero normal component. For scatter, positive definiteness ensures positive variance in that direction, so the stretch makes the largest eigenvalue diverge.

Common Pitfall

Incorrect reasoning: “Move a few observations away from a hyperplane and stretch in the normal direction; the location estimate must then diverge.” This does not follow. If the location estimate lies in the hyperplane, stretching leaves it fixed.
Correction: The location argument needs the affine-frame lemma’s specific conclusion $T(x)\notin H$. Once that is known, affine equivariance gives a normal coordinate $a t_p$ with $t_p\ne0$, which diverges as $a$ grows.
Another common error: Treating the bounds as achieved breakdown fractions. They are upper bounds for all procedures satisfying the stated conditions; an individual estimator may have lower breakdown.

Key takeaway: Affine equivariance imposes finite-sample limits of $\lceil(n-p+1)/2\rceil/n$ for location and $\lfloor(n-p+1)/2\rfloor/n$ for positive-definite scatter. The location proof depends essentially on the affine-frame lemma guaranteeing a nonzero normal component.

Check Your Understanding

Work through these questions using the definitions and bounds above.

For $n=14$ and $p=3$, calculate the location and scatter replacement-count bounds and their fractions.
Why does affine equivariance alone, applied to an arbitrary sample, not establish the location breakdown bound?
In the location proof, what role does the condition $T(x)\notin H$ play?
For scatter, explain why positive definiteness implies that stretching normal to $H$ makes the largest eigenvalue diverge.
Do the upper bounds imply that every affine-equivariant estimator attains its stated bound? Explain.