Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

The power of standard information for multivariate approximation in the randomized setting


Authors: G. W. Wasilkowski and H. Wozniakowski
Journal: Math. Comp. 76 (2007), 965-988
MSC (2000): Primary 41A63, 65C05, 65D15, 65Y20
DOI: https://doi.org/10.1090/S0025-5718-06-01944-2
Published electronically: December 13, 2006
MathSciNet review: 2291845
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted $ L_2$-norm. We consider functions with an arbitrarily large number of variables, $ d$, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points.

We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the $ n$th minimal errors, i.e., of the minimal errors among all algorithms using $ n$ function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting.

We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor $ \varepsilon$ is polynomial in  $ \varepsilon^{-1}$ (strong tractability), and polynomial in $ d$ and $ \varepsilon^{-1}$ (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check.

We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of $ d$, we prove that strong tractability is equivalent to tractability.

We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 41A63, 65C05, 65D15, 65Y20

Retrieve articles in all journals with MSC (2000): 41A63, 65C05, 65D15, 65Y20


Additional Information

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

H. Wozniakowski
Affiliation: Department of Computer Science, Columbia University, New York, NY 10027, USA, and Institute of Applied Mathematics, University of Warsaw, Warsaw, Poland
Email: henryk@cs.columbia.edu

DOI: https://doi.org/10.1090/S0025-5718-06-01944-2
Keywords: Weighted multivariate approximation, randomized algorithms, Monte Carlo methods, tractability
Received by editor(s): December 8, 2005
Published electronically: December 13, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.