Noisy Information and Computational Complexity
The book presents a theory of computational complexity of continuous problems with noisy information, i.e., contaminated by errors. The sources of noise include: previous computations, inexact measurements, transmission errors, arithmetic limitations, etc. Deterministic and random noise are considered. A number of applications is given. Noisy information is typical of many problems arising in different scientific fields, e.g. signal processing, control theory, computer vision, numerical algorithms, etc. This monograph is based on results of many researchers in this area including the results of the author. Some of the author's results are not published elsewhere. Information-based complexity models cover a large variety of problems but the author is mainly interested in linear problems, i.e., problems which can be described in terms of approximating a linear operator from noisy information about results of some linear functionals. The problem complexity depend on the setting. Worst case, average case, worst-average, average-worst and asymptotic case settings are studied in the different chapters of the book. Each chapter is followed by Notes, Remarks and Exercises. In the worst case setting, the error and the cost are defined by their worst performance. In the average case setting, the author consider the average error and cost. The mixed worst-average and average-worst case settings are obtained by combining the worst and average cases. In the asymptotic setting the author is interested in the asymptotic behavior of algorithms. Other settings such as probabilistic and randomized are not involved in the monograph. The paper is interesting for numerical mathematicians dealing with the theory of computational complexity as well as for statisticians, engineers, control theorists and economists.
- On the power of standard information for \(L_{\infty}\) approximation in the randomized setting
- Average case optimality
- Spatial adaption for predicting random functions
- Noisy inference and oracles
- A stochastically quasi-optimal search algorithm for the maximum of the simple random walk
- Spatial shape-preserving interpolation using \(\nu\)-splines
- Recovering linear operators and Lagrange function minimality condition
- A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise
- Optimal recovery of operators in function \(L\)-spaces
- Optimal recovery of operator sequences
- Learning from non-random data in Hilbert spaces: an optimal recovery perspective
- Computational (numerical) diameter in a context of general theory of a recovery
- Adaption allows efficient integration of functions with unknown singularities
- On the optimal robust solution of IVPs with noisy information
- Optimal recovery methods exact on trigonometric polynomials for the solution of the heat equation
- Optimal recovery from inaccurate data in Hilbert spaces: regularize, but what of the parameter?
- The power of adaption for approximating functions with singularities
- Improvements of Winograd's result on computation in the presence of noise (Corresp.)
- The power of standard information for multivariate approximation in the randomized setting
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- scientific article; zbMATH DE number 193625 (Why is no real title available?)
- Joint spectra of Toeplitz operators and optimal recovery of analytic functions
- On linear versus nonlinear approximation in the average case setting
- A survey of average case complexity for linear multivariate problems
- scientific article; zbMATH DE number 953037 (Why is no real title available?)
- Recovering signals from inner products involving prolate spheroidals in the presence of jitter
- Exact orders of computational (numerical) diameters in problems of reconstructing functions and sampling solutions of the Klein-Gordon equation from Fourier coefficients
- Automatic integration using asymptotically optimal adaptive simpson quadrature
- Convergence of sparse variational inference in Gaussian processes regression
- On optimal recovery of values of linear operators from information known with a stochastic error
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- scientific article; zbMATH DE number 7204267 (Why is no real title available?)
- Instances of computational optimal recovery: dealing with observation errors
- Computability of solutions of operator equations
- A study on regularization for discrete inverse problems with model-dependent noise
- Optimal conditional estimation: Average case setting
- Worst case tractability of linear problems in the presence of noise: linear information
- The complexity of Fredholm equations of the second kind: noisy information about everything
- On the construction of families of optimal recovery methods for linear operators
- Homogeneous algorithms and solvable problems on cones
- Radius of information for two intersected centered hyperellipsoids and implications in optimal recovery from inaccurate data
- Error bounds and the asymptotic setting in kernel-based approximation
- Recovery of analytic functions that is exact on subspaces of entire functions
- Optimal recovery methods for solutions of the Dirichlet problem that are exact on subspaces of spherical harmonics
- Learning the maximum of a Hölder function from inexact data
- On the randomized Euler algorithm under inexact information
- Optimal recovery of a solution of a system of linear differential equations from initial information given with a random error
- Full C(N)D-study of computational capabilities of Lagrange polynomials
- Noisy nonlinear information and entropy numbers
- Approximation of functions: optimal sampling and complexity
- Approximation of solutions of the heat equation by inaccurate information
- Recovery of differential operators from a noisy Fourier transform
- The quantum setting with randomized queries for continuous problems
- Informative cardinality of trigonometric Fourier coefficients and their limiting error in the discretization of a differentiation operator in multidimensional Sobolev classes
This page was built for publication: Noisy Information and Computational Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4229815)
