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

DOI:
https://doi.org/10.1090/S0273-0979-1993-00400-2

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 consists of function values and the second of all continuous linear functionals. Tractability of LMP means that the average case complexity is with *p* independent of *d*. We prove that tractability of an LMP in is equivalent to tractability in , although the proof is *not* constructive. We provide a simple condition to check tractability in .

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.

**[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), no. 4, 641–659. MR**871027**, https://doi.org/10.1216/RMJ-1986-16-4-641**[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), no. 1, 1–23. MR**1048027**, https://doi.org/10.1016/0885-064X(90)90009-3**[5]**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**, https://doi.org/10.1006/jcom.1993.1019**[6]**P. Speckman,*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*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR**958691****[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]**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****[12]**G. W. Wasilkowski,*Randomization for continuous problems*, J. Complexity**5**(1989), no. 2, 195–218. MR**1006106**, https://doi.org/10.1016/0885-064X(89)90004-6**[13]**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**, https://doi.org/10.1090/S0273-0979-1993-00379-3**[14]**Arthur G. Werschulz,*Counterexamples in optimal quadrature*, Aequationes Math.**29**(1985), no. 2-3, 183–203. MR**819308**, https://doi.org/10.1007/BF02189827**[15]**H. Woźniakowski,*Average case complexity of multivariate integration*, Bull. Amer. Math. Soc. (N.S.)**24**(1991), 185-194.**[16]**H. Woźniakowski,*Average case complexity of linear multivariate problems. I. Theory*, J. Complexity**8**(1992), no. 4, 337–372. MR**1195257**, https://doi.org/10.1016/0885-064X(92)90001-R

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

DOI:
https://doi.org/10.1090/S0273-0979-1993-00400-2

Article copyright:
© Copyright 1993
American Mathematical Society