Tractability of Multivariate Problems: Volume I: Linear Information (Ems Tracts in Mathematics)

Preface......Page 7
Contents......Page 9
1 Overview......Page 13
2 Motivation for Tractability Studies......Page 15
Notes and Remarks......Page 25
Example 1: Integration of Lipschitz Functions......Page 26
Example 2: Integration of Trigonometric Polynomials......Page 28
Example 3: Integration of Smooth Periodic Functions......Page 31
Example 4: Approximation of C Functions......Page 35
Example 5: Discrepancy......Page 46
Example 6: Diagonal Problems for Weighted Spaces......Page 52
Tractability in Other Settings......Page 60
Example 7: Isotropic Wiener Measure......Page 62
Example 8: Folded Wiener Sheet Measure......Page 70
Example 9: Absolute and Normalized Errors......Page 75
Example 10: Relative Error......Page 77
Randomized Setting......Page 79
Example 11: Monte Carlo Algorithm......Page 80
Example 12: Class all......Page 85
Open Problems......Page 87
Notes and Remarks......Page 97
Complexity in the Worst Case Setting......Page 101
Types of Information......Page 104
Algorithms and Their Cost......Page 108
Why Do We Use the Real Number Model?......Page 111
Errors and Complexity......Page 117
Information Complexity and Total Complexity......Page 119
Basic Results for Linear Problems in the Worst Case Setting......Page 120
On the Power of Adaption......Page 121
Linear and Nonlinear Algorithms for Linear Problems......Page 127
Linear Problems on Hilbert Spaces for all......Page 130
Sobolev Embeddings......Page 131
Average Case Setting......Page 139
Probabilistic Setting......Page 149
Randomized Algorithms......Page 152
Multivariate Problems and Tractability......Page 160
Polynomial Tractability......Page 161
Weak Tractability......Page 162
Generalized Tractability......Page 163
Notes and Remarks......Page 164
5 Worst Case Setting......Page 167
Linear Problems Defined over Hilbert Spaces......Page 168
Linear Tensor Product Problems......Page 185
Linear Weighted Tensor Product Problems......Page 200
Weighted Hilbert Spaces......Page 201
Types of Weights......Page 206
Weighted Operators......Page 211
Tractability of Weighted Problems......Page 212
Other Ways of Obtaining Linear Weighted Problems......Page 232
Weighted Sobolev Space of Smooth Functions......Page 233
General Linear Weighted Problems......Page 241
Notes and Remarks......Page 250
Linear Problems......Page 253
Linear Tensor Product Problems......Page 267
Linear Weighted Tensor Product Problems......Page 277
Notes and Remarks......Page 294
Tractability of Linear Problems for all......Page 296
8 Generalized Tractability......Page 298
Motivation of Generalized Tractability......Page 301
Linear Tensor Product Problems......Page 307
Restricted Tractability in......Page 308
Restricted Tractability in d......Page 311
Restricted Tractability with d*1 and _0<1......Page 326
Unrestricted Tractability Domain......Page 331
Finitely Many Eigenvalues......Page 332
Exponential Decay of Eigenvalues......Page 339
Polynomial Decay of Eigenvalues......Page 343
Comparison......Page 350
Notes and Remarks......Page 352
Korobov Spaces......Page 353
Weighted Korobov Spaces......Page 359
The First Weighted Sobolev Space......Page 362
The Second Weighted Sobolev Space......Page 365
The Third Weighted Sobolev Space......Page 367
Gaussian Measures on Banach Spaces......Page 369
Gaussian Measures and Reproducing Kernel Hilbert Spaces......Page 373
Appendix C List of Open Problems......Page 375
Bibliography......Page 377
Index......Page 393