Information-Based Complexity

Information-Based Complexity

Hardcover

$83.12 $99.95 Save 17% Current price is $83.12, Original price is $99.95. You Save 17%.

Product Details

ISBN-13: 9780126975451
Publisher: Elsevier Science & Technology Books
Publication date: 07/28/1988
Series: Computer Science and Scientific Computing Series
Pages: 523
Product dimensions: 15.00(w) x 23.00(h) x (d)

Table of Contents

Prefacexiii
Chapter 1.Overview1
Chapter 2.Example: Continuous Binary Search5
1.Introduction5
1.1.Problem Formulation6
1.2.Information6
1.3.Model of Computation6
2.Complexity7
3.Worst Case Setting8
4.Average Case Setting10
5.Probabilistic Setting12
6.Relative Error13
6.1.Worst Case Setting14
6.2.Average Case Setting15
6.3.Probabilistic Setting17
7.Comparison of Complexity18
8.Mixed Settings19
9.Noisy Information20
10.Final Comments21
Chapter 3.General Formulation23
1.Introduction23
2.Formulation24
2.1.Problem Formulation24
2.2.Information27
2.3.Model of Computation30
2.4.How Can We Compute Approximations?33
3.Complexity in Three Settings35
4.Asymptotic Setting38
5.Randomization38
Chapter 4.Worst Case Setting: Theory41
1.Introduction41
2.Radius and Diameter of Information43
3.Algorithms48
3.1.Local and Global Errors48
3.2.Central Algorithms49
3.3.Interpolatory Algorithms51
4.Cardinality Number and Complexity53
5.Linear Problems55
5.1.Definition of Linear Problems56
5.2.Adaption versus Nonadaption57
5.3.Optimal Information65
5.4.Relations between nth Minimal Radii and Gelfand n-Widths70
5.5.Linear Algorithms75
5.6.Optimal Linear Algorithms and Linear Kolmogorov n-Widths91
5.7.Spline Algorithms95
5.8.Complexity101
6.Different Error Criteria105
6.1.Relative Error105
6.2.Normalized Error109
6.3.Convex and Symmetric Error113
Chapter 5.Worst Case Setting: Applications117
1.Introduction117
2.Integration117
2.1.Smooth Periodic Functions119
2.2.Smooth Nonperiodic Functions123
2.3.Weighted Integration in a Reproducing Kernel Hilbert Space131
3.Function Approximation137
3.1.Smooth Periodic Functions138
3.2.Smooth Nonperiodic Functions: Hilbert Case144
3.3.Smooth Nonperiodic Functions: Banach Case147
4.Computer Vision148
5.Linear Partial Differential Equations153
6.Integral Equations167
7.Ill-Posed Problems173
8.Optimization177
9.Large Linear Systems178
10.Eigenvalue Problem183
11.Ordinary Differential Equations186
12.Nonlinear Equations188
13.Topological Degree193
Chapter 6.Average Case Setting: Theory195
1.Introduction195
2.Radius of Information197
3.Algorithms204
3.1.Local and Global Average Errors204
3.2.Central Algorithms206
4.Average Cardinality Number and Complexity213
5.Linear Problems215
5.1.Linear Problems in the Average Case Setting217
5.2.Gaussian Measures218
5.3.Central Algorithms222
5.4.Spline Algorithms226
5.5.Optimal Nonadaptive Information233
5.6.Adaptive Information236
5.6.1.Adaptive Information with Fixed Cardinality237
5.6.2.Adaptive Information with Varying Cardinality240
5.7.Complexity248
5.8.Linear Problems for Bounded Domains257
5.8.1.Average Radius of Information259
5.8.2.Proof of Theorem 5.8.1.265
6.Different Error Criteria268
6.1.Relative Error268
6.2.Normalized Error279
6.3.General Error Functional281
6.4.Precision Error292
Chapter 7.Average Case Setting: Applications296
1.Introduction296
2.Integration297
2.1.Smooth Functions297
2.2.Weighted Integration in a Reproducing Kernel Hilbert Space302
3.Function Approximation309
3.1.Smooth Periodic Functions309
3.2.Smooth Nonperiodic Functions311
4.Ill-Posed Problems315
Chapter 8.Probabilistic Setting323
1.Introduction323
2.Relation to Average Case Setting326
3.Radius of Information327
4.Probabilistic Cardinality Number and Complexity328
5.Linear Problems329
5.1.Optimal Error Algorithms329
5.2.Estimates of the Radius of Information331
5.3.Optimal Information334
5.4.Complexity336
5.5.Linear Problems for Bounded Domains344
6.Different Error Criteria346
6.1.Relative Error346
6.2.Normalized Error356
6.3.General Error Functional358
7.Applications359
Chapter 9.Comparison between Different Settings364
1.Introduction364
2.Integration of Smooth Functions365
3.Integration of Smooth Periodic Functions368
4.Approximation of Smooth Periodic Functions370
5.Approximation of Smooth Nonperiodic Functions372
Chapter 10.Asymptotic Setting375
1.Introduction375
2.Asymptotic and Worst Case Settings: Linear Problems383
2.1.Optimal Algorithms383
2.2.Optimal Information389
2.3.Continuous Algorithms394
3.Asymptotic and Worst Case Settings: Nonlinear Problems395
3.1.Optimal Algorithms395
3.2.Optimal Information399
3.3.Applications400
4.Asymptotic and Average Case Settings403
4.1.Optimal Algorithms404
4.2.Rate of Convergence407
4.3.Optimal Information410
Chapter 11.Randomization413
1.Introduction413
2.Random Information and Random Algorithms414
3.Average Case Setting418
3.1.Linear Problems for the Whole Space419
3.2.Linear Problems for Bounded Domains421
4.Worst Case Setting422
4.1.Function Approximation and Other Problems423
4.1.1.Function Approximation425
4.1.2.Maximum and Extremal Points425
4.1.3.Function Inverse426
4.1.4.Topological Degree427
4.2.Integration429
4.3.Linear Problems with Unrestricted Information431
Chapter 12.Noisy Information434
1.Introduction434
2.Worst Case Setting with Deterministic Noise434
2.1.Basic Definitions434
2.2.Uniformly Bounded Noise436
3.Average Case Setting with Random Noise441
3.1.Basic Definitions441
3.2.Normally Distributed Noise443
3.3.Does Adaption Help?443
3.3.1.Examples444
3.3.2.Adaptive Choice of Observations Does Not Help445
4.Mixed Setting450
Appendix453
1.Functional Analysis453
1.1.Linear Spaces and Linear Operators453
1.2.Linear Independence, Dimension, and Linear Subspaces454
1.3.Norms and Continuous Linear Operators455
1.4.Banach Spaces456
1.5.Inner Products and Hilbert Spaces456
1.5.1.Inner Products456
1.5.2.Hilbert Spaces457
1.5.3.Separable Hilbert Spaces458
1.6.Bounded Operators on Hilbert Spaces458
1.6.1.Bounded Functionals and Riesz's Theorem458
1.6.2.Adjoint Operators458
1.6.3.Orthogonal and Projection Operators459
1.6.4.Spectrum460
2.Measure Theory461
2.1.Borel [sigma]-Field, Measurable Sets and Functions461
2.2.Measures and Probability Measures461
2.3.Integrals462
2.4.Characteristic Functional464
2.5.Mean Element464
2.6.Covariance and Correlation Operators465
2.7.Induced and Conditional Measures465
2.8.Product Measures and Fubini's Theorem466
2.9.Gaussian Measures466
2.9.1.Measure of a Ball467
2.9.2.Induced and Conditional Measures471
Bibliography475
Author Index511
Subject Index517

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews