Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure


Author: G. W. Wasilkowski
Journal: Bull. Amer. Math. Soc. 28 (1993), 308-314
MSC: Primary 65Y20; Secondary 41A44, 41A65, 65D15, 65D30
DOI: https://doi.org/10.1090/S0273-0979-1993-00379-3
MathSciNet review: 1184000
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the average case complexity of multivariate integration and $ {L_{2}}$ function approximation for the class $ {F = C([0,1]^{d})}$ of continuous functions of d variables. The class F is endowed with the isotropic Wiener measure (Brownian motion in Levy's sense). Furthermore, for both problems, only function values are used as data.


References [Enhancements On Off] (What's this?)

  • [1] Z. Ciesielski, On Levy's Brownian motion with several-dimensional time, Lecture Notes in Math., vol. 472, Springer-Verlag, New York, 1975, pp. 29-56. MR 0391282 (52:12103)
  • [2] S. Haber, A modified Monte Carlo quadrature, Math. Comp. 20 (1966), 361-368. MR 0210285 (35:1178)
  • [3] G. S. Kimeldorf and G. Wahba, A correspondence between Bayesian estimation on stochastic processes and smoothing by splines, Ann. Math. Stat. 41 (1970), 495-502. MR 0254999 (40:8206)
  • [4] -, Spline functions and stochastic processes, Sankhya Ser. A 32 (1970), 173-180. MR 0303594 (46:2731)
  • [5] D. Lee, Approximation of linear operators on a Wiener space, Rocky Mountain J. Math. 16 (1986), 641-659. MR 871027 (88f:41053)
  • [6] D. Lee and G. W. Wasilkowski, Approximation of linear functionals on a Banach space with a Gaussian measure, J. Complexity 2 (1986), 12-43. MR 925342 (88m:65088)
  • [7] P. Levy, Processus stochastique et mouvement Brownien, Gauthier-Villars, Paris, 1948. MR 0190953 (32:8363)
  • [8] G. M. Molchan, On some problems concerning Brownian motion in Levy's sense, Theory Probab. Appl. 12 (1967), 682-690.
  • [9] E. Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Math., vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255 (90a:65004)
  • [10] K. Ritter, Approximation and optimization on the Wiener space, J. Complexity 6 (1990), 337-364. MR 1085383 (91k:90135)
  • [11] J. Sacks and D. Ylvisaker, Design for regression problems with correlated errors. III, Ann. Math. Stat. 41 (1970), 2057-2074. MR 0270530 (42:5418)
  • [12] -, Statistical design and integral approximation, Proc. 12th Bienn. Sem. Canad. Math. Congr., Montreal, 1970, pp. 115-136. MR 0277069 (43:2806)
  • [13] P. Speckman, $ {L_p}$ approximation of autoregressive Gaussian process, report, Department of Statistics, University of Oregon, Eugene, OR, 1979.
  • [14] A. V. Suldin, Wiener measure and its applications to approximation methods. I, Izv. Vyssh. Ucheb. Zaved. Mat. 13 (1959), 145-158. (Russian) MR 0157489 (28:722)
  • [15] -, Wiener measure and its applications to approximation methods. II, Izv. Vyssh. Ucheb. Zaved. Mat. 18 (1960), 165-179. (Russian) MR 0164183 (29:1482)
  • [16] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Academic Press, New York, 1988. MR 958691 (90f:68085)
  • [17] G. Wahba, On the regression design problem of Sacks and Ylvisaker, Ann. Math. Stat. 42 (1971), 1035-1043. MR 0279955 (43:5676)
  • [18] -, Spline models for observational data, SIAM-NSF Regional Conf. Ser. in Appl. Math., vol. 59, SIAM, Philadelphia, PA, 1990. MR 1045442 (91g:62028)
  • [19] G. W. Wasilkowski, Information of varying cardinality, J. Complexity 2 (1986), 204-228. MR 922813 (88m:65099)
  • [20] -, Randomization for continuous problems, J. Complexity 5 (1989), 195-218. MR 1006106 (91a:65006)
  • [21] G. W. Wasilkowski and F. Gao, On the power of adaptive information for functions with singularities, Math. Comp. 58 (1992), 285-304. MR 1106987 (92f:65027)
  • [22] G. W. Wasilkowski and H. Woźniakowski, Can adaption help on the average?, Numer. Math. 44 (1984), 169-190. MR 753951 (86d:68035)
  • [23] H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), 185-194. MR 1072015 (91i:65224)
  • [24] -, Average case complexity of linear multivariate problems, (to appear in Bull. Amer. Math. Soc. (N.S.)). MR 1193541 (94a:65076a)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC: 65Y20, 41A44, 41A65, 65D15, 65D30

Retrieve articles in all journals with MSC: 65Y20, 41A44, 41A65, 65D15, 65D30


Additional Information

DOI: https://doi.org/10.1090/S0273-0979-1993-00379-3
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society