Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



Average case complexity of linear multivariate problems

Author: H. Woźniakowski
Journal: Bull. Amer. Math. Soc. 29 (1993), 70-76
MSC (2000): Primary 65Y20; Secondary 65D15, 68Q25
MathSciNet review: 1193541
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ {\Lambda ^{std}}$ consists of function values and the second $ {\Lambda ^{all}}$ of all continuous linear functionals. Tractability of LMP means that the average case complexity is $ O({(1/\varepsilon )^p})$ with p independent of d. We prove that tractability of an LMP in $ {\Lambda ^{std}}$ is equivalent to tractability in $ {\Lambda ^{all}}$, although the proof is not constructive. We provide a simple condition to check tractability in $ {\Lambda ^{all}}$.

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 65Y20, 65D15, 68Q25

Retrieve articles in all journals with MSC (2000): 65Y20, 65D15, 68Q25

Additional Information

Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society