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

Wasilkowski, G. W.

doi:10.1090/S0273-0979-1993-00379-3

Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure
HTML articles powered by AMS MathViewer

by G. W. Wasilkowski PDF

Bull. Amer. Math. Soc. 28 (1993), 308-314 Request permission

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

Z. Ciesielski, On Lévy’s Brownian motion with several-dimensional time, Probability—Winter School (Proc. Fourth Winter School, Karpacz, 1975) Lecture Notes in Math., Vol. 472, Springer, Berlin, 1975, pp. 29–56. MR 0391282
Seymour Haber, A modified Monte-Carlo quadrature, Math. Comp. 20 (1966), 361–368. MR 210285, DOI 10.1090/S0025-5718-1966-0210285-0
George S. Kimeldorf and Grace Wahba, A correspondence between Bayesian estimation on stochastic processes and smoothing by splines, Ann. Math. Statist. 41 (1970), 495–502. MR 254999, DOI 10.1214/aoms/1177697089
George S. Kimeldorf and Grace Wahba, Spline functions and stochastic processes, Sankhyā Ser. A 32 (1970), 173–180. MR 303594
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
D. Lee and G. W. Wasilkowski, Approximation of linear functionals on a Banach space with a Gaussian measure, J. Complexity 2 (1986), no. 1, 12–43. MR 925342, DOI 10.1016/0885-064X(86)90021-X
Paul Lévy, Processus stochastiques et mouvement brownien, Gauthier-Villars & Cie, Paris, 1965 (French). Suivi d’une note de M. Loève; Deuxième édition revue et augmentée. MR 0190953

On some problems concerning Brownian motion in Levy’s sense

12

Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792
Klaus Ritter, Approximation and optimization on the Wiener space, J. Complexity 6 (1990), no. 4, 337–364. MR 1085383, DOI 10.1016/0885-064X(90)90027-B
Jerome Sacks and Donald Ylvisaker, Designs for regression problems with correlated errors. III, Ann. Math. Statist. 41 (1970), 2057–2074. MR 270530, DOI 10.1214/aoms/1177696705
Jerome Sacks and Donald Ylvisaker, Statistical designs and integral approximation, Proc. Twelfth Biennial Sem. Canad. Math. Congr. on Time Series and Stochastic Processes; Convexity and Combinatorics (Vancouver, B.C., 1969) Canad. Math. Congr., Montreal, Que., 1970, pp. 115–136. MR 0277069

${L_p}$ approximation of autoregressive Gaussian process

A. V. Sul′din, Wiener measure and its applications to approximation methods. I, Izv. Vysš. Učebn. Zaved. Matematika 1959 (1959), no. 6 (13), 145–158 (Russian). MR 0157489
A. V. Sul′din, Wiener measure and its applications to approximation methods. II, Izv. Vysš. Učebn. Zaved. Matematika 1960 (1960), no. 5 (18), 165–179 (Russian). MR 0164183
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
Grace Wahba, On the regression design problem of Sacks and Ylvisaker, Ann. Math. Statist. 42 (1971), 1035–1053. MR 279955, DOI 10.1214/aoms/1177693331
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, Information of varying cardinality, J. Complexity 2 (1986), no. 3, 204–228. MR 922813, DOI 10.1016/0885-064X(86)90002-6
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 and F. Gao, On the power of adaptive information for functions with singularities, Math. Comp. 58 (1992), no. 197, 285–304. MR 1106987, DOI 10.1090/S0025-5718-1992-1106987-X
G. W. Wasilkowski and H. Woźniakowski, Can adaption help on the average?, Numer. Math. 44 (1984), no. 2, 169–190. MR 753951, DOI 10.1007/BF01410103
H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015, DOI 10.1090/S0273-0979-1991-15985-9
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