Noisy Information and Computational Complexity

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