Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

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

PII: S 0273-0979(1993)00400-2
Article copyright: © Copyright 1993 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia