On the average complexity of multivariate problems
From MaRDI portal
Publication:757054
A linear problem is the approximation of S(f), where S is a continuous linear operation S: \(F_ 1\to F_ 2\). It is typically assumed that \(F_ 2\) is a separable Hilbert space, and either \(F_ 1\) is also a separable Hilbert space or S is of some special form. Known results are extended for the case where \(F_ 1\) is a separable Banach space equipped with a Gaussian or orthogonally invariant measure, and S is an arbitrary continuous linear operator. The results are applied to the approximation of real functions of d variables. In particular, it is shown that the average complexity of this problem is almost independent of the dimension d if arbitrary linear functionals are permitted in the information.
Recommendations
- Average case complexity of linear multivariate problems. I: Theory
- Average case complexity of linear multivariate problems. II: Applications
- Tractability of linear multivariate problems in the average case setting
- A survey of average case complexity for linear multivariate problems
- Complexity of multilinear problems in the average case setting
Cites work
- A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines
- Approximation of linear functionals on a Banach space with a Gaussian measure
- Average case optimal algorithms in Hilbert spaces
- Average case optimality
- Can adaption help on the average?
- Elliptically contoured measures on infinite-dimensional Banach spaces
- Gaussian measures in Banach spaces
- scientific article; zbMATH DE number 3688714 (Why is no real title available?)
- scientific article; zbMATH DE number 3751955 (Why is no real title available?)
- 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 3204642 (Why is no real title available?)
- scientific article; zbMATH DE number 3250960 (Why is no real title available?)
- Optimal algorithms for linear problems with Gaussian measures
Cited in
(42)- On the power of standard information for multivariate approximation in the worst case setting
- Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting
- Probabilistic setting of information-based complexity
- Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
- Complexity of multilinear problems in the average case setting
- Function approximation and integration on the Wiener space with noisy data
- Average case complexity of linear multivariate problems. II: Applications
- Average case complexity of elliptic partial differential equations
- Hyperbolic cross designs for approximation of random fields
- Special issue: Complexity of multivariate problems. Papers of the workshop, Baptist Univ., Hong Kong, China, October 4--8, 1999
- Testing linear operators -- an average case study
- Average approximations and moments of measures
- Adaptive wavelet methods for the stochastic Poisson equation
- Linear widths of a multivariate function space equipped with a Gaussian measure
- Information of varying cardinality
- Sharp asymptotics of the functional quantization problem for Gaussian processes.
- Testing linear operators
- Average case tractability of a multivariate approximation problem
- Estimation and detection of a function from tensor product spaces
- High-resolution product quantization for Gaussian processes under sup-norm distortion
- On optimal allocations for estimating the surface of a random field
- Approximation and optimization on the Wiener space
- Average case complexity of linear multivariate problems
- Average case complexity of multivariate integration
- The power of standard information for multivariate approximation in the randomized setting
- Tractability of linear multivariate problems in the average case setting
- Average case tractability of non-homogeneous tensor product problems
- On spectral asymptotics of the tensor product of operators with almost regular marginal asymptotics
- A survey of average case complexity for linear multivariate problems
- Approximation of additive random fields based on standard information: average case and probabilistic settings
- On the average complexity of the $k$-level
- Kriging prediction with isotropic Matérn correlations: robustness and experimental designs
- Average case tractability of approximating -variate functions
- Small ball probabilities for smooth Gaussian fields and tensor products of compact operators
- Small ball probabilities for Gaussian random fields and tensor products of compact operators
- Average complexity for linear operators over bounded domains
- L₂-small ball asymptotics for Gaussian random functions: a survey
- Linear vs standard information for scalar stochastic differential equations
- Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure
- Average-case complexity of the min-sum matrix product problem
- Approximation complexity of additive random fields
- Multivariate \(L_{\infty}\) approximation in the worst case setting over reproducing kernel Hilbert spaces
This page was built for publication: On the average complexity of multivariate problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757054)
