This book deals with the computational complexity of mathematical problems for which available information is partial, noisy and priced. The author develops a general theory of computational complexity of continuous problems with noisy information and gives a number of applications; he considers deterministic as well as stochastic noise. He also presents optimal algorithms, optimal information, and complexity bounds in different settings: worst case, average case, mixed worst-average, average-worst, and asymptotic. Particular topics include: the existence of optimal linear (affine) algorithms, optimality properties of smoothing spline, regularization and least squares algorithms (with the optimal choice of the smoothing and regularization parameters), adaption versus nonadaption, and relations between different settings. The book integrates the work of researchers over the past decade in such areas as computational complexity, approximation theory, and statistics, and includes many new results as well. The author supplies two hundred exercises to increase the reader's understanding of the subject.
Author(s): Leszek Plaskota
Publisher: CUP
Year: 1996
Language: English
Pages: 321
Cover......Page 1
Title......Page 4
Copyright......Page 5
Contents......Page 6
Preface......Page 10
List of symbols......Page 11
1 Overview......Page 14
2.1 Introduction......Page 18
2.2 Information, algorithms, approximation......Page 21
2.3 Radius and diameter of information......Page 25
2.4.1 Existence of optimal affine algorithms......Page 33
2.4.2 The case of Hilbert noise......Page 36
2.5.1 Splines and smoothing splines......Page 45
2.5.2 a-smoothing splines......Page 48
2.6.1 The Hilbert case with optimal a......Page 57
2.6.2 Least squares and regularization......Page 63
2.6.3 Polynomial splines......Page 67
2.6.4 Splines in r.k.h.s.......Page 71
2.7.1 Nonadaptive and adaptive information......Page 76
2.7.2 When does adaption not help?......Page 79
2.8.1 Linear problems in Hilbert spaces......Page 84
2.8.2 Approximation and integration of Lipschitz functions......Page 94
2.9.1 Computations over the space G......Page 102
2.9.2 Cost and complexity, general bounds......Page 105
2.10.1 Linear problems in Hilbert spaces......Page 113
2.10.2 Approximation and integration of Lipschitz functions......Page 119
2.10.3 Multivariate approximation in a Banach space......Page 122
3.1 Introduction......Page 134
3.2 Information and its radius......Page 136
3.3.1 Basic properties......Page 145
3.3.2 Gaussian measures as abstract Wiener spaces......Page 147
3.4 Linear problems with Gaussian measures......Page 152
3.4.1 Induced and conditional distributions......Page 153
3.4.2 Optimal algorithms......Page 156
3.5 The case of linear functionals......Page 161
3.6 Optimal algorithms as smoothing splines......Page 168
3.6.1 A general case......Page 169
3.6.2 Special cases......Page 170
3.6.3 Relations to worst case setting......Page 172
3.7 Varying information......Page 175
3.7.1 Nonadaptive and adaptive information......Page 176
3.7.2 Adaption versus nonadaption......Page 178
3.8.1 Linear problems with Gaussian measures......Page 183
3.8.2 Approximation and integration on the Wiener space......Page 193
3.9 Complexity......Page 210
3.9.1 Adaption versus nonadaption......Page 211
3.9.2 Complexity bounds......Page 215
3.10.1 Linear problems with Gaussian measures......Page 218
3.10.2 Approximation and integration on the Wiener space......Page 223
4.1 Introduction......Page 228
4.2.1 The one dimensional problem......Page 229
4.2.2 Almost optimality of affine algorithms......Page 233
4.2.3 Relations to other settings......Page 243
4.3.1 Ellipsoidal problems in R'......Page 247
4.3.2 The Hilbert case......Page 251
5.1 Introduction......Page 261
5.2.1 The one dimensional problem......Page 262
5.2.2 Almost optimality of linear algorithms......Page 265
5.2.3 Relations to other settings......Page 273
5.3 Approximation of operators......Page 276
6.1 Introduction......Page 281
6.2 Asymptotic and worst case settings......Page 282
6.2.1 Information, algorithm and error......Page 283
6.2.2 Optimal algorithms......Page 284
6.2.3 Optimal nonadaptive information......Page 289
6.3 Asymptotic and average case settings......Page 294
6.3.1 Optimal algorithms......Page 295
6.3.2 Convergence rate......Page 298
6.3.3 Optimal nonadaptive information......Page 301
References......Page 306
Author index......Page 317
Subject index......Page 319
