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 Free Access

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?)

  • [1] K. I. Babenko, On the approximation of a class of periodic functions of several variables by trigonometric polynomials, Dokl. Akad. Nauk SSSR 132 (1960), 247-250, 982-985; English transl. in Soviet Math. Dokl. 1 (1960).
  • [2] D. Lee, Approximation of linear operators on a Wiener space, Rocky Mountain J. Math. 16 (1986), 641-659. MR 871027 (88f:41053)
  • [3] A. Papageorgiou, Average case complexity bounds for continuous problems, Ph.D. thesis, Dept. of Computer Science, Columbia University, 1990.
  • [4] A. Papageorgiou and G. W. Wasilkowski, On the average complexity of multivariate problems, J. Complexity 6 (1990), 1-23. MR 1048027 (91b:94020)
  • [5] S. Paskov, Average case complexity of multivariate integration for smooth functions, (to appear in J. Complexity, 1993). MR 1226314 (94f:65135)
  • [6] P. Speckman, $ {L_p}$ approximation of autoregressive Gaussian processes, Ph.D. thesis, Dept. of Math., UCLA, 1976.
  • [7] V. N. Temlyakov, Approximate recovery of periodic functions of several variables, Math. USSR-Sb. 56 (1987), 249-261.
  • [8] -, Private communication, 1991.
  • [9] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Academic Press, New York, 1988. MR 958691 (90f:68085)
  • [10] G. Wahba, Interpolating surfaces: high order convergence rates and their associated designs, with application to X-ray image reconstruction, Dept. of Statistics, University of Wisconsin, 1978.
  • [11] -, Spline models for observational data, CBMS-NSF Regional Conf. Ser. in Appl. Math., vol. 59, SIAM, Philadelphia, PA, 1990. MR 1045442 (91g:62028)
  • [12] G. W. Wasilkowski, Randomization for continuous problems, J. Complexity 5 (1989), 195-218. MR 1006106 (91a:65006)
  • [13] -, Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure, Bull. Amer. Math. Soc. (N.S.) 28 (1993) (to appear). MR 1184000 (93i:65136)
  • [14] A. G. Werschulz, Counterexamples in optimal quadratures, Aequationes Math. 29 (1985), 183-202. MR 819308 (87f:65032)
  • [15] H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), 185-194.
  • [16] -, Average case complexity of linear multivariate problems, Part I: Theory, Part II: Applications, Dept. of Computer Science, Columbia University, J. Complexity 8 (1992), 337-392. MR 1195257 (94a:65076b)

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