The power of standard information for multivariate approximation in the randomized setting
Authors:
G. W. Wasilkowski and H. Wozniakowski
Journal:
Math. Comp. 76 (2007), 965988
MSC (2000):
Primary 41A63, 65C05, 65D15, 65Y20
Published electronically:
December 13, 2006
MathSciNet review:
2291845
Fulltext 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 norm. We consider functions with an arbitrarily large number of variables, , 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 th minimal errors, i.e., of the minimal errors among all algorithms using 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 is polynomial in (strong tractability), and polynomial in and (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 , 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.
 1.
N.
Aronszajn, Theory of reproducing
kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 0051437
(14,479c), http://dx.doi.org/10.1090/S00029947195000514377
 2.
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
(22 #6077)
 3.
J. Dick, I. H. Sloan, X. Wang and H. Wozniakowski, Good lattice rules in weighted Korobov spaces with general weights, to appear in Numer. Math.
 4.
B. L. Granovskii and S. M. Ermakov, The Monte Carlo method, J. Soviet Math. 7 (1977), 161192.
 5.
M. Griebel and H. Wozniakowski, On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation, to appear in Math. Computation.
 6.
S.
Heinrich, Lower bounds for the complexity of Monte Carlo function
approximation, J. Complexity 8 (1992), no. 3,
277–300. MR 1187419
(93h:65007), http://dx.doi.org/10.1016/0885064X(92)900279
 7.
S.
Heinrich, Monte Carlo complexity of global solution of integral
equations, J. Complexity 14 (1998), no. 2,
151–175. MR 1629093
(99g:65135), http://dx.doi.org/10.1006/jcom.1998.0471
 8.
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), http://dx.doi.org/10.1023/A:1018948631251
 9.
Frances
Y. Kuo, Ian
H. Sloan, and Henryk
Woźniakowski, Lattice rules for multivariate approximation
in the worst case setting, Monte Carlo and quasiMonte Carlo methods
2004, Springer, Berlin, 2006, pp. 289–330. MR 2208715
(2006j:41044), http://dx.doi.org/10.1007/3540311866_18
 10.
F. Kuo, I. H. Sloan and H. Wozniakowski, Lattice rules for multivariate approximation in the average case setting, in progress.
 11.
Peter
Mathé, Random approximation of Sobolev embeddings, J.
Complexity 7 (1991), no. 3, 261–281. MR 1128021
(93d:65008), http://dx.doi.org/10.1016/0885064X(91)90036W
 12.
A.
S. Nemirovsky and D.
B. Yudin, Problem complexity and method efficiency in
optimization, A WileyInterscience Publication, John Wiley & Sons,
Inc., New York, 1983. Translated from the Russian and with a preface by E.
R. Dawson; WileyInterscience Series in Discrete Mathematics. MR 702836
(84g:90079)
 13.
Erich
Novak, Deterministic and stochastic error bounds in numerical
analysis, Lecture Notes in Mathematics, vol. 1349,
SpringerVerlag, Berlin, 1988. MR 971255
(90a:65004)
 14.
Erich
Novak, Stochastic properties of quadrature formulas, Numer.
Math. 53 (1988), no. 5, 609–620. MR 954773
(89i:65026), http://dx.doi.org/10.1007/BF01397555
 15.
Erich
Novak, Optimal linear randomized methods for linear operators in
Hilbert spaces, J. Complexity 8 (1992), no. 1,
22–36. MR
1153612 (93f:65048), http://dx.doi.org/10.1016/0885064X(92)900327
 16.
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
(2005h:81097), http://dx.doi.org/10.1007/s1020800200746
 17.
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), http://dx.doi.org/10.1016/0885064X(90)900093
 18.
H. Pfeiffer, Monte Carlo methods with few random bits, Ph.D. Thesis, University of Jena, 2005.
 19.
Leszek
Plaskota, Noisy information and computational complexity,
Cambridge University Press, Cambridge, 1996. MR 1446005
(99b:65189)
 20.
Klaus
Ritter, Averagecase analysis of numerical problems, Lecture
Notes in Mathematics, vol. 1733, SpringerVerlag, Berlin, 2000. MR 1763973
(2001i:65001)
 21.
J.
F. Traub, G.
W. Wasilkowski, and H.
Woźniakowski, Informationbased 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)
 22.
J.
F. Traub and A.
G. Werschulz, Complexity and information, Lezioni Lincee.
[Lincei Lectures], Cambridge University Press, Cambridge, 1998. MR 1692462
(2000m:65170)
 23.
Joe
Fred Traub and H.
Woźniakowsi, A general theory of optimal algorithms,
Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New
YorkLondon, 1980. ACM Monograph Series. MR 584446
(84m:68041)
 24.
Grace
Wahba, Spline models for observational data, CBMSNSF Regional
Conference Series in Applied Mathematics, vol. 59, Society for
Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442
(91g:62028)
 25.
G.
W. Wasilkowski, Some nonlinear problems are as easy as the
approximation problem, Comput. Math. Appl. 10 (1984),
no. 45, 351–363 (1985). MR 777390
(86j:41023), http://dx.doi.org/10.1016/08981221(84)900634
 26.
G.
W. Wasilkowski, Randomization for continuous problems, J.
Complexity 5 (1989), no. 2, 195–218. MR 1006106
(91a:65006), http://dx.doi.org/10.1016/0885064X(89)900046
 27.
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
(2000h:65200), http://dx.doi.org/10.1006/jcom.1999.0512
 28.
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
(2002g:41052)
 29.
Arthur
G. Werschulz, The computational complexity of differential and
integral equations, Oxford Mathematical Monographs, The Clarendon
Press, Oxford University Press, New York, 1991. An informationbased
approach; Oxford Science Publications. MR 1144521
(93a:68061)
 30.
A. G. Werschulz and H. Wozniakowski, Tractability of quasilinear problems I: general results, II: secondorder elliptic problems, submitted for publication, 2005.
 31.
H.
Woźniakowski, Tractability and strong tractability of linear
multivariate problems, J. Complexity 10 (1994),
no. 1, 96–128. MR 1263379
(95d:65117), http://dx.doi.org/10.1006/jcom.1994.1004
 1.
 N. Aronszajn, Theory of reproducing kernels, Trans. AMS 68 (1950), 337404. MR 0051437 (14:479c)
 2.
 N. S. Bakhvalov, On approximate calculation of integrals, Vestnik MGV, Ser. Mat. Mekh. Astron. Fiz. Him. 4 (1959), 318. MR 0115275 (22:6077)
 3.
 J. Dick, I. H. Sloan, X. Wang and H. Wozniakowski, Good lattice rules in weighted Korobov spaces with general weights, to appear in Numer. Math.
 4.
 B. L. Granovskii and S. M. Ermakov, The Monte Carlo method, J. Soviet Math. 7 (1977), 161192.
 5.
 M. Griebel and H. Wozniakowski, On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation, to appear in Math. Computation.
 6.
 S. Heinrich, Lower bounds for the complexity of Monte Carlo function approximation, J. Complexity 8 (1992), 277300. MR 1187419 (93h:65007)
 7.
 S. Heinrich, Monte Carlo complexity of global solution of integral equations, J. Complexity 14 (1998), 151175. MR 1629093 (99g:65135)
 8.
 F. J. Hickernell and H. Wozniakowski, Integration and approximation in arbitrary dimensions, Advances in Comput. Math. 12 (2000), 2558. MR 1758946 (2001d:65017)
 9.
 F. Kuo, I. H. Sloan and H. Wozniakowski, Lattice rules for multivariate approximation in the worst case setting, in Monte Carlo and QuasiMonte Carlo Methods 2004, eds. H. Niederreiter and D. Talay, SpringerVerlag, Berlin, pp. 289330, 2006. MR 2208715 (2006j:41044)
 10.
 F. Kuo, I. H. Sloan and H. Wozniakowski, Lattice rules for multivariate approximation in the average case setting, in progress.
 11.
 P. Mathé, Random approximation of Sobolev embeddings, J. Complexity 7 (1991), 261281. MR 1128021 (93d:65008)
 12.
 A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley, New York, 1983. MR 0702836 (84g:90079)
 13.
 E. Novak, Deterministic and Stochastic Error Bounds in Numerical Analysis, Lect. Notes in Math. 1349, SpringerVerlag, Berlin, 1988. MR 0971255 (90a:65004)
 14.
 E. Novak, Stochastic properties of quadrature formulas, Numer. Math. 53 (1988), 609620. MR 0954773 (89i:65026)
 15.
 E. Novak, Optimal linear randomized methods for linear operators in Hilbert spaces, J. Complexity 8 (1992), 2236. MR 1153612 (93f:65048)
 16.
 E. Novak, I. H. Sloan and H. Wozniakowski, Tractability of approximation for weighted Korobov spaces on classical and quantum computers, Found. Comput. Math. 4 (2004), 121156. MR 2049868 (2005h:81097)
 17.
 A. Papageorgiou and G. W. Wasilkowski, On the average complexity of multivariate problems, J. Complexity 6 (1990), 123. MR 1048027 (91b:94020)
 18.
 H. Pfeiffer, Monte Carlo methods with few random bits, Ph.D. Thesis, University of Jena, 2005.
 19.
 L. Plaskota, Noisy Information and Computational Complexity, Cambridge Univ. Press, Cambridge, 1996. MR 1446005 (99b:65189)
 20.
 K. Ritter, AverageCase Analysis of Numerical Problems, Lect. Notes in Math. 1733, SpringerVerlag, Berlin, 2000. MR 1763973 (2001i:65001)
 21.
 J. F. Traub, G. W. Wasilkowski, and H. Wozniakowski, InformationBased Complexity, Academic Press, New York, 1988. MR 0958691 (90f:68085)
 22.
 J. F. Traub and A. G. Werschulz, Complexity and Information, Cambridge Univ. Press, Cambridge, 1998. MR 1692462 (2000m:65170)
 23.
 J. F. Traub and H. Wozniakowski, A General Theory of Optimal Algorithms, Academic Press, New York, 1980. MR 0584446 (84m:68041)
 24.
 G. Wahba, Spline Models for Observational Data, CBMSNSF 59, Philadelphia, 1990. MR 1045442 (91g:62028)
 25.
 G. W. Wasilkowski, Some nonlinear problems are as easy as the approximation problem, Comput. Math. Appl. 10 (1984), 351363. MR 0777390 (86j:41023)
 26.
 G. W. Wasilkowski, Randomization for continuous problems, J. Complexity 5 (1989), 195218. MR 1006106 (91a:65006)
 27.
 G. W. Wasilkowski and H. Wozniakowski, Weighted tensorproduct algorithms for linear multivariate problems, J. of Complexity 15, (1999), 402447. MR 1716741 (2000h:65200)
 28.
 G. W. Wasilkowski and H. Wozniakowski, On the power of standard information for weighted approximation, Found. Comput. Math. 1 (2001), 417434. MR 1857723 (2002g:41052)
 29.
 A. G. Werschulz, The Computational Complexity of Differential and Integral Equations, Oxford Univ. Press, Oxford, 1991. MR 1144521 (93a:68061)
 30.
 A. G. Werschulz and H. Wozniakowski, Tractability of quasilinear problems I: general results, II: secondorder elliptic problems, submitted for publication, 2005.
 31.
 H. Wozniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity, 10 (1994), 96128. MR 1263379 (95d:65117)
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 405060046
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:
http://dx.doi.org/10.1090/S0025571806019442
PII:
S 00255718(06)019442
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.
