9.5 Generalizations 130

9.6 Notes and comments 132

10 Native spaces 133

10.1 Reproducing-kernel Hilbert spaces 133

10.2 Native spaces for positive de¬nite kernels 136

10.3 Native spaces for conditionally positive de¬nite kernels 141

10.4 Further characterizations of native spaces 150

10.5 Special cases of native spaces 156

10.6 An embedding theorem 167

10.7 Restriction and extension 168

10.8 Notes and comments 170

11 Error estimates for radial basis function interpolation 172

11.1 Power function and ¬rst estimates 172

11.2 Error estimates in terms of the ¬ll distance 177

Contents vii

11.3 Estimates for popular basis functions 183

11.4 Spectral convergence for Gaussians and (inverse) multiquadics 188

11.5 Improved error estimates 191

11.6 Sobolev bounds for functions with scattered zeros 194

11.7 Notes and comments 204

12 Stability 206

12.1 Trade-off principle 208

Lower bounds for »min

12.2 209

12.3 Change of basis 215

12.4 Notes and comments 222

13 Optimal recovery 223

13.1 Minimal properties of radial basis functions 223

13.2 Abstract optimal recovery 226

13.3 Notes and comments 229

14 Data structures 230

14.1 The ¬xed-grid method 231

14.2 kd-Trees 237

14.3 bd-Trees 243

14.4 Range trees 246

14.5 Notes and comments 251

15 Numerical methods 253

15.1 Fast multipole methods 253

15.2 Approximation of Lagrange functions 265

15.3 Alternating projections 270

15.4 Partition of unity 275

15.5 Multilevel methods 280

15.6 A greedy algorithm 283

15.7 Concluding remarks 287

15.8 Notes and comments 287

16 Generalized interpolation 289

16.1 Optimal recovery in Hilbert spaces 289

16.2 Hermite“Birkhoff interpolation 292

16.3 Solving PDEs by collocation 296

16.4 Notes and comments 306

17 Interpolation on spheres and other manifolds 308

17.1 Spherical harmonics 308

viii Contents

17.2 Positive de¬nite functions on the sphere 310

17.3 Error estimates 314

17.4 Interpolation on compact manifolds 316

17.5 Notes and comments 321

References 323

Index 334

Preface

Scattered data approximation is a recent, fast growing research area. It deals with the

problem of reconstructing an unknown function from given scattered data. Naturally, it

has many applications, such as terrain modeling, surface reconstruction, ¬‚uid“structure

interaction, the numerical solution of partial differential equations, kernel learning, and

parameter estimation, to name a few. Moreover, these applications come from such different

¬elds as applied mathematics, computer science, geology, biology, engineering, and even

business studies.

This book is designed to give a thorough, self-contained introduction to the ¬eld of

multivariate scattered data approximation without neglecting the most recent results.

Having the above-mentioned applications in mind, it immediately follows that any com-

peting method has to be capable of dealing with a very large number of data points in an

arbitrary number of space dimensions, which might bear no regularity at all and which

might even change position with time.

Hence, in my personal opinion a true scattered data method has to be meshless. This is an

assumption that might be challenged but it will be the fundamental assumption throughout

this book. Consequently, certain methods, that generally require a mesh, such as those using

wavelets, multivariate splines, ¬nite elements, box splines, etc. are immediately ruled out.

This does not at all mean that such methods cannot sometimes be used successfully in the

context of scattered data approximation; on the contrary, it just explains why these methods

are not discussed in this book. The requirement of being truly meshless reduces the number

of ef¬cient multivariate methods dramatically. Amongst them, radial basis functions, or,

more generally, approximation by (conditionally) positive de¬nite kernels, the moving least

squares approximation, and, to a certain extent, partition-of-unity methods, appear to be the

most promising. Because of this, they will be given a thorough treatment.

A brief outline of the book is as follows. In Chapter 1 we discuss a few typical appli-

cations and then turn to natural cubic splines as a motivation for (conditionally) positive

de¬nite kernels. The following two chapters can be seen as an introduction to the problems

of multivariate approximation theory. Chapter 4 is devoted to the moving least squares ap-

proximation. In Chapter 5 we collect certain auxiliary results necessary for the rest of the

book, and the impatient or advanced reader might skip the details and come back to this

ix

x Preface

chapter whenever necessary. The theory of radial basis functions starts with the discussion

of positive de¬nite and completely monotone functions in Chapters 6 and 7 and continues

with conditionally positive de¬nite and compactly supported functions. In Chapters 10 and

11 we deal with the error analysis of the approximation process. In the following chapter

we start the numerical part of this book by discussing the stability of the process. After a

short interplay on optimal recovery in Chapter 13, we continue the numerical treatment with

chapters on data structures and ef¬cient algorithms, where partition-of-unity methods are

investigated also. In Chapter 16 we deal with generalized interpolation, which is important

if, for example, partial differential equations are to be solved numerically using scattered

data methods, and in Chapter 17 we consider applications to the sphere.

It is impossible to thank everyone who has helped me in the writing of this book. But it is

my pleasure to point out at least a few of those persons without diminishing the respect and

gratitude I owe to those not mentioned. First of all, I have to thank R. Schaback from the

University of G¨ ttingen and J. D. Ward and F. J. Narcowich from Texas A&M University.

o

It was they who ¬rst attracted my attention to the ¬eld of scattered data approximation, and

they have had a great in¬‚uence on my point of view. Further help either by discussion or by

proofreading parts of the text has been provided by A. Beckert, R. Brownlee, G. Fasshauer,

P. H¨ hner, J. Miranda, and R. Opfer. Finally, I am more than grateful to Cambridge University

a

Press, in particular to David Tranah and Ken Blake for their kind and ef¬cient support.

1

Applications and motivations

In practical applications over a wide ¬eld of study one often faces the problem of recon-

structing an unknown function f from a ¬nite set of discrete data. These data consist of data

sites X = {x1 , . . . , x N } and data values f j = f (x j ), 1 ¤ j ¤ N , and the reconstruction has

to approximate the data values at the data sites. In other words, a function s is sought that ei-

ther interpolates the data, i.e. that satis¬es s(x j ) = f j , 1 ¤ j ¤ N , or at least approximates

the data, s(x j ) ≈ f j . The latter case is in particular important if the data contain noise.

In many cases the data sites are scattered, i.e. they bear no regular structure at all, and there

is a very large number of them, easily up to several million. In some applications, the data

sites also exist in a space of very high dimensions. Hence, for a unifying approach methods

have to be developed which are capable of meeting this situation. But before pursuing this

any further let us have a closer look at some possible applications.