Information-based complexity / J.F. Traub, G.W. Wasilkowski, H. Woźniakowski.

Format:

Book

Author/Creator:

Traub, J. F. (Joseph Frederick), 1932-2015.

Contributor:

Wasilkowski, G. W.

Woźniakowski, H.

Series:

Computer science and scientific computing

Computer science and scientific computing.

Language:

English

Subjects (All):

Computational complexity.

Physical Description:

xiii, 523 pages ; 24 cm.

Place of Publication:

Boston : Academic Press, [1988]

Contents:

Chapter 2. Example: Continuous Binary Search 5

1.1. Problem Formulation 6

1.2. Information 6

1.3. Model of Computation 6

2. Complexity 7

3. Worst Case Setting 8

4. Average Case Setting 10

5. Probabilistic Setting 12

6. Relative Error 13

6.1. Worst Case Setting 14

6.2. Average Case Setting 15

6.3. Probabilistic Setting 17

7. Comparison of Complexity 18

8. Mixed Settings 19

9. Noisy Information 20

Chapter 3. General Formulation 23

2. Formulation 24

2.1. Problem Formulation 24

2.2. Information 27

2.3. Model of Computation 30

2.4. How Can We Compute Approximations? 33

3. Complexity in Three Settings 35

4. Asymptotic Setting 38

5. Randomization 38

Chapter 4. Worst Case Setting: Theory 41

2. Radius and Diameter of Information 43

3. Algorithms 48

3.1. Local and Global Errors 48

3.2. Central Algorithms 49

3.3. Interpolatory Algorithms 51

4. Cardinality Number and Complexity 53

5. Linear Problems 55

5.1. Definition of Linear Problems 56

5.2. Adaption versus Nonadaption 57

5.3. Optimal Information 65

5.4. Relations between nth Minimal Radii and Gelfand n-Widths 70

5.5. Linear Algorithms 75

5.6. Optimal Linear Algorithms and Linear Kolmogorov n-Widths 91

5.7. Spline Algorithms 95

5.8. Complexity 101

6. Different Error Criteria 105

6.1. Relative Error 105

6.2. Normalized Error 109

6.3. Convex and Symmetric Error 113

Chapter 5. Worst Case Setting: Applications 117

2. Integration 117

2.1. Smooth Periodic Functions 119

2.2. Smooth Nonperiodic Functions 123

2.3. Weighted Integration in a Reproducing Kernel Hilbert Space 131

3. Function Approximation 137

3.1. Smooth Periodic Functions 138

3.2. Smooth Nonperiodic Functions: Hilbert Case 144

3.3. Smooth Nonperiodic Functions: Banach Case 147

4. Computer Vision 148

5. Linear Partial Differential Equations 153

6. Integral Equations 167

7. Ill-Posed Problems 173

8. Optimization 177

9. Large Linear Systems 178

10. Eigenvalue Problem 183

11. Ordinary Differential Equations 186

12. Nonlinear Equations 188

13. Topological Degree 193

Chapter 6. Average Case Setting: Theory 195

2. Radius of Information 197

3. Algorithms 204

3.1. Local and Global Average Errors 204

3.2. Central Algorithms 206

4. Average Cardinality Number and Complexity 213

5. Linear Problems 215

5.1. Linear Problems in the Average Case Setting 217

5.2. Gaussian Measures 218

5.3. Central Algorithms 222

5.4. Spline Algorithms 226

5.5. Optimal Nonadaptive Information 233

5.6. Adaptive Information 236

5.6.1. Adaptive Information with Fixed Cardinality 237

5.6.2. Adaptive Information with Varying Cardinality 240

5.7. Complexity 248

5.8. Linear Problems for Bounded Domains 257

5.8.1. Average Radius of Information 259

5.8.2. Proof of Theorem 5.8.1. 265

6. Different Error Criteria 268

6.1. Relative Error 268

6.2. Normalized Error 279

6.3. General Error Functional 281

6.4. Precision Error 292

Chapter 7. Average Case Setting: Applications 296

2. Integration 297

2.1. Smooth Functions 297

2.2. Weighted Integration in a Reproducing Kernel Hilbert Space 302

3. Function Approximation 309

3.1. Smooth Periodic Functions 309

3.2. Smooth Nonperiodic Functions 311

4. Ill-Posed Problems 315

Chapter 8. Probabilistic Setting 323

2. Relation to Average Case Setting 326

3. Radius of Information 327

4. Probabilistic Cardinality Number and Complexity 328

5. Linear Problems 329

5.1. Optimal Error Algorithms 329

5.2. Estimates of the Radius of Information 331

5.3. Optimal Information 334

5.4. Complexity 336

5.5. Linear Problems for Bounded Domains 344

6. Different Error Criteria 346

6.1. Relative Error 346

6.2. Normalized Error 356

6.3. General Error Functional 358

7. Applications 359

Chapter 9. Comparison between Different Settings 364

2. Integration of Smooth Functions 365

3. Integration of Smooth Periodic Functions 368

4. Approximation of Smooth Periodic Functions 370

5. Approximation of Smooth Nonperiodic Functions 372

Chapter 10. Asymptotic Setting 375

2. Asymptotic and Worst Case Settings: Linear Problems 383

2.1. Optimal Algorithms 383

2.2. Optimal Information 389

2.3. Continuous Algorithms 394

3. Asymptotic and Worst Case Settings: Nonlinear Problems 395

3.1. Optimal Algorithms 395

3.2. Optimal Information 399

3.3. Applications 400

4. Asymptotic and Average Case Settings 403

4.1. Optimal Algorithms 404

4.2. Rate of Convergence 407

4.3. Optimal Information 410

Chapter 11. Randomization 413

2. Random Information and Random Algorithms 414

3. Average Case Setting 418

3.1. Linear Problems for the Whole Space 419

3.2. Linear Problems for Bounded Domains 421

4. Worst Case Setting 422

4.1. Function Approximation and Other Problems 423

4.1.1. Function Approximation 425

4.1.2. Maximum and Extremal Points 425

4.1.3. Function Inverse 426

4.1.4. Topological Degree 427

4.2. Integration 429

4.3. Linear Problems with Unrestricted Information 431

Chapter 12. Noisy Information 434

2. Worst Case Setting with Deterministic Noise 434

2.2. Uniformly Bounded Noise 436

3. Average Case Setting with Random Noise 441

3.2. Normally Distributed Noise 443

3.3. Does Adaption Help? 443

3.3.2. Adaptive Choice of Observations Does Not Help 445

4. Mixed Setting 450

1. Functional Analysis 453

1.1. Linear Spaces and Linear Operators 453

1.2. Linear Independence, Dimension, and Linear Subspaces 454

1.3. Norms and Continuous Linear Operators 455

1.4. Banach Spaces 456

1.5. Inner Products and Hilbert Spaces 456

1.5.1. Inner Products 456

1.5.2. Hilbert Spaces 457

1.5.3. Separable Hilbert Spaces 458

1.6. Bounded Operators on Hilbert Spaces 458

1.6.1. Bounded Functionals and Riesz's Theorem 458

1.6.2. Adjoint Operators 458

1.6.3. Orthogonal and Projection Operators 459

1.6.4. Spectrum 460

2. Measure Theory 461

2.1. Borel [sigma]-Field, Measurable Sets and Functions 461

2.2. Measures and Probability Measures 461

2.3. Integrals 462

2.4. Characteristic Functional 464

2.5. Mean Element 464

2.6. Covariance and Correlation Operators 465

2.7. Induced and Conditional Measures 465

2.8. Product Measures and Fubini's Theorem 466

2.9. Gaussian Measures 466

2.9.1. Measure of a Ball 467

2.9.2. Induced and Conditional Measures 471.

Notes:

Includes indexes.

Bibliography: pages 475-509.

ISBN:

0126975450

OCLC:

17209526