Average case complexity of linear multivariate problems. I: Theory

DOI10.1016/0885-064X(92)90001-RzbMath0767.41028arXivmath/9307234MaRDI QIDQ1203639

Henryk 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) Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.) (28C20) Approximation by positive operators (41A36)

Related Items

Applicability of Smolyak's algorithms to certain Banach spaces of multivariate functions. ⋮ A Framework for Controlling Sources of Inaccuracy in Gaussian Process Emulation of Deterministic Computer Experiments ⋮ 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 ⋮ A survey of average case complexity for linear multivariate problems ⋮ Average case complexity of linear multivariate problems. II: Applications ⋮ Adaptive wavelet methods for the stochastic Poisson equation ⋮ Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure ⋮ On optimal allocations for estimating the surface of a random field

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Information-based complexity: New questions for mathematicians
• Deterministic and stochastic error bounds in numerical analysis
• Gaussian measures in Banach spaces
• Average case complexity of multivariate integration for smooth functions
• Counterexamples in optimal quadrature
• Information of varying cardinality
• Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure
• Designs for Regression Problems with Correlated Errors
• Designs for Regression Problems With Correlated Errors: Many Parameters
• A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines
• On the Regression Design Problem of Sacks and Ylvisaker
• Designs for Regression Problems with Correlated Errors III
• On the optimality of linear methods for operator approximation in convex classes of functions