Average case complexity of linear multivariate problems
Author:
H. Woźniakowski
Journal:
Bull. Amer. Math. Soc. 29 (1993), 7076
MSC (2000):
Primary 65Y20; Secondary 65D15, 68Q25
MathSciNet review:
1193541
Fulltext 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), 247250, 982985; 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 (88f:41053), http://dx.doi.org/10.1216/RMJ1986164641
 [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 (91b:94020), http://dx.doi.org/10.1016/0885064X(90)900093
 [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
(94f:65135), http://dx.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. USSRSb. 56 (1987), 249261.
 [8]
, Private communication, 1991.
 [9]
J.
F. Traub, G.
W. Wasilkowski, and H.
Woźniakowski, Informationbased complexity, Computer
Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988.
With contributions by A. G. Werschulz and T. Boult. MR 958691
(90f:68085)
 [10]
G. Wahba, Interpolating surfaces: high order convergence rates and their associated designs, with application to Xray image reconstruction, Dept. of Statistics, University of Wisconsin, 1978.
 [11]
Grace
Wahba, Spline models for observational data, CBMSNSF Regional
Conference Series in Applied Mathematics, vol. 59, Society for
Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442
(91g:62028)
 [12]
G.
W. Wasilkowski, Randomization for continuous problems, J.
Complexity 5 (1989), no. 2, 195–218. MR 1006106
(91a:65006), http://dx.doi.org/10.1016/0885064X(89)900046
 [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
(93i:65136), http://dx.doi.org/10.1090/S027309791993003793
 [14]
Arthur
G. Werschulz, Counterexamples in optimal quadrature,
Aequationes Math. 29 (1985), no. 23, 183–203.
MR 819308
(87f:65032), http://dx.doi.org/10.1007/BF02189827
 [15]
H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), 185194.
 [16]
H.
Woźniakowski, Average case complexity of linear multivariate
problems. I. Theory, J. Complexity 8 (1992),
no. 4, 337–372. MR 1195257
(94a:65076b), http://dx.doi.org/10.1016/0885064X(92)90001R
 [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), 247250, 982985; 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), 641659. 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), 123. 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, 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. USSRSb. 56 (1987), 249261.
 [8]
 , Private communication, 1991.
 [9]
 J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Informationbased 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 Xray image reconstruction, Dept. of Statistics, University of Wisconsin, 1978.
 [11]
 , Spline models for observational data, CBMSNSF 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), 195218. 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), 183202. MR 819308 (87f:65032)
 [15]
 H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), 185194.
 [16]
 , Average case complexity of linear multivariate problems, Part I: Theory, Part II: Applications, Dept. of Computer Science, Columbia University, J. Complexity 8 (1992), 337392. 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
DOI:
http://dx.doi.org/10.1090/S027309791993004002
PII:
S 02730979(1993)004002
Article copyright:
© Copyright 1993
American Mathematical Society
