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

tractabilitylinear multivariate problems

Mathematics Subject Classification ID

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

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

• 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?)
• 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: Many Parameters
• Designs for Regression Problems with Correlated Errors
• Designs for Regression Problems with Correlated Errors III
• Deterministic and stochastic error bounds in numerical analysis
• Gaussian measures in Banach spaces
• 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 Regression Design Problem of Sacks and Ylvisaker
• On the optimality of linear methods for operator approximation in convex classes of functions

Cited in

(24)

• Integration and \(L_ 2\)-approximation: Average case setting with isotropic Wiener measure for smooth functions
• Fast prediction of deterministic functions using sparse grid experimental designs
• Adaptive wavelet methods for the stochastic Poisson equation
• Does Increased Regularity Lower Complexity?
• Tractability and strong tractability of linear multivariate problems
• Complexity of multilinear problems in the average case setting
• Tractability of linear multivariate problems in the average case setting
• Applicability of Smolyak's algorithms to certain Banach spaces of multivariate functions.
• A fast average case algorithm for lyndon decomposition
• Complexity of multilinear problems in the worst case setting
• Average case optimality for linear problems
• Noisy information: optimality, complexity, tractability
• A survey of average case complexity for linear multivariate problems
• 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
• 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
• A framework for controlling sources of inaccuracy in Gaussian process emulation of deterministic computer experiments
• Average case tractability of a multivariate approximation problem
• Average case complexity of linear multivariate problems. II: Applications
• Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting
• A note on varying cardinality in the average case setting
• Average case complexity of multivariate integration for smooth functions
• Average case complexity of linear multivariate problems

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)