Breakdown points and variation exponents of robust M-estimators in

linear models

Ivan Mizera^{∗} Comenius University, Bratislava

and

Christine H. Müller Free University of Berlin

Abstract: The breakdown point behavior of M-estimators in linear models with fixed designs, arising from planned experiments or qualitative factors, is characterized. Particularly, this behavior at fixed designs is quite different from that at designs which can be corrupted by outliers—the situation prevailing in the literature. For fixed designs, the breakdown points of robust M-estimators (those with bounded derivative of the score function), depend on the design and the variation exponent (index) of the score function. This general result implies that the highest breakdown point within all regression equivariant estimators can be attained also by certain M-estimators: those with slowly varying score function, like the Cauchy or slash maximum likelihood estimator. The M-estimators with variation exponent greater than 0, like the L_{1} or Huber estimator, exhibit a considerably worse breakdown point behavior. Finally, some known results about the breakdown point of the L_{1} estimator are improved and its numerical computation is outlined.

AMS 1991 subject classification: Primary: 62F35, 62F10; Secondary: 62J05, 62J10, 62K99. Key words and phrases: Breakdown point, L_{1} estimator, Linear model, Mestimator, Planned experiments, Regular variation. Running title: Breakdown points of M-estimators

∗Research supported by the Slovak GAS grant 1/1489/94 and by the grant 436 SLK 17/3/95 of the Deutsche Forschungsgemeinschaft

1 Introduction

We consider a general linear model

y = Xβ + ε

where y = (y_{1}, y_{2}, …, y_{N})^{T} ∈ ℝ^{N} is a vector of observations, β ∈ ℝ^{p} is an unknown parameter vector, ε = (ε_{1}, ε_{2}, …, ε_{N})^{T} ∈ ℝ^{N} a vector of errors, and X = (x_{1}, x_{2}, …, x_{N})^{T} ∈ ℝ^{N×p} is the known matrix of design points, which together constitute a design. Let β̂ be an estimator of β. If X is given by an experimentator, it can rightly be assumed that the design points do not contain any gross-errors, outliers and similar phenomena—in other words, they are without errors and, particularly, they are non-stochastic. The same can be said for factors of linear models which are of qualitative nature (in ANOVA models, for instance). In such a context, it is natural to define the breakdown point ε^{∗}(β̂, y, X) of β̂ as He et al. (1990), Ellis and Morgenthaler (1992), or Müller (1995):

ε^{∗}(β̂, y, X) = \frac{1}{N} min\{M: sup_{ỹ∈B(y,M)} ∥β̂(ỹ, X)∥ = ∞\},

where

B(y, M) = {ỹ: card{n : ỹ_{n} ≠ y_{n}} ≤ M}.

This approach to the breakdown point (with fixed design) differs from that one prevailing in the literature (with moving design). The latter assumes that not only the y_{i}’s, but also the design points x_{i} are vulnerable to errors, and, as a consequence, the definition of the breakdown point allows also for perturbations of the x_{i}’s in B(y, M) (see, for instance, Rousseeuw and Leroy, 1987).

In the present paper, we support the view that for planned experiments and models with qualitative factors, the approach with fixed design is more appropriate. In this vein, an upper bound for the breakdown point was given in Müller (1995): for any regression equivariant estimator (that is, an estimator such that β̂(y + Xϑ, X) = β̂(y, X) + ϑ for all y, X and ϑ),

ε^{∗}(β̂, y, X) ≤ \frac{1}{N} ⌊\frac{N − N (X) + 1}{2}⌋ ,  (1)

where

N (X) = max_{β≠0} card{n : x_{n}^{T} β = 0}

is the maximal number of regressors x_{n} in a subspace of ℝ^{p} (⌊u⌋ denotes the largest integer ≤ u). Note that (1) is the same as the upper bound in the moving design framework, though the latter allows for more general perturbations of the data points—see Rousseeuw and Leroy (1987) for N (X) = p − 1 and Mili and Coakley (1993) for the general case.

It is interesting whether for fixed design the upper bound (1) is attainable and which estimators can achieve it. Müller (1995) showed that the bound (1) can be attained by some trimmed L_{p} estimators. In the present paper, we address the question whether the bound can be attained also by certain M-estimators.

An M-estimator is defined via minimization:

β̂(y, X) = arg min_{β}D(β, y, X),

where

D(β, y, X) = ∑_{n=1}^{N} φ(y_{n} − x_{n}^{T} β)

is an objective function and φ is a given score function from ℝ to ℝ; in the sequel, we suppose that φ is absolutely continuous, a primitive function of ψ. Note that all M-estimators are regression equivariant.

For the special case of the location model— that is, the simplest regression model with x_{1} = x_{2} = ⋯ = x_{N} = 1 and β ∈ ℝ^{1}—it is known that Mestimators with bounded ψ attain the maximum possible breakdown point of approximately 50% whenever ψ is nondecreasing, corresponding to a convex φ (Huber, 1981, page 54) or φ is unbounded for redescending ψ (Huber, 1984). In regression models with moving design, all M-estimators with nondecreasing ψ have the same low breakdown point 1/N as the least squares estimator, as can be shown along the lines of Maronna, Bustos and Yohai (1979). Their finding created an overall impression in the robustness theory that M-estimators possess “bad” breakdown point behavior. However, the result of Maronna, Bustos and Yohai (1979) was based on the convexity of φ and used moving design definition of the breakdown point.

In the setting of fixed design, the whole performance of M-estimators radically changes. As shown below, M-estimators can exhibit high breakdown points, including the highest possible ones. Contrary to the location case, in general linear models the breakdown point of an M-estimator depends on the asymptotic behavior of the function φ, described in terms of the exponent r of regular variation of φ. Together with the design matrix X, r determines completely the breakdown behavior of the M-estimator.

The paper is organized as follows. In Section 2 we briefly introduce regularity conditions and state the main result: a dependence of the breakdown point of an M-estimator on its variation exponent r and the design matrix X. In Section 3 we discuss the regularity conditions. In Section 4, special attention is paid to two extreme cases: to M-estimators with r = 0, like the Cauchy and slash maximum likelihood estimator, which have the highest breakdown point possible for regression equivariant estimators; and to M-estimators with convex φ and r = 1, like the L_{1}, Huber and logistic maximum likelihood estimator, whose performance is much worse. The results for the L_{1} estimator improve and complement those of He et al. (1990) and Ellis and Morgenthaler (1992). Section 5 deals with applications: the explicit breakdown points are computed for special linear models and it is shown how choosing an appropriate design, for a given φ, can improve the breakdown point of the M-estimator. Section 6 brings the proofs. Finally, Appendix contains some considerations useful for numerical computation of the breakdown points of M-estimators with r = 1.

2 The main result

A measurable function f : ℝ^{+} → ℝ^{+} is called regularly varying, if there is a function h such that for all u > 0,

lim_{t→∞} \frac{f(tu)}{f(t)} = h(u),

(see Bingham, Goldie and Teugels, 1987, Chapter 1, or Resnick, 1987, Chapter 0). In such a case, h(u) = u^{r} for some r ∈ ℝ, which is called the exponent or index of variation. If r = 0, then f is called slowly varying.

We introduce the following assumptions about φ:

(A) Shape: φ is symmetric (even), nondecreasing on [0, +∞] and nonnegative.

(B) Unboundedness: φ is unbounded.

(C) Subadditivity: there exists L > 0 such that

φ(t + s) ≤ φ(t) + φ(s) + L for all t, s ≥ 0.

(D) Regular variation: φ is regularly varying with an exponent r ≥ 0.

Given r ≥ 0, we define, using the convention 0^{0} = 0,

M(X, r) =

min {card E: ∑_{n∈E} |x_{n}^{T} β|^{r} ≥ ∑_{n∉E} |x_{n}^{T} β|^{r} for some β ≠ 0} ,

where E runs over the subsets of {1, 2, …, N}. For r = 1, M(X, 1) coincides with the minimal possible cardinality of a set E ⊂ {1, 2, …, N} such that

max_{β≠0} \frac{∑_{n∈E} |x_{n}^{T} β|}{∑_{n=1}^{N} |x_{n}^{T} β|} ≥ \frac{1}{2}.

In this form, M(X, 1) was introduced by He et al. (1990) in the connection with breakdown points of L_{1} type estimators. Ellis and Morgenthaler (1992) employed it to derive a lower bound for the exact fit degree of the L_{1} estimator. They also pointed out its diagnostic value in the assessment of leverage points in L_{1} regression.

Proposition 1. If q ≥ r ≥ 0 then

M(X, q) ≤ M(X, r) ≤ M(X, 0) = ⌊\frac{N − N (X) + 1}{2}⌋ .  (2)

The following general theorem shows how the breakdown point of an M-estimator depends only on r and X, via M(X, r).

Theorem 1. If β̂ is an M-estimator with φ satisfying (A), (B), (C), and (D) with variation exponent r ∈ [0, 1], then

\frac{M(X, r)}{N} ≤ ε^{∗}(β̂, y, X) ≤ \frac{M(X, r) + 1}{N}  (3)

for all y ∈ ℝ^{N}.

The proof of Theorem 1 shows that the upper bound is still true when φ satisfies only (A), (B), and (D) with r > 1. Then, in general, the upper bound is not anymore sharp, as the case r = 2 shows: the least squares estimator has the breakdown point 1/N, which is in general not equal to (M(X, 2) + 1)/N. Hence the connection between the breakdown point and variation exponent holds only for robust M-estimators—that is, for those with bounded ψ.

Theorem 1 shows that for the large sample size N, the breakdown point is approximately equal to M(X, r)/N. In special cases, as shown in Section 4, the equality holds: ε^{∗}(β̂, y, X) = M(X, r)/N.

3 Discussion of the regularity conditions

Concerning shape, it is clear that nonnegativity of φ can be always achieved by adding a constant. The other assumptions in (A) are satisfied by all φ used in practice.

A standard property of regularly varying functions implies that if (D) holds with r > 0, then (B) is satisfied. This implication does not hold for r = 0; the location case shows that for r = 0, the assumption (B) in Theorem 1 is essential.

Since φ and φ + K yield the same M-estimates, (C) really means a kind of subadditivity: a constant can be added to φ such that for the resulting φ, φ(t + s) ≤ φ(t) + φ(s) holds—not only for t, s ≥ 0, but for all t, s, as shown by Lemma 1 in Section 6. Subadditivity holds for φ(u) = |u|; for other functions φ this is not that obvious, nevertheless, (C) can be proved relatively easily from simpler assumptions.

A careful inspection of the proof of Lemma 4.2. in Huber (1984) reveals that if

(i) (A) is fulfilled and φ(0) = 0;

(ii) there is an u_{0} ≤ 0 such that ψ is nondecreasing for 0 < u < u_{0} and nonincreasing for u_{0} < u < ∞, with ψ(u) → 0 for u → ∞;

then η(t) = sup_{s} |φ(t+s)−φ(s)|−φ(t) is bounded. This immediately implies (C). (See also Mizera, 1996.) Assumptions (i) and (ii) are satisfied, for instance, by the Cauchy log-likelihood φ(u) = log(1+u^{2}). Another example is provided by the slash likelihood (for the definition, see Morgenthaler and Tukey, 1991, or Hoaglin, Mosteller and Tukey, 1983).

For convex φ, (C) can be verified by observing that (c denotes the limit of ψ at ∞) for s, t ≥ 0,

\begin{aligned}φ(s + t) − φ(s) & = ∫_{s}^{s+t} ψ(u) du ≤ ct = ∫_{0}^{t} ψ(u) du + ∫_{0}^{t}(c − ψ(u)) du \\ & ≤ ∫_{0}^{t} ψ(u) du + ∫_{0}^{∞}(c − ψ(u)) du ≤ φ(t) + L \end{aligned}

—provided that ∫_{0}^{∞}(c − ψ(u)) du = L is finite. In this way, (C) follows for the Huber as well as for the logistic maximum likelihood estimator (for the definition, see Hampel et al., 1986).

For convex φ, subaddivity also implies boundedness of ψ: just observe that (C) entails

∫_{s}^{s+t} ψ(u) du = φ(s + t) − φ(s) ≤ φ(t) + L.

By monotonicity of ψ,

∫_{s}^{s+t} ψ(u) du ≥ ψ(s)t.

Consequently, ψ(s)t ≤ φ(t)+L; this cannot be true if ψ(s) → ∞ for s → ∞.

The easiest way to verify (D) is a direct one, using the L’Hospital rule. Also, all functions with a nonzero limit at ∞ are slowly varying; as a consequence, any nondecreasing bounded ψ is slowly varying and this implies, through Proposition 1.5.8 of Bingham, Goldie and Teugels (1987) (see also Resnick, 1987, Theorem 0.6.a), that the corresponding φ is regularly varying with r = 1. There are also other criteria for regular variation: for instance, the von Mises property asserts that φ is regularly varying with the exponent r whenever

(D1)  lim_{u→∞} \frac{uψ(u)}{φ(u)} = r.

If uψ(u) is bounded, then (B) immediately implies the slow variation of φ.

If φ is the log-likelihood corresponding to a density f, that is, if φ(u) = − log f(u), then (A) is satisfied whenever f is symmetric and unimodal. Condition (D) in this case reflects the tail behavior of f: it is implied by a stronger condition

(D2) There exist r ≥ 0, c > 0 and m > 0 such that

lim_{t→∞} \frac{φ(t)}{m log(t) + c t^{r}} = 1.

Condition (D2) is itself implied by a further stronger condition

(D3) There exist L^{∗} > 0, r ≥ 0, m ≥ 0 and c ≥ 0, m + c > 0, such that

|φ(t) − m log(t) − c t^{r}| ≤ L^{∗} for all t > L^{∗}.  (4)

A special class of functions satisfying (4) appeared in He et al. (1990): they called those φ satisfying (4) with m = 0 and r = 1 “score functions of L_{1} type”. The log-likelihood functions φ satisfying (D2) with r > 0 correspond to light-tailed distributions (distributions with exponential tails; for instance, logistic and exponential distribution); the slowly varying φ with r = 0 correspond to heavy-tailed distributions (distributions with algebraic tails, like the Student t-distributions with k degrees of freedom, including the Cauchy distribution with k = 1). For more background on tail behavior, see Jurečková (1981) or He et al. (1990).

The following proposition summarizes some interrelations among the regularity conditions.

Proposition 2. Suppose that (A) holds. Then (a) (D1) implies (D); (b) (D2) implies (D) and (B); (c) (D3) implies (D2), and also (C) if r ∈ [0, 1];

(d) (B), (C) and (D) imply r ∈ [0, 1].

Summarizing the discussion above, we have (among others) the following examples of estimators satisfying (A), (B), (C) and (D): the L_{1}, Huber and logistic maximum likelihood estimator (r = 1), the Cauchy and slash maximum likelihood estimator (r = 0).

4 Special cases: r = 0 and r = 1

The following theorem is a direct corollary of the upper bound (1) and Proposition 1.

Theorem 2. For an M-estimator β̂ with φ satisfying (A), (B), (C), and (D) with r = 0,

ε^{∗}(β̂, y, X) = \frac{M(X, 0)}{N} = \frac{1}{N} ⌊\frac{N − N (X) + 1}{2}⌋

holds for all y ∈ ℝ^{N} and X.

In other words, M-estimators with slowly varying φ, like the Cauchy or slash maximum likelihood estimator, have the highest breakdown point possible for regression equivariant estimators.

¿From Proposition 1 follows that this does not hold, in general, for Mestimators with r = 1 (see also Section 5). For certain special cases of these estimators, a sharpening of Theorem 1, akin to Theorem 2, can be proved. We prove this fact for the L_{1} estimator.

Theorem 3. For the L_{1} estimator β̂_{1},

ε^{∗}(β̂_{1}, y, X) = \frac{M(X, 1)}{N}  (5)

holds for all y ∈ ℝ^{N} and X.

Proving Theorem 3, we have only to show that, in view of (3),

ε^{∗}(β̂_{1}, y, X) ≤ \frac{M(X, 1)}{N}.  (6)

We first establish (6) for y = 0. To finish the proof of Theorem 3, it is sufficient to verify that the L_{1} estimator is of uniform variation. (See Section 6 for the details.)

We say that an estimator β̂ is of uniform variation, if, given X, for every δ > 0 there is a K > 0 such that whenever ∥y^{1} − y^{2}∥ ≤ δ, then for any β^{1} ∈ β̂(y^{1}, X) there is β^{2} ∈ β̂(y^{2}, X) such that ∥β^{1} − β^{2}∥ ≤ K. Uniform variation implies—as shown by Lemma 4—that the breakdown point ε^{∗}(β̂_{1}, y, X) does not exceed the breakdown point at 0. Ellis and Morgenthaler (1992) used a similar idea for the transition from the upper bound on the exactfit point to the upper bound on the breakdown point for an arbitrary y. Instead of uniform variation they used uniform continuity (which is more stringent and implies uniform variation).

It is plausible that the analogue of Theorem 3 holds for some other L_{1}- type estimators: particularly, we were able to prove (6) with y = 0 for the Huber estimator. We conjecture that this estimator is also of uniform variation, and, as a consequence, satisfies (5). In this connection, Lemma 5.3 of He et al. (1990) should be quoted: one of its possible interpretations (its original statement is in a slightly vague form) would yield uniform variation of all L_{1}-type estimators. Unfortunately, that version which could be proved—matching the needs of the original paper (He and Portnoy, personal communication)—seems not to be helpful for our purposes.

5 Applications

For designs with minimum support, like the classical A- and D- optimal designs for polynomial regression and the designs for the one-way layout, the breakdown points of all M-estimators with φ satisfying (A), (B), (C) and (D) with r ∈ [0, 1] are equal and attain the maximum value if the numbers of repetitions are equal. This is a consequence of the following proposition.

Proposition 3. Suppose that {x_{1}, …, x_{N}} ⊆ {χ_{1}, …, χ_{p}} ⊂ ℝ^{p}. Let N_{i} = ∑_{n=1}^{N} 1_{{χ_{i}}}(x_{n}) for i = 1, …, p. If χ_{1}, …, χ_{p} are linearly independent, then

M(X, r) = ⌊\frac{N − N (X) + 1}{2}⌋ = ⌊\frac{1 + min_{i=1,...,p} N_{i}}{2} ⌋ ≤ ⌊\frac{N + p}{2p}⌋

for every r ∈ [0, 1].

In the setting of Proposition 3, or if r = 0, the quantity M(X, r) can be easily computed, since N (X) can be (see Müller, 1995, 1996a, 1996b, for a numerical algorithm Mili and Coakley, 1993). In other cases, computing M(X, r) requires special considerations.

In the sequel we concentrate on the important case r = 1, which provides also lower bounds for every r ∈ (0, 1), in view of Proposition 1. For r = 1, we can construct an algorithm to compute M(X, 1) numerically, based on certain convexity and linearity properties which hold in this case; see Appendix for more details. But, for special linear models, we are also able to give explicit formulas.

For the linear regression through the origin, we have the following obvious result (see also He et al., 1990).

Proposition 4. If, for n = 1, …, N, x_{n} = t_{n} ∈ ℝ with |t_{1}| ≤ |t_{2}| ≤ ⋯ ≤ |t_{N}| then

M(X, 1) = min \{M: ∑_{n=1}^{N−M} |t_{n}| ≤ ∑_{n=N−M+1}^{N} |t_{n}|\} ≤ ⌊\frac{N + 1}{2}⌋ .

The equality holds if and only if |t_{1}| = |t_{2}| = ⋯ = |t_{N}|.

We also can write an explicit formula for M(X, 1) in the univariate linear regression with a constant term.

Proposition 5. If, for n = 1, …, N, x_{n} = (1, t_{n})^{T} ∈ ℝ^{2} with t_{1} ≤ t_{2} ≤ ⋯ ≤ t_{N}, then

\begin{aligned}M(X, 1) & = \begin{matrix}min & \{M: ∑_{n=1}^{N−M}(t_{n} − t_{1}) ≤ ∑_{n=N−M+1}^{N}(t_{n} − t_{1}) \\ or & ∑_{n=M+1}^{N}(t_{N} − t_{n}) ≤ ∑_{n=1}^{M}(t_{N} − t_{n})\} \end{matrix} \\ & ≤ ⌊\frac{N + 3}{4}⌋ . \end{aligned}

Proposition 5 shows that the upper bound of N/4 is attained by designs with equispaced design points t_{n}, as well as by the classical D-optimal design which puts a half of the observation at the each endpoint of the design region. There are also other designs attaining the upper bound — for instance, the design with L observations at 1 and 3 and 2L observations at 2.

Moreover, note that in the linear regression setting of Proposition 5, Mestimators satisfying (D) with r = 0 have the breakdown point ⌊N/2⌋ if the design points x_{n} are pairwise different (see Müller, 1995). That means that the Cauchy estimator (among others) has a much higher breakdown point than the L_{1} estimator.

Proposition 5 gives also upper bounds for the breakdown point in other linear models.

Proposition 6. Let, for n = 1, …, N, x_{n} = (x_{n}^{1}, …, x_{n}^{p})^{T} with x_{1}^{i} ≤ x_{2}^{i} ≤ ⋯ ≤ x_{N}^{i} for i ∈ {1, …, p}. If there exists A ∈ ℝ^{2×p} such that Ax_{n} = (1, x_{n}^{i})^{T} for n = 1, …, N, then

\begin{aligned}M(X, 1) & ≤ \begin{matrix}min & \{M: ∑_{n=1}^{N−M}(x_{n}^{i} − x_{1}^{i}) ≤ ∑_{n=N−M+1}^{N}(x_{n}^{i} − x_{1}^{i}) \\ or & ∑_{n=M+1}^{N}(x_{N}^{i} − x_{n}^{i}) ≤ ∑_{n=1}^{M}(x_{N}^{i} − x_{n}^{i})\} \end{matrix} \\ & ≤ ⌊\frac{N + 3}{4}⌋ . \end{aligned}

Proposition 6 provides, in particular for polynomial regression and for multiple linear regression, an upper bound for the breakdown point of the L_{1} and Huber estimators, as well as a complete proof of the Ellis’ and Morgenthaler’s upper bound of 1/4. Ellis and Morgenthaler (1992) showed, for lattice designs, that there are designs attaining this upper bound.

6 Proofs

Proof of Proposition 1. We first prove the inequality part of (2). Take an arbitrary β ≠ 0 and E ⊂ {1, 2, …, N} with card E = M(X, r) and

∑_{n∈E} |x_{n}^{T} β|^{r} − ∑_{n∉E} |x_{n}^{T} β|^{r} ≥ 0.  (7)

If there are i ∈ E and j ∉ E such that |x_{i}^{T} β| < |x_{j}^{T} β|, then we can exchange i and j—that is, we can consider (E ∪{j})∖{i} instead of E. Thus, without loss of generality we can assume that

d = min{|x_{n}^{T} β|: n ∈ E} ≥ max{|x_{n}^{T} β|: n ∉ E}.

Then

\begin{aligned}0 & ≤ d^{q−r}(∑_{n∈E} |x_{n}^{T} β|^{r} − ∑_{n∉E} |x_{n}^{T} β|^{r}) \\ & ≤ ∑_{n∈E} |x_{n}^{T} β|^{r}|x_{n}^{T} β|^{q−r} − ∑_{n∉E} |x_{n}^{T} β|^{r}|x_{n}^{T} β|^{q−r}, \end{aligned}

hence M(X, q) ≤ M(X, r).

Now we show the equality in (2). By definition of N (X), there exists β ≠ 0 and E_{0} ⊂ {1, 2, …, N} with card E_{0} = N (X) such that |x_{n}^{T} β|^{0} = 0 for all n ∈ E_{0} and |x_{n}^{T} β|^{0} = 1 for all n ∉ E_{0}. Then for any subset E ⊂ {1, 2, …, N} ∖ E_{0} with card E = ⌊(N − N (X) + 1)/2⌋ we have

\begin{aligned}∑_{n∈E} |x_{n}^{T} β|^{0} & = ⌊\frac{1}{2}(N − N (X) + 1)⌋ \\ & ≥ N − ⌊\frac{1}{2}(N − N (X) + 1)⌋ − N (X) = ∑_{n∉E} |x_{n}^{T} β|^{0}; \end{aligned}

hence M(X, 0) ≤ ⌊(N − N (X) + 1)/2⌋. To see the reverse inequality, take any β ≠ 0 and E ⊂ {1, 2, …, N} with card E = M(X, 0) such that (7) holds with r = 0. Since at most N (X) of the x_{n}^{T} β’s satisfy |x_{n}^{T} β|^{0} = 0, we have

\begin{aligned}M(X, 0) & ≥ ∑_{n∈E} |x_{n}^{T} β|^{0} ≥ ∑_{n∉E} |x_{n}^{T} β|^{0} \\ & ≥ N − M(X, 0) − N (X), \end{aligned}

and this implies that 2M(X, 0) ≥ N − N (X); that is, M(X, 0) ≥ ⌊(N − N (X) + 1)/2⌋.

Before proving Theorem 1, we state three lemmas.

Lemma 1. Conditions (A) and (C) imply

φ(t + s) ≤ φ(t) + φ(s) + L for all t, s ∈ ℝ.

Proof. We prove the equivalent assertion: for any s, t ∈ ℝ, φ(s − t) ≥ φ(s) − φ(t) − L. If 0 ≤ t < s, then φ(s) = φ(s − t + t) ≤ φ(s − t) + φ(t) + L. If s < t ≤ 0, then, due to the symmetry of φ, we have φ(s) = φ(−s) = φ(−(s−t)−t) ≤ φ(s−t)+φ(t)+L. Finally, if |s| ≤ |t|, then φ(s−t)−φ(s) ≥ 0 − φ(t) − L, since φ is nonnegative and nondecreasing.

Lemma 2. Suppose that φ satisfies conditions (A) and (D) and let t_{k} → ∞ and u_{k} → u be arbitrary. Then

lim_{k→∞} \frac{φ(u_{k}t_{k})}{φ(t_{k})} = u^{r},

for k → ∞, whenever (a) r > 0, u_{k} ≥ 0 and u ≥ 0; or (b) r = 0 and u > 0 Proof. The lemma follows from the standard property of regularly varying functions: see, for instance, Bingham, Goldie and Teugels (1987, Theorem 1.5.7) or Resnick (1987, Proposition 0.5).

Lemma 3. If N (X) < N, then for all r ≥ 0 there is a β ≠ 0 and a subset E ⊆ {1, 2, …, N} with card E = M(X, r) + 1 such that

∑_{n∈E} |x_{n}^{T} β|^{r} > ∑_{n∉E} |x_{n}^{T} β|^{r}.

Proof. Let β ≠ 0 and E ⊂ {1, 2, …, N} with card E = M(X, r) so that

∑_{n∈E} |x_{n}^{T} β|^{r} ≥ ∑_{n∉E} |x_{n}^{T} β|^{r}  (8)

is satisfied. If the inequality in (8) is sharp then it remains sharp when we add an element to E. If we have equality in (8) and there exists n ∉ E with |x_{n}^{T} β| ≠ 0 then we can add this n to E so that for E ∪ {n} the inequality in (8) is sharp. If |x_{n}^{T} β| = 0 for all n ∉ E then equality in (8) implies |x_{n}^{T} β| = 0 for all n = 1, 2, …, N so that N (X) = N. This contradicts the assumptions.

Proof of Theorem 1. Lower bound. Due to the regression equivariance of M-estimators, we may assume that β̂(y, X) = 0, without loss of generality. Let M = Nε^{∗}(β̂, y, X). Then for every k ∈ ℕ there is a y^{k} ∈ B(y, M), such that ∥β̂(y^{k}, X)∥ > k. Again without restricting generality we may suppose that y_{n}^{k} = y_{n} for n = 1, 2, …, N − M. For brevity, β̂(y^{k}, X) is denoted by β^{k}. We have that ∥β^{k}∥ → ∞ and, in view of the compactness of the unit sphere in ℝ^{p}, we may also suppose that

\frac{β^{k}}{∥β^{k}∥} → β^{0},

passing otherwise to a subsequence. Since

0 ≥ D(β^{k}, y^{k}, X) − D(0, y^{k}, X)

= ∑_{n=1}^{N−M} φ(y_{n} − x_{n}^{T} β^{k}) + ∑_{n=N−M+1}^{N} φ(y_{n}^{k} − x_{n}^{T} β^{k})

− ∑_{n=1}^{N−M} φ(y_{n}) − ∑_{n=N−M+1}^{N} φ(y_{n}^{k}),

we have by Lemma 1 and the symmetry of φ

0 ≥ ∑_{n=1}^{N−M} φ(x_{n}^{T} β^{k}) − 2 ∑_{n=1}^{N−M} φ(y_{n}) − ∑_{n=N−M+1}^{N} φ(x_{n}^{T} β^{k}) − NL. (9)

Dividing (9) by φ(∥β^{k}∥) and letting k → ∞, we obtain

0 ≥ ∑_{n=1}^{N−M} lim inf_{k→∞} \frac{φ (∥β^{k}∥ |x_{n}^{T} \frac{β^{k}}{∥β^{k}∥} |)}{φ(∥β^{k}∥)}

− ∑_{n=N−M+1}^{N} lim sup_{k→∞} \frac{φ (∥β^{k}∥ |x_{n}^{T} \frac{β^{k}}{∥β^{k}∥} |)}{φ(∥β^{k}∥)}.

(10)

If r ∈ (0, 1] then, in view of Lemma 2(a), the inequality (10) acquires the form

0 ≥ ∑_{n=1}^{N−M} |x_{n}^{T} β^{0}|^{r} − ∑_{n=N−M+1}^{N} |x_{n}^{T} β^{0}|^{r},

which implies that M ≥ M(X, r). Consequently, we have ε^{∗}(β̂, y, X) ≥ M(X, r)/N in this case.

Suppose now that r = 0. If t_{k} → ∞ and u_{k} → 0, then

0 ≤ lim inf_{k→∞} \frac{φ(u_{k}t_{k})}{φ(t_{k})} ≤ lim sup_{k→∞} \frac{φ(u_{k}t_{k})}{φ(t_{k})} ≤ lim_{k→∞} \frac{φ(t_{k})}{φ(t_{k})} = 1,  (11)

by (A). Since x_{n}^{T} β^{0} = 0 for at most N (X) of the x_{n}’s, (10), (11) and Lemma 2(b) entail

0 ≥ N − M − N (X) − M,

hence M ≥ (N − N (X))/2, and consequently, in view of Proposition 1,

ε^{∗}(β̂, y, X) ≥ \frac{1}{N} ⌊\frac{N − N (X) + 1}{2}⌋ = \frac{M(X, 0)}{N}.

Upper bound. We consider the case r = 0 first. Here we see at once that the upper bound (1) and Proposition 1 yield even that

ε^{∗}(β̂, y, X) ≤ \frac{1}{N} ⌊\frac{N − N (X) + 1}{2}⌋ = \frac{M(X, 0)}{N}.

Now, let r ∈ (0, 1]. Suppose that M = M(X, r) + 1. If N (X) = N, the upper bound (1) shows that there is nothing to prove; hence suppose that N (X) < N. By Lemma 3, there is a set E ⊆ {1, 2, …, N}, with card E = M, and β^{1} ≠ 0 such that

∑_{n∈E} |x_{n}^{T} β^{1}|^{r} > ∑_{n∉E} |x_{n}^{T} β^{1}|^{r}.  (12)

Without restriction of generality we may now assume that E = {N − M + 1, N − M + 2, …, N}. Let β^{k} = kβ^{1}. Define y^{k} to satisfy y_{n}^{k} = y_{n} for n = 1, 2, …, N − M and y_{n}^{k} = x_{n}^{T} β^{k} for n ∈ E.

Suppose that there is a compact K such that β̃^{k} = β̂(y^{k}, X) ∈ K for all k. Then,

0 < d_{k} = D(β^{k}, y^{k}, X) − D(β̃^{k}, y^{k}, X)

= ∑_{n=1}^{N−M} φ(y_{n} − x_{n}^{T} β^{k}) − ∑_{n=1}^{N−M} φ(y_{n} − x_{n}^{T} β̃^{k})

+ ∑_{n=N−M+1}^{N} φ(0) − ∑_{n=N−M+1}^{N} φ(x_{n}^{T} β^{k} − x_{n}^{T} β̃^{k}).

Since β̃^{k}, and consequently x_{n}^{T} β̃^{k} are in a compact set, dividing by φ(k) and letting k → ∞ yields, in view of (A) and Lemma 2(a), that

0 ≤ lim_{k→∞} \frac{d_{k}}{φ(k)}

= ∑_{n=1}^{N−M} lim_{k→∞} \frac{φ (k (x_{n}^{T} β^{1} − \frac{1}{k}y_{n}))}{φ(k)} − ∑_{n=N−M+1}^{N} lim_{k→∞} \frac{φ(k(x_{n}^{T} β^{1} − \frac{1}{k}x_{n}^{T} β̃^{k}))}{φ(k)}

= ∑_{n=1}^{N−M} |x_{n}^{T} β^{1}|^{r} − ∑_{n=N−M+1}^{N} |x_{n}^{T} β^{1}|^{r}.

This is in contradiction with (12); hence, ε^{∗}(β̂, y, X) ≤ M/N.

Proof of Proposition 2. For (a), see Resnick (1987, Proposition 0.7.a). Concerning (b): it is clear that (D2) implies (B). (D2) with r > 0 implies

lim_{t→∞} \frac{φ(t)}{c t^{r}} = 1,

thus for every u > 0 we have

lim_{t→∞} \frac{φ(u t)}{φ(t)} = lim_{t→∞} \frac{φ(u t)}{c (u t)^{r}} u^{r} \frac{c t^{r}}{φ(t)} = u^{r}

and hence (D) holds. (D2) with r = 0 implies

lim_{t→∞} \frac{φ(t)}{m log(t)} = 1,

hence for every u > 0,

lim_{t→∞} \frac{φ(u t)}{φ(t)} = lim_{t→∞} \frac{φ(u t)}{m log(u t)} \frac{m log(u) + m log(t)}{φ(t)} = 1

and (D) holds as well. Statement (c) is obvious. Finally, (C) yields that

\frac{φ(2t)}{φ(t)} ≤ 2 + \frac{L}{φ(t)}.

Passing to limit on both sides and using (D) and (B), we obtain that 2^{r} ≤ 2; hence r ≤ 1, proving (d).

The following sequence of lemmas proves Theorem 3.

Lemma 4. Suppose that β̂ is of uniform variation. Then for all y ∈ ℝ^{N},

ε^{∗}(β̂, y, X) ≤ ε^{∗}(β̂, 0, X).

Proof. Let M = Nε^{∗}(β̂, 0, X); then there is a sequence ỹ^{k} such that (without restricting generality) ỹ_{n}^{k} = 0 for n = 1, 2, …, N − M, and

∥β̂(ỹ^{k}, X)∥ → ∞.  (13)

Given y, let δ = ∥y−0∥. Let y^{k} be the vector with components y_{n}^{k} = y_{n}+ỹ_{n}^{k} for n = 1, 2, …, N. Since

∥y^{k} − ỹ^{k}∥ = ∑_{n=1}^{N} y_{n}^{2} = ∥y − 0∥ = δ,

the uniform variation of β yields that there is K > 0 and β̂(y^{k}, X) such that

∥β̂(y^{k}, X) − β̂(ỹ^{k}, X)∥ ≤ K

for all k. Thus, ∥β̂(y^{k}, X)∥ → ∞ by (13), so that ε^{∗}(β̂, y, X) ≤ M/N, proving the lemma.

Lemma 5. For any X, ε^{∗}(β̂_{1}, 0, X) ≤ M(X, 1)/N.

Proof. Let M = M(X, 1). By the definition of M(X, 1), there is a β^{1} ≠ 0 and E with card E = M such that for β = β^{1},

∑_{n∈E} |x_{n}^{T} β| ≥ ∑_{n∉E} |x_{n}^{T} β|.  (14)

Then (14) holds, with the same E, also for β = β^{k} = kβ^{1}, for all k ∈ ℕ. Without restriction of generality we may again suppose that E = {N − M + 1, N − M + 2, …, N}.

For k ∈ ℕ, let y_{n}^{k} = 0 for n = 1, 2, …, N − M and y_{n}^{k} = x_{n}^{T} β^{k} otherwise. For the L_{1} estimator, φ(u) = φ_{1}(u) = |u|; by (14),

\begin{aligned}D(β^{k}, y^{k}, X) & − D(0, y^{k}, X) \\ & = ∑_{n=1}^{N−M} |x_{n}^{T} β^{k}| − ∑_{n=N−M+1}^{N} |x_{n}^{T} β^{k}| ≤ 0. \end{aligned}

By the convexity of the argmin set, there is a β̃^{1} minimizing D(β, y^{1}, X) which is equal neither to 0 nor to β^{1}. It is easily seen, directly from the definition, that the L_{1} estimator is scale equivariant: β̂(sy, X) = sβ̂(y, X). Therefore, β̃^{k} = kβ̃^{1} minimizes D(β, y^{k}, X). Since ∥β̃^{k}∥ → ∞, the lemma follows.

The proof of the uniform variation of the L_{1} estimator uses the idea of directional derivatives, borrowed from the proof of Lemma 5.3 of He et al. (1990). Define

S_{b}(α) = ∑_{n=1}^{N} |y_{n} − x_{n}^{T} (β + αb)|,
R = {n: y_{n} = x_{n}^{T} β}

For the directional derivative

S′_{b}(0) = lim_{α↓0} \frac{S_{b}(α) − S_{b}(0)}{α},

we have

\begin{matrix}S′_{b}(0) = − ∑_{n∉R} sign(y_{n} − x_{n}^{T} β) x_{n}^{T} b + ∑_{n∈R} |x_{n}^{T} b|, \\ S′_{b}(0) α ≤ S_{b}(α) − S_{b}(0), \end{matrix}

and S′_{b}(0) > 0 whenever α_{0} exists such that S_{b}(α) > S_{b}(0) for all 0 < α < α_{0}. Define, analogously to He et al. (1990), page 1208,

S(b, R, X) = {s = (s_{n})_{n∉R} ∈ {−1, 1}^{N−card R}:

− ∑_{n∉R} s_{n} x_{n}^{T} b + ∑_{n∈R} |x_{n}^{T} b| > 0},

g(b, R, X) = min_{s∈S(b,R,X)}{− ∑_{n∉R} s_{n} x_{n}^{T} b + ∑_{n∈R} |x_{n}^{T} b|},
c(R, X) = min{g(b, R, X): ∥b∥ = 1},
c(X) = min{c(R, X): R ⊂ {1, 2, …, N}}.

We have that g(b, R, X) > 0, c(R, X) > 0, c(X) > 0.

Lemma 6. The L_{1} estimator is of uniform variation.

Proof. Fix δ > 0 and y = (y_{1}, y_{2}, …, y_{N})^{T} ∈ ℝ^{N}. Take any y^{0} ∈ ℝ^{N} with |y_{n}^{0} −y_{n}| ≤ δ for all n = 1, 2, …, N and any β^{0} ∈ β̂_{1}(y^{0}, X). We shall prove that there exists β ∈ β̂_{1}(y, X) with

∥β^{0} − β∥ ≤ \frac{2 N δ}{c(X)}.

Assume the contrary: that for all β ∈ β̂_{1}(y, X) we have ∥β^{0} − β∥ > 2Nδ/c(X). Then β^{0} ∉ β̂_{1}(y, X). Since β̂_{1}(y, X) is a convex and closed subset of ℝ^{p}, there exists β ∈ β̂_{1}(y, X) such that β + α(β^{0} − β) ∉ β̂_{1}(y, X) for all α ∈ (0, 1]. For b = β^{0} − β define S_{b}(α) as above. Then we have S_{b}(α) > S_{b}(0) for all α ∈ (0, 1] and therefore S′_{b}(0) > 0. This implies

∑_{n=1}^{N} |y_{n}^{0} − x_{n}^{T} β^{0}| ≥ ∑_{n=1}^{N} |y_{n} − x_{n}^{T} β^{0}| − ∑_{n=1}^{N} |y_{n}^{0} − y_{n}|

≥ S_{b}(1) − Nδ ≥ S_{b}(0) + S′_{b}(0) − Nδ ≥ S_{b}(0) + c(X) ∥β^{0} − β∥ − Nδ

> ∑_{n=1}^{N} |y_{n} − x_{n}^{T} β| + Nδ

≥ ∑_{n=1}^{N} |y_{n}^{0} − x_{n}^{T} β|

—a contradiction to β^{0} ∈ β̂_{1}(y^{0}, X).

Proof of Proposition 3. Set M = ⌊(1 + min_{i=1,...,p} N_{i})/2⌋. First assume that r = 1. Without loss of generality we can assume that N_{1} = min_{1≤i≤p} N_{i} and x_{n} = χ_{1} for n = 1, …, N_{1}. Then there exists β ≠ 0 with χ_{i}^{T} β = 0 for i = 2, …, p such that

∑_{n=M+1}^{N} |x_{n}^{T} β| − ∑_{n=1}^{M} |x_{n}^{T} β| = (N_{1} − M)||χ_{1}^{T} β| − M|χ_{1}^{T} β| ≤ 0.

Hence, we have M(X, 1) ≤ ⌊(1 + min_{i} N_{i})/2⌋. Now consider any β ≠ 0 and any E ⊂ {1, …, N} with card E = M − 1. There exists α_{1}, α_{2}, …, α_{p} and β_{1}, β_{2}, …, β_{p} ≠ 0 with χ_{i}^{T} β_{j} = 0 for i ≠ j and β = α_{1}β_{1} + ⋯ + α_{p}β_{p} such that |χ_{i}^{T} β| = |α_{i}| |χ_{i}^{T} β_{i}| for i = 1, …, p. Let j = arg max_{i=1,...,p} |α_{i}| |χ_{i}^{T} β_{i}|. Then

∑_{n∉E} |x_{n}^{T} β| − ∑_{n∈E} |x_{n}^{T} β|
≥ ∑_{i≠j} N_{i} |α_{i}| |χ_{i}^{T} β_{i}| + (N_{j} − M + 1)|α_{j}| |χ_{j}^{T} β_{j}|
− (M − 1)|α_{j}| |χ_{j}^{T} β_{j}| > 0.

Observing that N (X) = N − N_{1} proves the proposition for r = 1. Proposition 1 provides the proposition for every r ∈ [0, 1].

Proof of Proposition 5. Equality. For every E with card E = M ≤ N/2 the existence of β satisfying (14) is equivalent with the existence of β_{1} such that

∑_{n∉E} |β_{1} + t_{n}| ≤ ∑_{n∈E} |β_{1} + t_{n}|.  (15)

But if β_{1} and E with card E = M exist such that (15) is satisfied, then (15) holds either for E = {1, …, M} and β_{0} = −t_{N} or for E = {N − M + 1, …, N} and β_{0} = −t_{1}.

Upper bound. Ellis and Morgenthaler showed in their Proposition 4.1 that 1/4 is an upper bound for the breakdown point of the L_{1} estimator if N = 4K with K ∈ ℕ. Theorem 3 says that M(X, 1)/N is the breakdown point of the L_{1} estimator; hence, the proposed upper bound holds for N = 4K. To prove the assertion for N = 4K + k with k = 1, 2, 3 assume that M(X, 1) > ⌊(N + 3)/4⌋ = K + 1. Then the already proved first part of Proposition 5 (equality) yields for M = K + 1 that

\begin{aligned}& ∑_{n=1}^{N−M}(t_{n} − t_{1}) > ∑_{n=N−M+1}^{N}(t_{n} − t_{1}) \\ and & ∑_{n=M+1}^{N}(t_{N} − t_{n}) > ∑_{n=1}^{M}(t_{N} − t_{n}). \end{aligned}  (16)

Let L ∈ {1, 2, 3} such that N + L = 4(K + 1). Consider the extended design X^{∗} = (x_{1}^{∗}, x_{1}^{∗}, …, x_{N+L}^{∗})^{T} given by x_{n}^{∗} = (1, t_{n}^{∗})^{T} = (1, t_{n})^{T} for n = 1, …, ⌊(N + 1)/2⌋, x_{n}^{∗} = (1, t_{n}^{∗})^{T} = (1, t_{⌊(N+1)/2⌋})^{T} for n = ⌊(N + 1)/2⌋ + 1, …, ⌊(N + 1)/2⌋ + L, and x_{n}^{∗} = (1, t_{n}^{∗})^{T} = (1, t_{n−L})^{T} for n = ⌊(N + 1)/2⌋ + L + 1, …, N + L. This extended design also satisfies t_{1}^{∗} ≤ t_{2}^{∗} ≤ ⋯ ≤ t_{N+L}^{∗}. Since M = K + 1 ≤ ⌊(N + 1)/2⌋ ≤ N − M, we have by (16)

\begin{aligned}∑_{n=1}^{N+L−M}(t_{n}^{∗} − t_{1}^{∗}) & = ∑_{n=1}^{N−M}(t_{n} − t_{1}) + ∑_{l=1}^{L}(t_{⌊(N+1)/2⌋} − t_{1}) \\ & > ∑_{n=N−M+1}^{N}(t_{n} − t_{1}) = ∑_{n=N+L−M+1}^{N+L}(t_{n}^{∗} − t_{1}^{∗}) \end{aligned}

and

\begin{aligned}∑_{n=M+1}^{N+L}(t_{N+L}^{∗} − t_{n}^{∗}) & = ∑_{n=M+1}^{N}(t_{N} − t_{n}) + ∑_{l=1}^{L}(t_{N} − t_{⌊(N+1)/2⌋}) \\ & > ∑_{n=1}^{M}(t_{N} − t_{n}) = ∑_{n=1}^{M}(t_{N+L}^{∗} − t_{n}^{∗}). \end{aligned}

This implies, in view of the equality part of Proposition 5, that M(X^{∗}, 1) > K + 1. But since N + L = 4(K + 1), we obtain from the result of Ellis and Morgenthaler (1992) the contradiction: M(X^{∗}, 1) ≤ K + 1.

Proof of Proposition 6. Demanding the existence of β = A^{T} β̃ for some β̃ ∈ ℝ^{2} such that (14) holds for β is a more stringent requirement than demanding an existence of a general β satisfying (14).

Appendix: computation of M(X, 1)

For computing M(X, 1) numerically, the following observations are useful. For E ⊆ {1, 2, …, N}, let

F_{E}(β) = \frac{∑_{n∈E} |x_{n}^{T} β|}{∑_{n=1}^{N} |x_{n}^{T} β|}.

Note that if N (X) < N, then M(X, 1) − 1 is equal to the maximal cardinality of a set E ⊂ {1, 2, …, N} such that max_{β} F_{E}(β) < 1/2. For c ≠ 0, F_{E}(cβ) = F_{E}(β); thus, since we can restrict the domain of maximization to a compact set

A = {β : ∑_{n=1}^{N} |x_{n}^{T} β| = 1} ,

the maximum is attained for every E. Let X be the set of all design points x_{n} (that is, multiple design points enter X only once). Let D be the set of all subsets D of X with the property that the linear space spanned by the elements of D is (p − 1)-dimensional. Let

D^{⊥} = {β: x_{n}^{T} β = 0 for all x_{n}^{T} ∈ D}

be the orthogonal complement of this space and let

B = ⋃_{D∈D}(A ∩ D^{⊥}).

Now, let S = {−1, 1}^{N}. For s ∈ S we define

A_{s} = {β ∈ A: |x_{n}^{T} β| = s_{n}x_{n}^{T} β for n = 1, 2, …, N} .

In other terms, if β ∈ A_{s}, then sign(x_{n}^{T} β) = s_{n} or 0.

Lemma 7. For every s ∈ S, the set A_{s} is compact and convex (possibly empty). All extremal points of A_{s} lie in B; F_{E} is linear on A_{s} for every E.

Proof. Since A_{s} ⊂ A, it is bounded; the properties determining A_{s} preserve under a passage to limit, hence A_{s} is closed. Convex combinations also remain in A_{s}; since

∑_{n=1}^{N} |x_{n}^{T} β| = ∑_{n=1}^{N} s_{n}x_{n}^{T} β,

all convex combinations of elements of A_{s} belong to A. Linearity of F_{E} on A_{s} follows in an analogous way.

Fix s ∈ S. Let β be an extremal point of A_{s} and let C be the set of all those x_{n} for which x_{n}^{T} β = 0. Suppose that the dimension of the linear space spanned by C does not exceed p − 2. Then the linear space spanned by C ∪ {∑_{n=1}^{N} s_{n}x_{n}} has dimension at most p − 1; consequently, there is a β̃ ≠ 0 such that x_{n}^{T} β̃ = 0 for all x_{n} ∈ C and ∑_{n=1}^{N} s_{n}x_{n}^{T} β̃ = 0. For all x_{n} ∈ X ∖ C, |x_{n}^{T} β| ≥ η for some η > 0; we can suppose that |x_{n}^{T} β̃| ≤ η/2 for all n = 1, 2, …, N, taking a suitable nonzero multiple of β̃ otherwise. As a consequence,

sign(x_{n}^{T} β + x_{n}^{T} β̃) = sign(x_{n}^{T} β) = sign(x_{n}^{T} β − x_{n}^{T} β̃)  (17)

for all x_{n} ∈ X ∖ C, and also for all x_{n} ∈ C. Therefore,

\begin{aligned}∑_{n=1}^{N} |x_{n}^{T} (β + β̃)| & = ∑_{n=1}^{N} s_{n}x_{n}^{T} (β + β̃) \\ & = ∑_{n=1}^{N} s_{n}x_{n}^{T} β + ∑_{n=1}^{N} s_{n}x_{n}^{T} β̃ = 1, \end{aligned}

and analogously ∑_{n=1}^{N} |x_{n}^{T} (β − β̃)| = 1. We obtain, in view of (17), that β is a convex combination of β + β̃ and β − β̃, both elements of A_{s}. This contradicts the extremality of β; hence, the space spanned by C has dimension at least p − 1. It cannot have dimension p since then x_{n}^{T} β = 0 for all x_{n} ∈ C would imply β = 0, a contradiction with the fact that β ∈ A. Thus, the dimension is p − 1, as had to be proved.

Proposition 7. For every E ⊆ {1, 2, …, N}, the maximum max_{β} F_{E}(β) is attained on some point of B, which satisfies

\frac{1}{2} card B ≤ \binom{card X}{p − 1}.  (18)

Proof. Since D^{⊥} is a one-dimensional subspace of ℝ^{p}, the set A ∩ D^{⊥} contains, for any D ∈ D, at most two elements; this proves (18). The remaining part of the statement follows from Lemma 7 and the fact that A = ⋃_{s∈S} A_{s}—since the maximum of a linear function over a compact convex set is attained in one of its extremal points.

Proposition 7 says that for computing M(X, 1), we have only to inspect β ∈ B. Note that, in fact, we have to consider only one β from each A∩D^{⊥}, the second one is −β, with the same |x_{n}^{T} β|’s for all n = 1, 2, …, N.

Acknowledgements

We are very grateful to Jana Jurečková for valuable suggestions and discussions, and to her, Xuming He and Stephen Portnoy for exhaustive replies to our queries. The authors express their thanks to Viktor Kurotschka and Andrej Pázman and to the Deutsche Forschungsgemeinschaft and Slovak Grant Agency for Science for supporting their mutual visits of the Free University and Comenius University.

References

Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. Cambridge University Press, Cambridge.

Ellis, S. P. and Morgenthaler, S. (1992). Leverage and breakdown in L_{1} regression. J. Amer. Statist. Assoc. 87, 143–148.

Hampel, F. R., Ronchetti, E. M., Rousseeuw, P. J. and Stahel, W. A. (1986). Robust Statistics—The Approach Based on Influence Functions. Wiley, New York.

He, X., Jurečková, J., Koenker, R. and Portnoy, S. (1990). Tail behavior of regression estimators and their breakdown points. Econometrica 58, 1195–1214.

Hoaglin, D. C., Mosteller, F. and Tukey, J. W. (eds.) (1983). Understanding Robust and Exploratory Data Analysis. Wiley, New York.

Huber, P. J. (1981). Robust Statistics. Wiley, New York.

Huber, P. J. (1984). Finite sample breakdown of M- and P-estimators. Ann. Statist. 12, 119–126.

Jurečková, J. (1981). Tail-behavior of location estimators. Ann. Statist. 9, 578–585.

Maronna, R. A., Bustos, O. H. and Yohai, V. J. (1979). Bias- and efficiencyrobustness of general M-estimators for regression with random carriers. In: Smoothing Techniques for Curve Estimation, eds. T. Gasser and M. Rosenblatt, Lecture Notes in Mathematics 757, Springer, Berlin, 91–116.

Maronna, R. A., Yohai, V. J. and Zamar, R. J. (1993). Bias-robust regression estimation: A partial survey. In: New Directions in Statistical Data Analysis and Robustness, eds. S. Morgenthaler, E. Ronchetti and W. A. Stahel, Birkhäuser, Basel, 157–176.

Mili, L. and Coakley, C. W. (1993). Robust estimation in structured linear regression. Technical Report No. 93-13, Department of Statistics, Virginia Polytechnic Institute and State University. (To appear in Ann. Statist.)

Mizera, I. (1996). Weak continuity of redescending M-estimators of location with an unbounded objective function. In: PROBASTAT’94, Proceedings of the Second International Conference on Mathematical Statistics, Tatra Mountains Mathematical Publications 7, 343–347.

Morgenthaler, S. and Tukey, J. W. (1991). Configural Polysampling. Wiley, New York.

Müller, Ch. H. (1995). Breakdown points for designed experiments. J. Statist. Plann. Inference. 45, 413–427.

Müller, Ch. H. (1996a). High breakdown point designs. In: Robust Statistics, Data Analysis, and Computer Intensive Methods, In Honor of Peter Huber’s 60th Birthday, ed. H. Rieder, Lecture Notes in Statistics 109, Springer, New York, 353–360.

Müller, Ch. H. (1996b). Optimal breakdown point maximizing designs. In: PROBASTAT’94, Proceedings of the Second International Conference on Mathematical Statistics, Tatra Mountains Mathematical Publications 7, 79–85.

Resnick, S. I. (1987). Extreme Values, Regular Variation, and Point Processes. Springer, New York.

Rousseeuw, P. J. and Leroy, A. M. (1987). Robust Regression and Outlier Detection. Wiley, New York.

Comenius University Department of Probability and Statistics, Mlynská dolina SK-84215 Bratislava Slovakia e-mail: mizera@fmph.uniba.sk Free University of Berlin Department of Mathematics Arnimallee 2–6 D-14195 Berlin Germany e-mail: mueller@math.fu-berlin.de