High breakdown point designs

Christine H. Müller Freie Universität Berlin, Fachbereich Mathematik und Informatik, WE 1, Arnimallee 2-6, D-14195 Berlin, Germany, e-mail: mueller@math.fu-berlin.de

Abstract. A linear model is assumed where the experimental conditions are given by the experimenter so that they are without gross errors. For this situation we regard h-trimmed L_{p}-estimators which generalize the least median of squares estimator and the least trimmed squares estimators. The breakdown point of these estimators depends strongly on the underlying design and breakdown point maximizing estimators can be derived within these estimators. Also breakdown point maximizing designs can be derived. But these designs are often very different from the classically optimal designs which ensure efficiency also for robust procedures. Therefore we regard compromises providing high breakdown point and high efficient designs.

1 Breakdown points for designed experiments

We regard a general linear model

y = Xβ + z

where y = (y_{1}, ..., y_{N})′ ∈ IR^{N} is the observation vector, X = (x_{1}, ..., x_{N})′ ∈ X^{N} ⊂ IR^{N×r} the known design matrix, briefly also called 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 x_{n}, n = 1, ..., N, from the experimental region X.

If we have an estimator β̂ : IR^{N} × X^{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, X) was defined by Donoho and Huber (1983) by allowing also outliers in the experimental conditions as

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

where Y_{M}(y, X) is the set of all contaminated samples (\overline{y}, \overline{X}) ∈ IR^{N} × X^{N} for which m(1) < ... < m(N − M) exist so that (\overline{y}_{m(i)}, \overline{x}_{m(i)}) = (y_{m(i)}, x_{m(i)}) for all i ∈ \{1, ..., N − M\}.

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, X) is defined as in Ellis and Morgenthaler (1992) and Müller (1993) by

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

where Y_{M}(y) is the set of all contaminated observation vectors \overline{y} ∈ IR^{N} for which m(1) < ... < m(N −M) exist 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 X, i.e.

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

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

2 Breakdown point maximizing estimators

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.2) equal to \frac{1}{N}. To improve the breakdown point alternative estimators were proposed. One is the least median of squares estimator (LMS estimator) β̂_{LMS} which minimizes the median of squared residuals instead of the sum of squared residuals, i.e. which is given by

β̂_{LMS}(y, X) = arg min_{β∈IR^{r}} med_{n=1,...,N}(y_{n} − x′_{n}β)^{2}

(see Rousseeuw (1984), Rousseeuw and Leroy (1987)).

But if we have a linear regression model y_{n} = β_{0} + β_{1}t_{n} + z_{n} with t_{n} ∈ [−1, 1] and x_{n} = (1, t_{n})′ and use the classically optimal design (A-, D-, E-optimal) design X^{0} with \frac{N}{2} observations at x = (1, −1)′ and \frac{N}{2} observations at x = (1, 1)′ (see also Section 3) then the breakdown point of the LMS estimator is ϵ^{∗}(β̂_{LMS}, X^{0}) = \frac{1}{N} because the exact fit point satisfies ϵ^{∗}(β̂_{LMS}, X^{0}β, X^{0}) = \frac{1}{N}. I.e. at X^{0} the breakdown point of the LMS estimator coincides with the breakdown point of the LS estimator.

To improve the breakdown point at the classically optimal design X^{0} we can regard a generalization of the LMS estimator, namely the h-trimmed L_{p}-estimators which were regarded in Müller (1993) and which also generalize the least trimmed squares estimators (see also Rousseeuw and Leroy (1987), Coakley (1991), Coakley and Mili (1992), Mili and Coakley (1993)). A h-trimmed L_{p}-estimator is given by

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

where w_{1}, ..., w_{N} > 0, p > 0 and |y_{(1)} − x′_{(1)}β|, ..., |y_{(N)} − x′_{(N)}β| are the ordered residuals for a given β, i.e. we have |y_{(1)} − x′_{(1)}β| ≤ ... ≤ |y_{(N)} − x′_{(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 X 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 X only via N(X) and increases when N(X) decreases. Thereby N(X) is the maximal number of experimental conditions x_{n} which are lying in a (r − 1)-dimensional subspace of IR^{r}, i.e.

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

where N_{V} := ∑_{n=1}^{N} 1_{V} (x_{n}) (compare also with the quantity Δ(Q) used in Davies (1993), (1994)). In particular for N(X) < h ≤ \frac{N+N(X)+1}{2} the breakdown point of the h-trimmed L_{p}-estimator is

ϵ^{∗}(β̂_{h}, X) = \frac{1}{N} (h − N(X)) (2.3)

and for [\frac{N+N(X)+1}{2}] ≤ h ≤ [\frac{N+N(X)+2}{2}] we have

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

where [z] := max{n ∈ IN; n ≤ z} (see Müller (1993)).

Every regession equivariant estimator, i.e. every estimator β̂ satisfying β̂(y + Xθ, X) = β̂(y, X) + θ for all y ∈ IR^{N} and θ ∈ IR^{r} as the h-trimmed L_{p}-estimators, has a breakdown point with

ϵ^{∗}(β̂, y, X) ≤ \frac{1}{N} [\frac{N − N(X) + 1}{2}]

for all y ∈ IR^{N} (see Müller (1993)). Hence the maximum breakdown point at the design X is

ϵ^{∗}(X) := max\{ϵ^{∗}(β̂, X); β̂ regression equivariant\} = \frac{1}{N} [\frac{N − N(X) + 1}{2}]

and is attained by h-trimmed L_{p}-estimators with [\frac{N+N(X)+1}{2}] ≤ h ≤ [\frac{N+N(X)+2}{2}] so that these h-trimmed L_{p}-estimators are breakdown point maximizing estimators.

3 Breakdown point maximizing designs

A breakdown maximizing design can be defined as a design X^{∗} which maximize the maximum breakdown point ϵ^{∗}(X) within a given class Δ of designs X, i.e.

X^{∗} = arg max{ϵ^{∗}(X); X ∈ Δ}.

Because the maximum breakdown point is a decreasing function of N(X) we also can define a breakdown point maximizing design as a design X^{∗} which minimizes N(X), i.e.

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

(see Müller (1993)). Because of (2.3) the breakdown point maximizing design maximizes not only the breakdown point of the breakdown point maximizing estimator but also the breakdown point of every h-trimmed L_{p}-estimator with N(X^{∗}) < h ≤ \frac{N+N(X^{∗})+1}{2}.

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

For example for linear regression N(X) is the maximal number of repetitions of a experimental condition x_{n} so that a design X^{∗} with no repeated experimental conditions x_{n} satisfies N(X^{∗}) = 1 and therefore is breakdown point maximizing. But these breakdown point maximizing designs are very different from the classically optimal design which minimizes some functional ϕ of the covariance matrix (X′X)^{−1} of the least squares estimator as the trace (A-optimality), the determinant (D-optimality) or the maximum eigenvalue (E-optimality) of (X′X)^{−1}. The equivalence theorems for A-, D- and E-optimality (see Pukelsheim (1993) p. 221, 212 and 181-182, respectively) provide that in Δ = X^{N} the A-, D- and Eoptimal design has \frac{N}{2} repetitions of x = (1, −1)′ and \frac{N}{2} repetitions of x = (1, 1)′ if X = \{1\}×[−1, 1] is the experimental region. Hence for linear regression we have a contradiction between maximum breakdown point and classic optimality.

This contradiction is in particular grave because classically optimal designs provide also high efficiency of some robust procedures. In particular rank-based estimators as regarded in Hössjer (1994) and Huber M-estimators have an asymptotic covariance matrix which coincides with the covariance matrix of the least squares estimator except for some constant which does not depend on the design (see Hössjer (1994), Bickel (1975), Yohai and Maronna (1979)). Also at A-optimal designs the trace of the asymptotic covariance matrix of the optimal robust Hampel-Krasker estimator is minimized (see Müller (1994)). Moreover the classically optimal design for linear regression with X = {1} × [−1, 1] maximizes the breakdown point of the L_{1}-estimator (see Ellis and Morgenthaler (1992)).

4 Combining high breakdown point and high efficiency

Estimators which combine high breakdown point and high efficiency can be easily constructed by one-step M-estimators

β̂(y, X) = β̂^{0}(y, X) + \frac{1}{N} ∑_{n=1}^{N} ψ(y_{n} − x′_{n}β̂^{0}(y, X), x_{n}),

where the initial estimator β̂^{0} is a high breakdown point estimator and the score function ψ provides high asymptotic efficiency. If the initial estimator is asymptotically normally distributed with convergence rate of N^{−1/2} as many h-trimmed L_{p}-estimators (see Hössjer (1994)) then the finite sample breakdown point of β̂ coincides with that of the initial estimator β̂^{0} and the asymptotic covariance matrix is only determined by the score function ψ (see Jurečková and Portnoy (1987)).

To find a design which combines high breakdown point and high efficiency is more difficult. There are situations where even designs exist which are classically optimal as well as breakdown point maximizing (see Müller (1994)) but these situations are rare. More typical is the situation of linear regression where classically optimal designs are very different from the breakdown point maximizing designs. In all these situations constrained problems will be a good compromise to combine high breakdown point and high asymptotic efficiency.

One constrained problem is to minimize a functional ϕ of the covariance matrix (X′X)^{−1} under the side condition that the breakdown point is not too bad, i.e.

X^{∗∗} = arg min\{ϕ((X′X)^{−1}); ϵ^{∗}(X) ≥ B, X ∈ Δ\} = arg min\{ϕ((X′X)^{−1}); N(X) ≤ \overline{B}, X ∈ Δ\}.

For the particular case that N(X) is the maximal number of repetitions as for linear regression this problem was already treated by Wynn (1982), Wierich (1985) and Fedorov (1989) by constructing optimal designs with bounded number of repetitions.

Another constrained problem is to maximize the breakdown point under the side condition that the functional ϕ of the covariance matrix (X′X)^{−1} is not too large, i.e.

X^{∗∗} = arg max{ϵ^{∗}(X); ϕ((X′X)^{−1}) ≤ B, X ∈ Δ} = arg min{N(X); ϕ((X′X)^{−1}) ≤ B, X ∈ Δ}.

In particular we can set

B = min{ϕ((X′X)^{−1}); X ∈ Δ}

so that we restrict ourselves to ϕ-optimal designs. This of course makes only sense if we have several ϕoptimal designs. For example for linear regression this makes no sense because the A-, D- and E-optimal design is unique. But there are other problems for which we have several classically optimal designs as the following examples show.

5 Examples

A) 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 whether it will participate and if it will participate on which side of the balance the object should be put. Hence for the n’th weighing realization we have to choose

x_{n} ∈ X = {−1, 0, 1}^{4}

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

y_{n} = x′_{n}β + z_{n} = β^{1}x_{n}^{1} + ... + β^{4}x_{n}^{4} + z_{n}

where β = (β^{1}, β^{2}, β^{3}, β^{4})′ ∈ IR^{4}, x_{n} = (x_{n}^{1}, x_{n}^{2}, x_{n}^{3}, x_{n}^{4})′ ∈ X and z_{n} is an error which may be also an outlier if some extraordinary shake happens. Then the equivalence theorems (see as in Section 3 for example Pukelsheim (1993)) provide that every design X ∈ X^{N} satisfying X′X = N E_{4}, where E_{4} denotes the 4 × 4-identity matrix, is A-, D- and E-optimal in Δ = X^{N}, i.e. classically optimal. In particular if the sample size is N = 8L, where L is an integer, then classically optimal designs are X = (X_{1}|...|X_{1})′ and X^{∗} = (X_{2}|...|X_{2})′, where the matrix X_{1} = (1_{4}|X_{0})′ ∈ IR^{4×4} is repeated 2L-times and the matrix X_{2} = ((1_{4}|X_{0})′|(1_{4}| − X_{0})′) ∈ IR^{4×8} is repeated L times. Thereby we have 1_{4} = (1, 1, 1, 1)′ and

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

The design X has minimum support but the maximum breakdown point at X is approximately the half of that of X^{∗} which is the breakdown point maximizing design within the classically optimal designs in X^{N} (see Müller (1994)). Note that X^{∗} is not breakdown point maximizing within all designs of X^{N}. But if we reduce X to X_{0} = {−1, 1}^{4} then X^{∗} also is breakdown point maximizing in X_{0}^{N} as Müller (1994) showed.

B) Multiple regression on balls. Another example where several classically optimal designs exist is the problem of multiple regression on balls which also was regarded in Müller (1994). For this problem Müller (1994) showed that classically optimal designs exist which are also breakdown point maximizing within all designs so that in particular they are breakdown point maximizing within the classically optimal designs.

References

[1] Bickel, P.J. (1975). One-step Huber estimates in the linear model. J. Amer. Statist. Assoc. 70, 428-434.

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

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

[4] Davies, P.L. (1993). Aspects of robust linear regression. Ann. Statist. 21, 1843-1899.

[5] Davies, P.L. (1994). Desirable properties, breakdown and efficiency in the linear regression model. Statist. Probab. Lett. 19, 361-370.

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

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

[8] Fedorov, V.V. (1989). Optimal design with bounded density: Optimization algorithms of the exchange type. J. Statist. Plann. Inference 22, 1-13.

[9] Hössjer, O. (1991). Rank-based estimates in the linear model with high breakdown point. J. Amer. Statist. Assoc. 89, 149-158.

[10] Jurečková, J. and Portnoy, S. (1987). Asymptotics for one-step M-estimators in regression with application to combining efficiency and high breakdown point. Commun. Statist.-Theory Meth. 16, 2187-2199.

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

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

[13] Müller, Ch.H. (1994). Optimal designs for robust estimation in conditionally contaminated linear models. J. Statist. Plann. Inference. 38, 125-140.

[14] Müller, Ch.H. (1994). Optimal breakdown point maximizing designs. Submitted to the Proceedings of PROBASTAT’94. Tatra Mountains Mathematical Publications, Bratislava.

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

[16] Rousseuw, P.J. (1984). Least median of squares regression. J. Amer. Statist. Assoc. 79, 871-880.

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

[18] Wierich, W. (1985). Optimum designs under experimental constraints for a covariate model and an intra-class regression model. J. Statist. Plann. Inference 12, 27-40.

[19] Wynn, H. (1982). Optimum submeasures with applications to finite population sampling. In: Statistical Decision Theory and Related Topics III, Vol. 2. Academic Press, New York, 485-495.

[20] Yohai, V.J. and Maronna, R.A. (1979). Asymptotic behavior of M-estimators for the linear model. Ann. Statist. 7, 258-268.