The power of standard information for multivariate approximation in the randomized setting
HTML articles powered by AMS MathViewer
- by G. W. Wasilkowski and H. Woźniakowski PDF
- Math. Comp. 76 (2007), 965-988 Request permission
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
- N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 51437, DOI 10.1090/S0002-9947-1950-0051437-7
- N. S. Bahvalov, Approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. 1959 (1959), no. 4, 3–18 (Russian). MR 0115275
- J. Dick, I. H. Sloan, X. Wang and H. Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights, to appear in Numer. Math.
- B. L. Granovskii and S. M. Ermakov, The Monte Carlo method, J. Soviet Math. 7 (1977), 161-192.
- M. Griebel and H. Woźniakowski, On the optimal convergence rate of universal and non-universal algorithms for multivariate integration and approximation, to appear in Math. Computation.
- S. Heinrich, Lower bounds for the complexity of Monte Carlo function approximation, J. Complexity 8 (1992), no. 3, 277–300. MR 1187419, DOI 10.1016/0885-064X(92)90027-9
- S. Heinrich, Monte Carlo complexity of global solution of integral equations, J. Complexity 14 (1998), no. 2, 151–175. MR 1629093, DOI 10.1006/jcom.1998.0471
- 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
- Frances Y. Kuo, Ian H. Sloan, and Henryk Woźniakowski, Lattice rules for multivariate approximation in the worst case setting, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 289–330. MR 2208715, DOI 10.1007/3-540-31186-6_{1}8
- F. Kuo, I. H. Sloan and H. Woźniakowski, Lattice rules for multivariate approximation in the average case setting, in progress.
- Peter Mathé, Random approximation of Sobolev embeddings, J. Complexity 7 (1991), no. 3, 261–281. MR 1128021, DOI 10.1016/0885-064X(91)90036-W
- A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson. MR 702836
- 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
- Erich Novak, Stochastic properties of quadrature formulas, Numer. Math. 53 (1988), no. 5, 609–620. MR 954773, DOI 10.1007/BF01397555
- Erich Novak, Optimal linear randomized methods for linear operators in Hilbert spaces, J. Complexity 8 (1992), no. 1, 22–36. MR 1153612, DOI 10.1016/0885-064X(92)90032-7
- Erich Novak, Ian H. Sloan, and Henryk Woźniakowski, Tractability of approximation for weighted Korobov spaces on classical and quantum computers, Found. Comput. Math. 4 (2004), no. 2, 121–156. MR 2049868, DOI 10.1007/s10208-002-0074-6
- 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
- H. Pfeiffer, Monte Carlo methods with few random bits, Ph.D. Thesis, University of Jena, 2005.
- Leszek Plaskota, Noisy information and computational complexity, Cambridge University Press, Cambridge, 1996. MR 1446005, DOI 10.1017/CBO9780511600814
- Klaus Ritter, Average-case analysis of numerical problems, Lecture Notes in Mathematics, vol. 1733, Springer-Verlag, Berlin, 2000. MR 1763973, DOI 10.1007/BFb0103934
- 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
- J. F. Traub and A. G. Werschulz, Complexity and information, Lezioni Lincee. [Lincei Lectures], Cambridge University Press, Cambridge, 1998. MR 1692462, DOI 10.1080/16073606.1997.9631861
- Joe Fred Traub and H. Woźniakowsi, A general theory of optimal algorithms, ACM Monograph Series, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR 584446
- 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, Some nonlinear problems are as easy as the approximation problem, Comput. Math. Appl. 10 (1984), no. 4-5, 351–363 (1985). MR 777390, DOI 10.1016/0898-1221(84)90063-4
- 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 H. Woźniakowski, Weighted tensor product algorithms for linear multivariate problems, J. Complexity 15 (1999), no. 3, 402–447. Dagstuhl Seminar on Algorithms and Complexity for Continuous Problems (1998). MR 1716741, DOI 10.1006/jcom.1999.0512
- G. W. Wasilkowski and H. Woźniakowski, On the power of standard information for weighted approximation, Found. Comput. Math. 1 (2001), no. 4, 417–434. MR 1857723, DOI 10.1007/s102080010016
- Arthur G. Werschulz, The computational complexity of differential and integral equations, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1991. An information-based approach; Oxford Science Publications. MR 1144521
- A. G. Werschulz and H. Woźniakowski, Tractability of quasilinear problems I: general results, II: second-order elliptic problems, submitted for publication, 2005.
- H. Woźniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity 10 (1994), no. 1, 96–128. MR 1263379, DOI 10.1006/jcom.1994.1004
Additional Information
- G. W. Wasilkowski
- Affiliation: Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 40506-0046
- MR Author ID: 189251
- ORCID: 0000-0003-4727-7368
- Email: greg@cs.uky.edu
- H. Woźniakowski
- 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
- Received by editor(s): December 8, 2005
- Published electronically: December 13, 2006
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2291845