Average case complexity of linear multivariate problems
HTML articles powered by AMS MathViewer
- by H. Woźniakowski PDF
- Bull. Amer. Math. Soc. 29 (1993), 70-76 Request permission
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
-
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).
- D. Lee, Approximation of linear operators on a Wiener space, Rocky Mountain J. Math. 16 (1986), no. 4, 641–659. MR 871027, DOI 10.1216/RMJ-1986-16-4-641 A. Papageorgiou, Average case complexity bounds for continuous problems, Ph.D. thesis, Dept. of Computer Science, Columbia University, 1990.
- A. Papageorgiou and G. W. Wasilkowski, On the average complexity of multivariate problems, J. Complexity 6 (1990), no. 1, 1–23. MR 1048027, DOI 10.1016/0885-064X(90)90009-3
- S. H. Paskov, Average case complexity of multivariate integration for smooth functions, J. Complexity 9 (1993), no. 2, 291–312. Festschrift for Joseph F. Traub, Part II. MR 1226314, DOI 10.1006/jcom.1993.1019 P. Speckman, ${L_p}$ approximation of autoregressive Gaussian processes, Ph.D. thesis, Dept. of Math., UCLA, 1976. V. N. Temlyakov, Approximate recovery of periodic functions of several variables, Math. USSR-Sb. 56 (1987), 249-261. —, Private communication, 1991.
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691 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.
- Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442, DOI 10.1137/1.9781611970128
- G. W. Wasilkowski, Randomization for continuous problems, J. Complexity 5 (1989), no. 2, 195–218. MR 1006106, DOI 10.1016/0885-064X(89)90004-6
- G. W. Wasilkowski, Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure, Bull. Amer. Math. Soc. (N.S.) 28 (1993), no. 2, 308–314. MR 1184000, DOI 10.1090/S0273-0979-1993-00379-3
- Arthur G. Werschulz, Counterexamples in optimal quadrature, Aequationes Math. 29 (1985), no. 2-3, 183–203. MR 819308, DOI 10.1007/BF02189827 H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), 185-194.
- H. Woźniakowski, Average case complexity of linear multivariate problems, Bull. Amer. Math. Soc. (N.S.) 29 (1993), no. 1, 70–76. MR 1193541, DOI 10.1090/S0273-0979-1993-00400-2
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 29 (1993), 70-76
- MSC (2000): Primary 65Y20; Secondary 65D15, 68Q25
- DOI: https://doi.org/10.1090/S0273-0979-1993-00400-2
- MathSciNet review: 1193541