Randomization for continuous problems
computational complexitycubature formulasextremal pointfunction inversefunctional evaluationslinear problems on Hilbert spacesmaximumrandom methodstopological degree
Degree, winding number (55M25) Algorithms for approximation of functions (65D15) Numerical quadrature and cubature formulas (65D32) Numerical solutions to equations with linear operators (65J10) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
The author deals with the computational complexity compran(\(\epsilon)\) for continuous problems with random methods, allowing the functional evaluations and the number of such evaluations to be chosen randomly with any arbitrary distribution. Integration problems are studied for which a sharp complexity lower bound is unknown. An approximation (with an error not exceeding \(\epsilon)\) is sought to \(S(f)=\int_{[0,1]^ d}f(x)dx\) for any function f: [0,1]\({}^ d\to {\mathbb{R}}\), whose derivatives up to order r are uniformly bounded in sup-norm (r\(\geq 0\) denotes regularity of f, \(d\geq 1\) is the number of variables in f). Then maximum, i.e. \(S(f)=\max_ xf(x),\) extremal point \(S(f)\in \arg \max_ xf(x),\) function inverse \(S(f)=f^{-1},\) topological degree \(S(f)=\deg (f),\) and linear problems on Hilbert spaces with unrestricted linear information are discussed.
- A Retrospective and Prospective Survey of the Monte Carlo Method
- An estimate of the mean remainder term in quadrature formulae
- Approximation of linear functionals on a Banach space with a Gaussian measure
- Average complexity for linear operators over bounded domains
- Complexity of computing topological degree of Lipschitz functions in n dimensions
- How powerful is continuous nonlinear information for linear problems?
- scientific article; zbMATH DE number 3850380 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- Information of varying cardinality
- Stochastic Quadrature Formulas
- The Monte Carlo method
- On the power of standard information for \(L_{\infty}\) approximation in the randomized setting
- The algorithm designer versus nature: A game-theoretic approach to information-based complexity
- Stochastic properties of quadrature formulas
- Optimal linear randomized methods for linear operators in Hilbert spaces
- Measures of uncertainty and information in computation
- Average case complexity of linear multivariate problems. II: Applications
- Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
- Complexity of Banach space valued and parametric stochastic Itô integration
- Computational complexity of continuous problems
- Average case complexity of linear multivariate problems
- The power of standard information for multivariate approximation in the randomized setting
- Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure
- scientific article; zbMATH DE number 866556 (Why is no real title available?)
- Liberating the dimension for function approximation and integration
- The randomized complexity of indefinite integration
- Approximate evaluations of characteristic polynomials of Boolean functions
- Integration error for multivariate functions from anisotropic classes
- Randomized approximation of Sobolev embeddings. II
- On piecewise-polynomial approximation of functions with a bounded fractional derivative in an \(L_ p\)-norm
- Infinite-dimensional quadrature and approximation of distributions
This page was built for publication: Randomization for continuous problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122297)
