Interpolation and Extrapolation Optimal Designs 2: Finite Dimensional General Models

Preface

This second volume, dedicated to optimal designs in interpolation and extrapolation, extends the concepts developed in Volume 1 [CEL 16] to the general framework of regression models defined on arbitrary finite dimensional linear spaces of regressors. This generalization is handled in relation to a variety of aspects. It pertains to the class of regressors, and extends the approach of the first volume to numerous optimality criteria. Special attention is also paid to the relations between these optimality criteria. The object to be estimated is also of a more general nature than an interpolated or an extrapolated value of the response variable under a given operational condition; these quantities are considered as special cases of a linear form of the coefficients of the regression model. Many hypotheses which have been assumed in Volume 1 are weakened. Nonlinear models are considered, as well as heteroscedastic or autocorrelated ones. Some excursion is proposed in cases when the dimension of the regressors is finite but is unknown, and tests for such problems are discussed. Finally, the algorithmic approach to optimal designs is considered, along with a discussion on the corresponding criteria, in the multivariate setting.

This volume is somehow self-consistent, and Volume 1 helps as a benchmark.

The geometric approach to Elfving’s theory follows the one adopted by Pukelsheim; we adopted the arguments arising from the theory of uniform approximation of continuous functions by a Haar system in order to achieve the analysis of the optimal designs for linear forms of the parameters in a Chebyshev regression; this is in the vein of many fundamental contributions in this field, as promoted by Kiefer and Wolfowitz, Karlin and Studden, and others.

We have found it useful to present a number of algorithms; these are stated with greater emphasis on their principles, than on their implementation.

Giorgio CELANT

Michel BRONIATOWSKI

February 2017

Introduction

The first four chapters contain material pertaining to the uniform approximation of continuous functions defined on a compact domain, making use of elements in a Haar finite dimensional linear space. The reader therefore has at their disposal the necessary topics to be used in a self contained volume. Also, much of the material presented here is to be used in the third volume, dealing with the infinite dimensional setting. The notation and style follow the approach which was adopted in the first volume.

The first chapter is devoted to the approximation of continuous functions in a normed space. Discussion is held on the advantages or drawbacks resulting from the fact that the norm is either induced by an inner product or not, in terms of existence and uniqueness of the approximation. We also consider natural questions pertaining to the approximating functions, such as rates of convergence, etc., in connection with some closeness considerations between the function to be approximated and the chosen class of approximating functions. Finally, we consider the choice of the norm in relation with requirements on the resulting measurement of the error. At the end of this first chapter, we deal with the special choice of Lp norms, together with some robustness considerations.

The second chapter is of fundamental importance for the topics covered in this volume. In the first volume, optimal interpolation and extrapolation designs were obtained, based on the Borel–Chebyshev theorem for the uniform polynomial approximation of continuous functions defined on a compact set of the real line. The generalization captured here holds on the substitution of the approximating elements by elements in a wider class than the class of polynomials with known degree. Extension of properties of such polynomials to larger classes of functions and the possible limits of such extensions is the core of this chapter, together with appropriate generalization of the Borel–Chebyshev theorem. Generalized polynomials, so-called Chebyshev or Haar systems are defined, and the corresponding properties of the linear space spanned by those systems (Haar spaces) are presented. In those spaces, generic elements share properties of usual polynomials, the Gauss d’Alembert theorem holds, as does an extended version of the Borel–Chebyshev theorem.

The chapter provides definitions for these generalized polynomials, together with a study of their algebraic properties (analysis of their roots, number of roots, etc.), and with a study of their properties with respect to the approximation of functions.

Chapter 3 is devoted to the various theorems that yield the tools for the approximation of functions in a Haar space.

Chapter 4 produces the explicit form of the best generalized polynomial that approximates a given continuous function uniformly. As such, the algorithms are similar to those presented in the first volume, at least in their approach; they generalize the algorithms of de la Vallée Poussin and Remez.

The interested reader will find much additional material in the following books: Rice [RIC 64], Dzyadyk [DZY 08], Achieser [ACH 92], Cheney [CHE 66], Karlin and Studden [KAR 66b], Natanson [NAT 64].

Chapters 5, 6, 7 and 8 are specifically devoted to the study of optimal designs.

Chapter 5 extends the results pertaining to extrapolation and interpolation designs to the context of the Chebyshev regression. The support of the designs is obtained through the Borel–Chebyshev theorem adapted to the generalized polynomials. The measure with such support, which determines the design, is characterized by a theorem due to Kiefer and Wolfowitz; the geometric approach which is adopted here is due to Hoel.

Chapter 6 is an extension of Chapter 5. The extrapolation is seen as a special linear form; in order to determine the optimal design for the estimation of a given linear form, a first analysis of the Gauss–Markov estimator is performed, hence focusing on the two ingredients which yield to specific questions in the realm of designs defined by generalized polynomials: bias and variance arguments. Unbiasedness is expressed in various ways, and yields to the notion of estimable linear forms. This approach induces a study of the moment matrix. The basic results that allow for the definition of the optimal design are Elfving and Karlin–Studden theorems.

Elfving’s theorem characterizes the optimal design for the estimation of a linear form cθ in a model of the form

in terms of the properties of the vector c which defines this form.

This result assesses that there exists some positive constant ρ such that ρ−1c is a convex combination of points of the form ± X(xi), i = 1, …, l where the xi’s are the supporting points of the c-optimal design; l denotes the cardinality of the support, and the weights of this convex combination are the frequencies of the design. Finally Elfving theorem assesses that

1) ρ² is the variance of the least square estimator of cθ when evaluated on the xi’s

2) The X(xi)’s are frontier points of the so called Elfving set; the value of l results from Carathéodory theorem for convex sets.

Chapter 6 provides an account of the above construction and results. Only in a few cases can the Elfving theorem produce the optimal design in an explicit way. However, when combined with the theorem by Kiefer and Wolfowitz obtained in Chapter 5, together with the extended Borel–Chebyshev theorem and the Karlin and Studden theorem, an operational approach to the optimal design can be handled. The Hoel Levine design, obtained in Volume 1, is deduced as a by-product of Karlin and Studden theorem. The geometric approach to Elfving’s theory, which has been chosen, follows Pukelsheim’s arguments; the discussion of Karlin and Studden’s theorem makes use of the theory of uniform approximation of functions.

The beginning of Chapter 7 considers various optimization criteria for the design. Relations between them are stated in a fundamental result which is known as the Kiefer–Wolfowitz equivalence theorem. Schoenberg’s theorem (which is only partly proved in this volume) allows for a generalization of the optimal design by Guest (see Volume 1) to the general Chebyshev regression.

The chapter also considers the consequences of relaxing a number of hypotheses assumed in Volume 1, such as homoscedasticity or linearity. In the heteroscedastic case, the Elfving theorem is generalized, leading to the theorem of Letz, Dette and Pepelyshev.

Nonlinearity leads to the study of the Fisher information matrix. We also propose a brief excursion toward cases when the polynomials are substituted for analytic functions. Various results in relation to the support of the optimal design for a linear form close this chapter, following various remarks by Kiefer, Wolfowitz and Studden.

The last chapter presents algorithms leading to optimal designs with respect to various criteria. The main topics are related to the problem posed by multi-valued regressors, with a joint range that differs from the Cartesian product of their univariate ranges, a case commonly met in applications. Generally, the simultaneous variation of the factors induces constraints in the regressor range which invalidate various symmetries, which in turn makes the optimal design a challenge. This chapter starts with a short discussion on such issues, and turns to the pioneering works of Fedorov and Wynn, and their extensions. Exchange algorithms are presented as well as a recent algorithm by Pronzato and Zhigljavsky, which obtains an optimal design under a concave criterion.

1

Approximation of Continuous Functions in Normed Spaces

1.1. Introduction

Given a real valued function f defined on ℝ which is assumed to belong to a class of functions F, approximating f amounts to substitute f by some function φ which belongs to some class V, which we will assume to be included in F. The natural setting is when F is a linear space, which we assume from now. The function φ will be chosen as to be more simple than f. We will call φ the approximation of f, or the approximating function. When f differs from φ, the error

will be considered; the relative error might also be considered, but we will mainly define φ through analysis pertaining to the function R.

In order to make this more meaningful, we have first to define the term simple when applied to approximation procedures, and its impact on the behavior of the function R. This requires a precise choice for the class V and for the criterion leading to the choice of φ in V for a given function f.

The choice of the approximating function φ clearly depends on properties to be expected by R or on some function of this error.

A natural setting leads one to define a distance d on F. Therefore, choosing φ follows from the solution of a problem of the kind

This problem may be difficult to solve when f does not belong to V.

A usual choice is to define the distance dF through a norm on F, say ║.║F. The resulting distance satisfies dF (f, g) := ║f − g║F.

The advantages of such a choice are clear when considering the properties of the norm. First, the norm is continuous, when seen as a functional on the linear space F. This setting makes all linear operations on F continuous with respect to the norm, and the topology on F is determined by the neighborhoods of the null function, through translation. This setting provides a set of useful tools; for example, the unit ball in F defined by

is compact if and only if F is a finite dimensional linear space (see Appendix 1, [CEL 16] theorem A1.6), a basic property to be used extensively when proving the existence of optimal points for a linear functional. More generally, all topological properties of a linear functional derive from its behavior on SF (0, 1). We suppose therefore that the function f to be approximated belongs to a normed space (F,║.║F ). We may also require a further assumption, which makes the analytic frame easier; at a certain time, we will require that the norm is defined by an inner product < .,. >F, defining In this case, F is a pre-Hilbert space.

The approximating function φ is assumed to belong to a finite dimensional subspace of F, denoted by V.

1.2. Some remarks on the meaning of the word simple. Choosing the approximation

The definition of simplicity is somehow vague and shares many different meanings. From the analytic point of view, simplicity is related to analytic regularity. From the standpoint of numerical calculation, the function is seen as a number of elementary operations to be performed; then complexity may be captured through the number of such operations. The function is complex when many operations are required to evaluate it. This latest point of view relates to the means at our disposal in terms of memory size, precision of the basic operations in the computer, speed of the processors, etc. Complexity results from the present state of the means at our disposal.

Choosing a function φ in a linear space V with finite dimension n may lead to defining n itself as the simplicity of the problem. It therefore seems that the simplicity of a given problem is defined by the number of parameters which are requested in order to solve it.

We say that the approximation procedure is linear when the approximating function φ belongs to a finite dimensional linear space.

The relation between the simplicity of the approximating function φ and the error R is loosely stated as follows.

Let φ1, .., φn be n functions defined on ℝ, and consider the absolute value of the local error substituting f by

namely,

This quantity is transformed into a global index, dF (f, φ), which is a function of the dimension of the linear space V where the approximation is performed. We denote this quantity by Ψ (n). When

[1.1]

for some non-negative and non-increasing function g which satisfies limn→∞ g(n) = 0, we say that the approximation procedure is of accuracy

Let and

where are the Fourier coefficients of f

We have

and there exists a constant c > 0, such that

[1.2]

The convergence of the series to f holds as a consequence of the following result:

THEOREM 1.1.– (Fejér) When f is some integrable function with summable Fourier coefficients, then the series of functions converges pointwise to f on ℝ.

PROOF.– See Kolmogorov–Fomine [KOL 74]

■

We prove [1.2] and deduce [1.1] for a suitable function g and with Ψ(N) := supx |f (x) − φN (x)|.

Evaluate

by parts, which yields

Iterating, we obtain

Hence, defining

it holds

For a smooth function, convergence of Ψ (N) to 0 is fast; for example, let

Then,

and therefore

Clearly, analytic simplicity and algorithmic complexity are concepts that interact with each other.

Another principle that may lead our ideas when choosing an approximating procedure is the following: the graph of φ should be as close as possible to that of f. Henceforth, when f has slow variations, we would require the same for φ, and the same for rapid variations of f.

For a given function f with slow variations, its approximation should be a polynomial with a low degree. On the contrary, a function f with large variations would require an approximating polynomial with a high degree. If f has nearly vertical slopes with abrupt changes in curvature or vertices with angular behavior, then its approximation can be chosen as a rational ratio function, i.e. the ratio of two polynomials. In such cases, the advantage of using an approximating function φ in

lies in the fact that a tuning of m and n allows us to reproduce very irregular local behaviors of f. This choice therefore allows us to reduce the complexity inherent to the choice of a polynomial with high degree for the same function f, which furthermore may lead to computational difficulties and numerical instability.

For functions f with rapid increase or decrease, the approximating function should include exponential terms of the form ex, e−x. Accordingly, approximations for periodic functions should include trigonometric terms. More generally, the choice of the function φ would make φ follow the graph of f as simply as possible, sometimes through the choice of a grid, according to the local behavior of f.

Observe that, except for the class all other approximating classes which we considered are linear spaces with finite dimension. For example, the linear space

has dimension m.

The linear space

which is used in order to approximate periodic functions has dimension 2n + 1.

1.2.1. Splines

Assuming that f is defined on some interval [a, b] in ℝ, define a partition of [a, b], namely, I1 := [a, z1] , …, Ii+1 := [zi, zi+1] , …, Ik := [zk, b]. In any of these interval Ij, f can be approximated by a simple function, for example, a straight line, a parabola or a cubic function. The resulting approximating function on [a, b] may not be defined in the same way on all the intervals Ij. Therefore, the restrictions φ |Ij of φ on the intervals Ij, j = 1, …, k, are polynomials with degree less or equal to m − 1.

For a given subdivision {z1, …, zk} of [a, b], the class Sm (z1, …,