Probabilistic setting of information-based complexity

DOI10.1016/0885-064X(86)90005-1MaRDI QIDQ1092660zbMATH OpenOpenAlexFDO

Authors H. Woźniakowski

Publication date 1986

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(86)90005-1

zbMATH Keywords

approximationGaussian measuresintegrationprobabilistic epsilon-delta complexity

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15) Numerical integration (65D30) Analysis of algorithms and problem complexity (68Q25)

Review text

We study the probabilistic (\(\epsilon\),\(\delta)\)-complexity for linear problems equipped with Gaussian measures. The probabilistic (\(\epsilon\),\(\delta)\)-complexity, \(comp^{prob}(\epsilon,\delta)\), is understood as the minimal cost required to compute approximations with error at most \(\epsilon\) on a set of measure at least 1-\(\delta\). We find estimates of \(comp^{prob}(\epsilon,\delta)\) in terms of eigenvalues of the correlation operator of the Gaussian measure over elements which we want to approximate. In particular, we study the approximation and integration problems.

Recommendations

• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• Probabilistic complexity analysis for linear problems in bounded domains
• On average case complexity of linear problems with noisy information
• scientific article; zbMATH DE number 953052
• Optimal algorithms for linear problems with Gaussian measures

Cites work

• Approximation of linear functionals on a Banach space with a Gaussian measure
• Gaussian measures in Banach spaces
• scientific article; zbMATH DE number 3755545 (Why is no real title available?)
• scientific article; zbMATH DE number 3456359 (Why is no real title available?)
• scientific article; zbMATH DE number 3245885 (Why is no real title available?)
• Information of varying cardinality
• On the average complexity of multivariate problems
• Some nonlinear problems are as easy as the approximation problem

Cited in

(23)

• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• An information-based approach to ill-posed problems
• The algorithm designer versus nature: A game-theoretic approach to information-based complexity
• Complexity of fixed points. I
• Measures of uncertainty and information in computation
• Complexity of verification and computation for IBC problems
• Information complexity of equations of the second kind with compact operators in Hilbert space
• On the adaptive and continuous information problems
• Linear widths of a multivariate function space equipped with a Gaussian measure
• Information of varying cardinality
• De-noising by thresholding operator adapted wavelets
• Hyperbolic cross and the complexity of various classes of ill-posed linear problems
• Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
• Estimating information amount under uncertainty: algorithmic solvability and computational complexity
• Recent developments in information-based complexity
• scientific article; zbMATH DE number 922628 (Why is no real title available?)
• Information-theoretic lower bound on energy cost of stochastic computation
• Average complexity for linear operators over bounded domains
• Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
• Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure
• s-numbers in information-based complexity
• On sequential and parallel solution of initial value problems
• Orthogonally invariant measures and best approximation of linear operators

This page was built for publication: Probabilistic setting of information-based complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1092660)