Average case tractability of approximating ∞-variate functions

Wasilkowski, G.

doi:10.1090/S0025-5718-2013-02759-7

Average case tractability of approximating $\infty$-variate functions
HTML articles powered by AMS MathViewer

by G. W. Wasilkowski PDF

Math. Comp. 83 (2014), 1319-1336 Request permission

Abstract:

We study function approximation in the average case setting for spaces of $\infty$-variate functions that have a weighted tensor product form and are endowed with a Gaussian measure that also has a weighted tensor product form. Moreover, we assume that the cost of function evaluation depends on the number of active variables and we allow it to be from linear to exponential. We provide a necessary and sufficient condition for the problem to be polynomially tractable and derive the exact value of the tractability exponent. In particular, the approximation problem is polynomially tractable under modest conditions on weights even if the function evaluation cost is exponential in the number of active variables. The problem is weakly tractable even if this cost is doubly exponential. These results hold for algorithms that can use unrestricted linear information. Similar results hold for weighted $L_2$ approximation, a special case of function approximation problems considered in this paper, and algorithms restricted to those that use only function samplings.

References

Ivo Babuška, Fabio Nobile, and Raúl Tempone, A stochastic collocation method for elliptic partial differential equations with random input data, SIAM J. Numer. Anal. 45 (2007), no. 3, 1005–1034. MR 2318799, DOI 10.1137/050645142
Jakob Creutzig, Steffen Dereich, Thomas Müller-Gronbach, and Klaus Ritter, Infinite-dimensional quadrature and approximation of distributions, Found. Comput. Math. 9 (2009), no. 4, 391–429. MR 2519865, DOI 10.1007/s10208-008-9029-x
A. Das, Field Theory: A Path Integral Approach, Lecture Notes in Physics, Vol. 52, World Scientific, Singapore, 1993.
C. DeWitt-Morette (editor), Special Issue on Functional Integration, J. Mathematical Physics 36 (1995).
D. Duffie, Dynamic Asset Pricing Theory, Princeton University, Princeton, NJ, 1996.
R. P. Egorov, P. I. Sobolevsky, and L. A. Yanovich, Functional Integrals: Approximate Evaluation and Applications, Kluver Academic, Dordrecht, 1993.
Richard P. Feynman and Albert R. Hibbs, Quantum mechanics and path integrals, Emended edition, Dover Publications, Inc., Mineola, NY, 2010. Emended and with a preface by Daniel F. Styer. MR 2797644
M. Gnewuch, Infinite-dimensional integration on weighted Hilbert spaces, submitted.
Fred J. Hickernell, Thomas Müller-Gronbach, Ben Niu, and Klaus Ritter, Multi-level Monte Carlo algorithms for infinite-dimensional integration on $\Bbb R^{\Bbb N}$, J. Complexity 26 (2010), no. 3, 229–254. MR 2657363, DOI 10.1016/j.jco.2010.02.002
Fred Hickernell, Greg Wasilkowski, and Henryk Woźniakowski, Tractability of linear multivariate problems in the average case setting, Monte Carlo and quasi-Monte Carlo methods 2006, Springer, Berlin, 2008, pp. 461–493. MR 2479240, DOI 10.1007/978-3-540-74496-2_{2}7
F. J. Hickernell and H. Woźniakowski, Integration and approximation in arbitrary dimensions, Adv. Comput. Math. 12 (2000), no. 1, 25–58. High dimensional integration. MR 1758946, DOI 10.1023/A:1018948631251
J. C. Hull, Option, Futures, and Other Derivatives, 5th ed., Upper Saddle River, New Jersey, 2002.
D. C. Khandekar, S. V. Lawande, and K. V. Bhagwat, Path-integral methods and their applications, World Scientific Publishing Co., Inc., River Edge, NJ, 1993. MR 1227096, DOI 10.1142/1332
Hagen Kleinert, Path integrals in quantum mechanics, statistics, and polymer physics, World Scientific Publishing Co., Inc., River Edge, NJ, 1990. MR 1141623, DOI 10.1142/1081
Frances Y. Kuo, Christoph Schwab, and Ian H. Sloan, Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients, SIAM J. Numer. Anal. 50 (2012), no. 6, 3351–3374. MR 3024159, DOI 10.1137/110845537
Frances Y. Kuo, Ian H. Sloan, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, Liberating the dimension, J. Complexity 26 (2010), no. 5, 422–454. MR 2719642, DOI 10.1016/j.jco.2009.12.003
F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, and H. Woźniakowski, On decompositions of multivariate functions, Math. Comp. 79 (2010), no. 270, 953–966. MR 2600550, DOI 10.1090/S0025-5718-09-02319-9
R. Merton, Continuous–Time Finance, Basil Blackwell, Oxford, 1990.
Ben Niu and Fred J. Hickernell, Monte Carlo simulation of stochastic integrals when the cost of function evaluation is dimension dependent, Monte Carlo and quasi-Monte Carlo methods 2008, Springer, Berlin, 2009, pp. 545–560. MR 2743918, DOI 10.1007/978-3-642-04107-5_{3}5
Ben Niu, Fred J. Hickernell, Thomas Müller-Gronbach, and Klaus Ritter, Deterministic multi-level algorithms for infinite-dimensional integration on $\Bbb R^{\Bbb N}$, J. Complexity 27 (2011), no. 3-4, 331–351. MR 2793867, DOI 10.1016/j.jco.2010.08.001
F. Nobile, R. Tempone, and C. G. Webster, A sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal. 46 (2008), no. 5, 2309–2345. MR 2421037, DOI 10.1137/060663660
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032, DOI 10.4171/084
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
L. Plaskota and G. W. Wasilkowski, Tractability of infinite-dimensional integration in the worst case and randomized settings, J. Complexity 27 (2011), no. 6, 505–518. MR 2846702, DOI 10.1016/j.jco.2011.01.006
Leszek Plaskota, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, A new algorithm and worst case complexity for Feynman-Kac path integration, J. Comput. Phys. 164 (2000), no. 2, 335–353. MR 1792515, DOI 10.1006/jcph.2000.6599
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. W. Wasilkowski, Optimal algorithms for linear problems with Gaussian measures, Rocky Mountain J. Math. 16 (1986), no. 4, 727–749. MR 871033, DOI 10.1216/RMJ-1986-16-4-727
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, Liberating the dimension for $L_2$-approximation, J. Complexity 28 (2012), no. 3, 304–319. MR 2914730, DOI 10.1016/j.jco.2011.12.002
G. W. Wasilkowski and H. Woźniakowski, Average case optimal algorithms in Hilbert spaces, J. Approx. Theory 47 (1986), no. 1, 17–25. MR 843452, DOI 10.1016/0021-9045(86)90043-2
Grzegorz W. Wasilkowski and Henryk Woźniakowski, On tractability of path integration, J. Math. Phys. 37 (1996), no. 4, 2071–2086. MR 1380891, DOI 10.1063/1.531493
G. W. Wasilkowski and H. Woźniakowski, Liberating the dimension for function approximation, J. Complexity 27 (2011), no. 1, 86–110. MR 2745302, DOI 10.1016/j.jco.2010.08.004
G. W. Wasilkowski and H. Woźniakowski, Liberating the dimension for function approximation: standard information, J. Complexity 27 (2011), no. 5, 417–440. MR 2805529, DOI 10.1016/j.jco.2011.02.002
F. W. Wiegel, Introduction to path-integral methods in physics and polymer science, World Scientific Publishing Co., Singapore, 1986. MR 868281, DOI 10.1142/0178