Average case complexity of linear multivariate problems. I: Theory

DOI10.1016/0885-064X(92)90001-RMaRDI QIDQ1203639zbMATH OpenFDO

Authors H. Woźniakowski

Publication date 22 February 1993

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

Full work available at URL https://arxiv.org/abs/math/9307234

zbMATH Keywords

linear multivariate problemstractability

Mathematics Subject Classification ID

Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.) (28C20) Approximation by positive operators (41A36) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study the average case complexity of a linear multivariate problem $(lmp)$ defined on functions of $d$ variables. We consider two classes of information. The first $lstd$ consists of function values and the second $lall$ of all continuous linear functionals. Tractability of $lmp$ means that the average case complexity is $O((1/e{)}^p)$ with $p$ independent of $d$. We prove that tractability of an $lmp$ in $lstd$ is equivalent to tractability in $lall$, although the proof is {it not} constructive. We provide a simple condition to check tractability in $lall$. We also address the optimal design problem for an $lmp$ by using a relation to the worst case setting. We find the order of the average case complexity and optimal sample points for multivariate function approximation. The theoretical results are illustrated for the folded Wiener sheet measure.

Recommendations

• Average case complexity of linear multivariate problems
• Average case tractability of a multivariate approximation problem
• Tractability of linear multivariate problems in the average case setting
• Average case complexity of linear multivariate problems. II: Applications
• A survey of average case complexity for linear multivariate problems

Cites work

• A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines
• Average case complexity of multivariate integration for smooth functions
• Counterexamples in optimal quadrature
• Designs for Regression Problems with Correlated Errors
• Designs for Regression Problems with Correlated Errors III
• Designs for Regression Problems With Correlated Errors: Many Parameters
• Deterministic and stochastic error bounds in numerical analysis
• Gaussian measures in Banach spaces
• scientific article; zbMATH DE number 3755545 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 45848 (Why is no real title available?)
• scientific article; zbMATH DE number 3456359 (Why is no real title available?)
• scientific article; zbMATH DE number 3509627 (Why is no real title available?)
• scientific article; zbMATH DE number 3601500 (Why is no real title available?)
• scientific article; zbMATH DE number 3359503 (Why is no real title available?)
• Information of varying cardinality
• Information-based complexity: New questions for mathematicians
• Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure
• On the optimality of linear methods for operator approximation in convex classes of functions
• On the Regression Design Problem of Sacks and Ylvisaker

Cited in

(26)

• Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting
• Complexity of multilinear problems in the average case setting
• Average case complexity of linear multivariate problems. II: Applications
• Average case complexity of multivariate integration for smooth functions
• Tractability and strong tractability of linear multivariate problems
• A note on varying cardinality in the average case setting
• Integration and \(L_ 2\)-approximation: Average case setting with isotropic Wiener measure for smooth functions
• Adaptive wavelet methods for the stochastic Poisson equation
• Applicability of Smolyak's algorithms to certain Banach spaces of multivariate functions.
• Average case tractability of a multivariate approximation problem
• On optimal allocations for estimating the surface of a random field
• Computational complexity in worst, stochastic and average case setting on functional approximation problem of multivariate
• Noisy information: optimality, complexity, tractability
• Average case complexity of linear multivariate problems
• A framework for controlling sources of inaccuracy in Gaussian process emulation of deterministic computer experiments
• Does Increased Regularity Lower Complexity?
• Average case complexity of multivariate integration
• Tractability of linear multivariate problems in the average case setting
• A survey of average case complexity for linear multivariate problems
• A fast average case algorithm for lyndon decomposition
• Fast prediction of deterministic functions using sparse grid experimental designs
• Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure
• Complexity of multilinear problems in the worst case setting
• On the average complexity of multivariate problems
• Average case optimality for linear problems
• Average-case complexity of the min-sum matrix product problem

This page was built for publication: Average case complexity of linear multivariate problems. I: Theory

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