Optimal breakdown point maximizing designs

Christine H. Müller Free University of Berlin, Department of Mathematics, Arnimallee 2-6, D-14195 Berlin, Germany, e-mail: mueller@math.fu-berlin.de

Abstract. In linear models the breakdown point of an estimator depends strongly on the underlying design. This holds in particular for high breakdown point estimators as the least median of squares estimator or least trimmed squares estimators. It could be shown that the breakdown point is maximized if the number of regressors which lie in a subspace is minimized. This means in particular that the number of repetitions of experimental conditions should be minimized. Usually this leads to designs which are very different from the classically optimal designs. But in some situations breakdown point maximizing designs can be found which are also optimal in the classical sense. In this paper two examples are given where breakdown point maximizing designs are also classically optimal.

AMS Mathematical Subject Classification (1991): 62K05, 62G35.

Key words: Linear model, breakdown point, trimmed L_{p}-estimator, optimal design.

1 Introduction

We regard a general linear model

y = X_{d}β + z

where y = (y_{1}, ..., y_{N})′ ∈ IR^{N} is the observation vector, X_{d} = (x(t_{1}), ..., x(t_{N}))′ ∈ IR^{N×r} the known design matrix, x : T → IR^{r} the known regression function, d = (t_{1}, ..., t_{N})′ ∈ T^{N} the design, β ∈ IR^{r} the unknown parameter vector and z = (z_{1}, ..., z_{N})′ ∈ IR^{N} the error vector. We assume that the experimenter can choose freely the experimental conditions t_{n}, n = 1, ..., N, from the experimental region T .

If we have an estimator β̂ : IR^{N} × T^{N} → IR^{r} for the unknown parameter β then we can regard as a robustness measure its breakdown point which is the minimal fraction of outliers which can provide an arbitrarily high bias of the estimator. Originally the breakdown point of an estimator β̂ at a finite sample (y, d) was defined by Donoho and Huber (1983) by allowing also outliers in the experimental conditions. In the literature mainly this definition is used by assuming that the experimental conditions are given per random (see for example Rousseeuw and Leroy (1987), Coakley (1991), Mili and Coakley (1993)). But for designed experiments the experimental conditions are given by the experimenter so that outlying experimental conditions can not appear. Therefore here the breakdown point at a given sample (y, d) is defined as in Ellis and Morgenthaler (1992) and Müller (1993) by

(1.1) ϵ^{∗}(β̂, y, d) := min\{\frac{M}{N}; M ∈ IN and sup_{\overline{y}∈Y_{M} (y)} |β̂(\overline{y}, d) − β̂(y, d)| = ∞ \},

where Y_{M}(y) is the set of all contaminated observation vectors \overline{y} ∈ IR^{N} for which m(1) < ... < m(N − M) exists so that \overline{y}_{m(i)} = y_{m(i)} for all i ∈ \{1, ..., N − M\}. By regarding the minimum possible breakdown point for an estimator β̂ at a given design d, i.e.

ϵ^{∗}(β̂, d) := min{ϵ^{∗}(β̂, y, d); y ∈ IR^{N}},

we get a breakdown point which is independent of the observation vector y.

The breakdown point of the classically optimal estimator for β, the least squares estimator (LS estimator) β̂_{LS}, is in the original definition of Donoho and Huber (1983) as well as in the definition of (1.1) equal to \frac{1}{N}. To improve the breakdown point we can regard the h-trimmed L_{p}-estimators which were regarded in Müller (1993) and which generalize the least median of squares estimator and the least trimmed squares estimators (see Rousseeuw and Leroy (1987), Coakley (1991), Coakley and Mili (1993), Mili and Coakley (1993)). A h-trimmed L_{p}-estimator is given by

β̂_{h}(y, d) = arg min_{β∈IR^{r}} ∑_{n=1}^{h} w_{n} |y_{(n)} − x(t_{(n)})′β|^{p}

where w_{1}, ..., w_{N} > 0, p > 0 and |y_{(1)} − x(t_{(1)})′β|, ..., |y_{(N)} − x(t_{(N)})′β| are the ordered residuals for a given β, i.e. we have |y_{(1)} − x(t_{(1)})′β| ≤ ... ≤ |y_{(N)} − x(t_{(N)})′β|.

As Müller (1993) has shown for h not too large the breakdown point of a h-trimmed L_{p}-estimator depends only on the trimming value h, on the design d and the sample size N, and it does not depend on p and the weights w_{n}. For fixed h and N the breakdown point depends on the design d only via N(d) and increases if N(d) decreases. Thereby N(d) is the maximal number of regressors x(t_{n}) which are lying in a (r − 1)-dimensional subspace of IR^{r}, i.e.

N(d) := max{N_{V}; V is a (r − 1) − dimensional subspace of IR^{r}},

where N_{V} := ∑_{n=1}^{N} 1_{V} (x(t_{n})). In particular for [\frac{N+N(d)+1}{2}] ≤ h ≤ [\frac{N+N(d)+2}{2}] the htrimmed L_{p}-estimator maximizes the breakdown point within all regression equivariant estimators with a maximum breakdown point of

ϵ^{∗}(d) := ϵ^{∗}(β̂_{h}, d) = \frac{1}{N} [\frac{N − N(d) + 1}{2}] .

Hence in Müller (1993) a breakdown point maximizing design within a class Δ of designs is defined as

d^{∗} = arg min{N(d); d ∈ Δ}.

Because we always have N(d) ≥ r − 1 a design d^{∗} with N(d^{∗}) = r − 1, i.e. a design where the regressors x(t_{1}), ..., x(t_{N}) are in general position (see Rousseeuw and Leroy (1987)), is breakdown point maximizing.

For example for linear regression N(d) is the maximal number of repetitions of a experimental condition t_{n} so that a design with no repeated experimental conditions t_{n} satisfies N(d) = 1 and therefore is breakdown point maximizing. But these breakdown point maximizing designs are very different from the classically optimal design which has \frac{N}{2} repetitions of t = −1 and \frac{N}{2} repetitions of t = 1 if T = [−1, 1] is the experimental region. Hence for linear regression we have a contradiction between maximum breakdown point and classic optimality.

But there are other problems for which it is possible to derive designs which are breakdown point maximizing as well as classically optimal. In this paper this is demonstrated for two problems, namely for the multiple regression on balls in Section 2 and for a weighing problem in Section 3.

2 Multiple regression on balls

In a r-dimensional multiple regression problem without constant term the observations are given by

y_{n} = x(t_{n})′β + z_{n} = ∑_{i=1}^{r} β^{i}t_{n}^{i} + z_{n}

for n = 1, ..., N, i.e. β = (β^{1}, ..., β^{r})′ ∈ IR^{r} and x(t) = t = (t^{1}, ..., t^{r})′. Here we assume that the experimental region is a ball, i.e.

t_{n} ∈ T = {t ∈ IR^{r}; ∑_{i=1}^{r}(t^{i})^{2} ≤ R^{2}}.

Without loss of generality we can assume that the radius of the ball is R = 1. Then the equivalence theorems (see for example Pukelsheim (1993)) provide that a design d ∈ T^{N} satisfying X′_{d}X_{d} = \frac{N}{r} E_{r}, where E_{r} denotes the r × r-identity matrix, is A-, D- and Eoptimal in Δ = T^{N}, i.e. classically optimal. In particular if the sample size N satisfies N = K r, where K is an integer, then the design given by d = (E_{r}|...|E_{r})′, where the identity matrix E_{r} is repeated K times, is classically optimal because X′_{d}X_{d} = \frac{N}{r} E_{r}. This design has minimum support but for r > 1 it provides a low maximum breakdown point of

ϵ^{∗}(d) = \frac{1}{N} [\frac{N − (r − 1)K + 1}{2}] = \frac{1}{N} [\frac{N − (r − 1)\frac{N}{r} + 1}{2}] ⟶^{N→∞} \frac{1}{2r}

because N(d) = (r − 1)K = N \frac{r−1}{r}. But instead of repeating the identity matrix K times we can use K different orthonormal matrices O_{1}, ..., O_{K} ∈ IR^{r×r} with O_{k} O′_{k} = E_{r} for k = 1, ..., K so that the r unit vectors are rotated to different positions by keeping the angles between them. It is always possible to find K positions so that the design d^{∗} with d^{∗} = (O_{1}|...|O_{K})′ = X_{d} satisfies N(d^{∗}) = r − 1 so that d^{∗} is breakdown point maximizing in Δ = T^{N}. In particular for r = 2 it is always possible to find N = 2K different experimental conditions t_{n} with |t_{n}| = 1 so that every t_{n} is othogonal to one another experimental condition t_{m} and no t_{n}, t_{m} with n ≠ m are lying on a line through the origin. Hence we have the following lemma.

Lemma 2.1 If d^{∗} = (O_{1}|...|O_{K})′ with O_{k} O′_{k} = E_{r} for k = 1, ..., K and N(d^{∗}) = r − 1 then d^{∗} is classically optimal in T^{N} as well as breakdown point maximizing in T^{N} with maximum breakdown point of

ϵ^{∗}(d^{∗}) = \frac{1}{N} [\frac{N − r + 2}{2}] ⟶^{N→∞} \frac{1}{2}.

A design d^{∗} = (O_{1}|...|O_{K})′ with O_{k} O′_{k} = E_{r} for k = 1, ..., K and N(d^{∗}) = r − 1 always exists.

3 Weighing designs for four objects

Here we regard the problem of weighing four objects with a chemical balance. The weights β^{1}, ..., β^{4} of the four objects are unknown and we can use N weighing realizations for determining the weights of the objects. For each weighing realization for each object we have to decide on which side of the balance the object should be put. Hence for the n’th weighing realization we have to choose

t_{n} ∈ T = {−1, 1}^{4}

where t_{n}^{i} = −1 and t_{n}^{i} = 1 means that in the n’th realization the i’th object is put on the lefthand side or righthand side of the balance, respectively. Then the result of the n’th weighing realization will be

y_{n} = x(t_{n})′β + z_{n} = β^{1}t_{n}^{1} + ... + β^{4}t_{n}^{4} + z_{n}

where β = (β^{1}, β^{2}, β^{3}, β^{4})′ ∈ IR^{4}, x(t) = t = (t^{1}, t^{2}, t^{3}, t^{4})′ ∈ T and z_{n} is an error which may be also an outlier if some extraordinary shake happens.

If a design d satisfies X′_{d}X_{d} = N E_{4}, where E_{4} denotes the 4 × 4 identity matrix, then as for multiple regression on balls d is A-, D- and E-optimal in Δ = T^{N}, i.e. classically optimal (see Section 2). In particular if the sample size is N = 4K, where K is an integer, then a classically optimal design is d = (X_{0}|...|X_{0})′, where the matrix X_{0} = (1_{4}|X)′ ∈ IR^{4×4} is repeated K-times, 1_{4} = (1, 1, 1, 1)′ and

X = ( \begin{matrix}1 & 1 & 1 \\ 1 & −1 & −1 \\ −1 & 1 & −1 \\ −1 & −1 & 1 \end{matrix} ) .

The design d has minimum support but it provides a maximum breakdown point of

ϵ^{∗}(d) = \frac{1}{N} [\frac{N − 3K + 1}{2}] ⟶^{N→∞} \frac{1}{8}

because N(d) = 3K = \frac{3 N}{4} . In the case of N = 8 L, where L is an integer, the breakdown is improved by a design d^{∗} = (X_{1}|...|X_{1})′, where the matrix X_{1} = ((1_{4}|X)′|(1_{4}|−X)′) ∈ IR^{4×8} is repeated L times. In Δ = T^{N} this design is breakdown point maximizing and classically optimal which shows the following lemma.

Lemma 3.1 If N = 8 L and d^{∗} = (X_{1}|...|X_{1})′, where L is an integer and X_{1} = ((1_{4}|X)′|(1_{4}| − X)′) is repeated L times, then d^{∗} is classically optimal in T^{N} as well as breakdown point maximizing in T^{N} with maximum breakdown point of

ϵ^{∗}(d^{∗}) = \frac{1}{N} [\frac{N − 4L + 1}{2}] ⟶^{N→∞} \frac{1}{4}.

Proof. Let be A the set of columns of (1_{4}|X)′ and B the set of columns of (1_{4}| − X)′. Then we have for every a ∈ A and b ∈ B the property (a′b)^{2} = 4. Hence for every a ∈ A and b_{1}, b_{2}, b_{3} ∈ B with b_{1} ≠ b_{2} ≠ b_{3} ≠ b_{1} we have det((a, b_{1}, b_{2}, b_{3})′(a, b_{1}, b_{2}, b_{3})) ≠ 0 so that a, b_{1}, b_{2}, b_{3} are linearly independent. Similarly every b ∈ B and a_{1}, a_{2}, a_{3} ∈ B with a_{1} ≠ a_{2} ≠ a_{3} ≠ a_{1} are linearly independent. Hence it is impossible that more than 4 elements of A ∪ B are lying in a subspace of IR^{4}, i.e. N(d^{∗}) ≤ 4 L. On the other hand for every a_{1}, a_{2} ∈ A there exists b_{1}, b_{2} ∈ B with a_{1}+b_{1} = (2, 0, 0, 0)′ = a_{2}+b_{2} so that a_{1}, a_{2}, b_{1}, b_{2} are linearly dependent. Hence we have N(d^{∗}) = 4 L = \frac{N}{2} . Moreover if additionally N = 6 J for some integer J then for every d^{6} = (X_{2}|...|X_{2})′, where X_{2} = (c_{1}, ..., c_{6}) is repeated J times and \{c_{1}, ..., c_{6}\} ⊂ A ∪ B, we have N(d^{6}) = 4 J = \frac{2 N}{3} > \frac{N}{2} = N(d^{∗}). If additionally N = 5 J for some integer J then for every d^{5} = (X_{3}|...|X_{3})′, where X_{3} = (c_{1}, ..., c_{5}) is repeated J times and \{c_{1}, ..., c_{5}\} ⊂ A ∪ B, we have N(d^{5}) ≥ 3 J = \frac{3 N}{5} > \frac{N}{2} = N(d^{∗}). The same holds for designs d^{4} and d^{7} with 4 and 7 different experimental conditions. Also designs which are a mixture of designs d^{4}, d^{5}, d^{6}, d^{7} and d^{∗} always satisfy N(d) ≥ N(d^{∗}) so that d^{∗} is breakdown point maximizing. □

Note that in many weighing problems it is also allowed that in some weighing realizations some of the objects do not participate so that for four objects the experimental region would be T_{0} = {−1, 0, 1}^{4}. But in T_{0}^{N} there is no breakdown point maximizing design which is also classically optimal.

Also note that the design used in Lemma 3.1 can be constructed by product designs (see for example Schwabe (1992)) so that for more than four objects breakdown point maximizing designs will be given by product designs. Often the product designs are criticized that they have too much support points. But for the breakdown point this is an advantage so that the breakdown point provides a justification of product designs.

References

[1] Coakley, C.W. (1991). Breakdown points under simple regression with replication. Technical Report No. 91-21, Department of Statistics, Virginia Polytechnic Institute and State University.

[2] Coakley, C.W. and Mili, L. (1993). Exact fit points under simple regression with replication. Statist. Probab. Lett. 17, 265-271.

[3] Donoho, D.L. and Huber, P.J. (1983). The notion of breakdown point. In A Festschrift for Erich L. Lehmann (P.J. Bickel, K.A. Doksum and J.L. Hodges, Jr.,eds.) 157-184. Wadsworth, Belmont, Calif.

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

[5] 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.

[6] Müller, Ch.H. (1993). Breakdown points for designed experiments. Preprint No. A-93-29, Freie Universität Berlin, Fachbereich Mathematik und Informatik. To appear in J. Statist. Plann. Inference.

[7] Pukelsheim, F. (1993). Optimal Design of Experiments. John Wiley, New York.

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

[9] Schwabe, R. (1992). Optimum designs for multi-factor models. Habilitation thesis. Freie Universität Berlin.