Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Average case tractability of approximating $ \infty$-variate functions


Author: G. W. Wasilkowski
Journal: Math. Comp. 83 (2014), 1319-1336
MSC (2010): Primary 41A65, 47B06, 68Q17
DOI: https://doi.org/10.1090/S0025-5718-2013-02759-7
Published electronically: August 1, 2013
MathSciNet review: 3167460
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2008e:65372), https://doi.org/10.1137/050645142
  • [2] 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 (2010h:65027), https://doi.org/10.1007/s10208-008-9029-x
  • [3] A. Das, Field Theory: A Path Integral Approach, Lecture Notes in Physics, Vol.52, World Scientific, Singapore, 1993.
  • [4] C. DeWitt-Morette (editor), Special Issue on Functional Integration, J.Mathematical Physics 36 (1995).
  • [5] D. Duffie, Dynamic Asset Pricing Theory, Princeton University, Princeton, NJ, 1996.
  • [6] R. P. Egorov, P. I. Sobolevsky, and L. A. Yanovich, Functional Integrals: Approximate Evaluation and Applications, Kluver Academic, Dordrecht, 1993.
  • [7] R. P. Feynman and A. R. Hibbs, Quantum Mechanics and Path-Integrals, McGraw-Hill, New York, 1965. MR 2797644 (2012e:81127)
  • [8] M. Gnewuch, Infinite-dimensional integration on weighted Hilbert spaces, submitted.
  • [9] Fred J. Hickernell, Thomas Müller-Gronbach, Ben Niu, and Klaus Ritter, Multi-level Monte Carlo algorithms for infinite-dimensional integration on $ \mathbb{R}^{\mathbb{N}}$, J. Complexity 26 (2010), no. 3, 229-254. MR 2657363 (2011d:65008), https://doi.org/10.1016/j.jco.2010.02.002
  • [10] 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 (2010i:60019), https://doi.org/10.1007/978-3-540-74496-2_27
  • [11] 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 (2001d:65017), https://doi.org/10.1023/A:1018948631251
  • [12] J. C. Hull, Option, Futures, and Other Derivatives, 5th ed., Upper Saddle River, New Jersey, 2002.
  • [13] 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 (94f:81090)
  • [14] Hagen Kleinert, Path integrals in quantum mechanics, statistics, and polymer physics, World Scientific Publishing Co. Inc., River Edge, NJ, 1990. MR 1141623 (93f:81070)
  • [15] F. Y. Kuo, Ch. Schwab, and I. 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
  • [16] 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 (2012a:65055), https://doi.org/10.1016/j.jco.2009.12.003
  • [17] 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 (2011a:41039), https://doi.org/10.1090/S0025-5718-09-02319-9
  • [18] R. Merton, Continuous-Time Finance, Basil Blackwell, Oxford, 1990.
  • [19] 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 (2012b:65007), https://doi.org/10.1007/978-3-642-04107-5_35
  • [20] Ben Niu, Fred J. Hickernell, Thomas Müller-Gronbach, and Klaus Ritter, Deterministic multi-level algorithms for infinite-dimensional integration on $ \mathbb{R}^{\mathbb{N}}$, J. Complexity 27 (2011), no. 3-4, 331-351. MR 2793867 (2012b:65034), https://doi.org/10.1016/j.jco.2010.08.001
  • [21] 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 (2009f:65257), https://doi.org/10.1137/060663660
  • [22] 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 (2009m:46037)
  • [23] 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 (2011h:46093)
  • [24] 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), https://doi.org/10.1016/0885-064X(90)90009-3
  • [25] 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 (2012k:65183), https://doi.org/10.1016/j.jco.2011.01.006
  • [26] 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 (2001i:65146), https://doi.org/10.1006/jcph.2000.6599
  • [27] 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 (90f:68085)
  • [28] G. W. Wasilkowski, Optimal algorithms for linear problems with Gaussian measures, Rocky Mountain J. Math. 16 (1986), no. 4, 727-749. MR 871033 (88a:28018), https://doi.org/10.1216/RMJ-1986-16-4-727
  • [29] G. W. Wasilkowski, Information of varying cardinality, J. Complexity 2 (1986), no. 3, 204-228. MR 922813 (88m:65099), https://doi.org/10.1016/0885-064X(86)90002-6
  • [30] G. W. Wasilkowski, Liberating the dimension for $ L_2$-approximation, J. Complexity 28 (2012), no. 3, 304-319. MR 2914730, https://doi.org/10.1016/j.jco.2011.12.002
  • [31] 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 (87k:41028), https://doi.org/10.1016/0021-9045(86)90043-2
  • [32] Grzegorz W. Wasilkowski and Henryk Woźniakowski, On tractability of path integration, J. Math. Phys. 37 (1996), no. 4, 2071-2086. MR 1380891 (97a:65010), https://doi.org/10.1063/1.531493
  • [33] G. W. Wasilkowski and H. Woźniakowski, Liberating the dimension for function approximation, J. Complexity 27 (2011), no. 1, 86-110. MR 2745302 (2011j:41044), https://doi.org/10.1016/j.jco.2010.08.004
  • [34] 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 (2012e:41044), https://doi.org/10.1016/j.jco.2011.02.002
  • [35] F. W. Wiegel, Introduction to path-integral methods in physics and polymer science, World Scientific Publishing Co., Singapore, 1986. MR 868281 (88i:82001)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 41A65, 47B06, 68Q17

Retrieve articles in all journals with MSC (2010): 41A65, 47B06, 68Q17


Additional Information

G. W. Wasilkowski
Affiliation: Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506
Email: greg@cs.uky.edu

DOI: https://doi.org/10.1090/S0025-5718-2013-02759-7
Received by editor(s): March 1, 2012
Received by editor(s) in revised form: September 10, 2012, and October 17, 2012
Published electronically: August 1, 2013
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society