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?)


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