Kritzer, Peter; Laimer, Helene; Pillichshammer, Friedrich Tractability of \(\mathbb{L}_2\)-approximation in hybrid function spaces. (English) Zbl 1396.41014 Funct. Approximatio, Comment. Math. 58, No. 1, 89-104 (2018). Summary: We consider multivariate \(\mathbb{L}_2\)-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error \(e^{\mathbb{L}_2-\text{app},\Lambda}(N,d)\) of all algorithms that use \(N\) information evaluations from the class \(\Lambda\) in the \(d\)-dimensional case. The two classes \(\Lambda\) considered in this paper are the class \(\Lambda^{\text{all}}\) consisting of all linear functionals and the class \(\Lambda^{\text{std}}\) consisting only of function evaluations. The focus lies on the dependence of \(e^{\mathbb{L}_2-\text{app},\Lambda}(N,d)\) on the dimension \(d\). The main results are conditions for weak, polynomial, and strong polynomial tractability. Cited in 1 Document MSC: 41A25 Rate of convergence, degree of approximation 41A63 Multidimensional problems 65D15 Algorithms for approximation of functions 65Y20 Complexity and performance of numerical algorithms Keywords:multivariate approximation; Walsh space; Korobov space; hybrid function space × Cite Format Result Cite Review PDF Full Text: DOI arXiv Euclid References: [1] N. Aronszajn. Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950) 337-404. · Zbl 0037.20701 · doi:10.1090/S0002-9947-1950-0051437-7 [2] J. Baldeaux, J. Dick, P. Kritzer, On the approximation of smooth functions using generalized digital nets, J. Complexity 25 (2009) 544-567. · Zbl 1182.65024 · doi:10.1016/j.jco.2009.07.003 [3] J. Dick, P. Kritzer, F.Y. Kuo, Approximation of functions using digital nets, in: A. Keller, S. Heinrich, H. Niederreiter (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer, Berlin, 2008, pp. 275-297. · Zbl 1153.65314 [4] J. Dick, P. Kritzer, F. Pillichshammer, H. Woźniakowski, Approximation of analytic functions in Korobov spaces, J. Complexity 30 (2014) 2-28. · Zbl 1342.41021 · doi:10.1016/j.jco.2013.05.001 [5] J. Dick, F.Y. Kuo, F. Pillichshammer, I.H. Sloan, Construction algorithms for polynomial lattice rules for multivariate integration, Math. Comp. 74 (2005) 1895-1921. · Zbl 1079.65007 · doi:10.1090/S0025-5718-05-01742-4 [6] J. Dick, F.Y. Kuo, I.H. Sloan, High-dimensional integration: the quasi-Monte Carlo way, Acta Numer. 22 (2013) 133-288. · Zbl 1296.65004 · doi:10.1017/S0962492913000044 [7] J. Dick, F. Pillichshammer, Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, J. Complexity 21 (2005) 149-195. · Zbl 1085.41021 · doi:10.1016/j.jco.2004.07.003 [8] P. Hellekalek, Hybrid function systems in the theory of uniform distribution of sequences, in: L. Plaskota, H. Woźniakowski (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2010, Springer, Berlin, 2012, pp. 435-449. · Zbl 1346.11043 [9] R. Hofer, P. Kritzer, G. Larcher, F. Pillichshammer, Distribution properties of generalized van der Corput-Halton sequences and their subsequences, Int. J. Number Theory 5 (2009) 719-746. · Zbl 1188.11038 · doi:10.1142/S1793042109002328 [10] A. Keller, Quasi-Monte Carlo image synthesis in a nutshell, in: J. Dick, F.Y. Kuo, G.W. Peters, I.H. Sloan (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2012, Springer, Berlin, 2013, pp. 213-249. · Zbl 1302.65010 [11] P. Kritzer, F. Pillichshammer, Tractability of multivariate integration in hybrid function spaces, in: R. Cools, D. Nuyens (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2014, Springer, Berlin, 2016, pp. 437-454. · Zbl 1356.65009 [12] F.Y. Kuo, I.H. Sloan, H. Woźniakowski, Lattice rules for multivariate approximation in the worst case setting, in: H. Niederreiter, D. Talay (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2004, Springer, Berlin, 2006, pp. 289-330. · Zbl 1097.65133 [13] G. Larcher, Discrepancy estimates for sequences: new results and open problems, in: P. Kritzer, H. Niederreiter, F. Pillichshammer, A. Winterhof (Eds.), Uniform Distribution and Quasi-Monte Carlo Methods, Radon Series in Computational and Applied Mathematics, DeGruyter, Berlin, 2014, pp. 171-189. [14] G. Leobacher, F. Pillichshammer, Introduction to Quasi-Monte Carlo Integration and Applications, Compact Textbooks in Mathematics, Birkhäuser, Cham, 2014. · Zbl 1309.65006 [15] E. Novak, I.H. Sloan, H. Woźniakowski, Tractability of approximation for weighted Korobov spaces on classical and quantum computers, Found. Comput. Math. 4 (2004) 121-156. · Zbl 1072.81014 · doi:10.1007/s10208-002-0074-6 [16] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume I: Linear Information, EMS, Zurich, 2008. · Zbl 1156.65001 [17] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume II: Standard Information for Functionals, EMS, Zurich, 2010. · Zbl 1241.65025 [18] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume III: Standard Information for Operators, EMS, Zurich, 2012. · Zbl 1359.65003 [19] I.H. Sloan, H. Woźniakowski, Tractability of multivariate integration for weighted Korobov classes, J. Complexity 17 (2001) 697-721. · Zbl 0998.65004 · doi:10.1006/jcom.2001.0599 [20] J.F. Traub, G.W. Wasilkowski, H. Woźniakowski, Information-Based Complexity, Academic Press, New York, 1988. · Zbl 0654.94004 [21] G.W. Wasilkowski, H. Woźniakowski, Weighted tensor product algorithms for linear multivariate problems, J. Complexity 15 (1999) 402-447. · Zbl 0939.65079 · doi:10.1006/jcom.1999.0512 [22] X. Zeng, P. Kritzer, F.J. Hickernell, Spline methods using integration lattices and digital nets, Constr. Approx. 30 (2009) 529-555. · Zbl 1184.41009 · doi:10.1007/s00365-009-9072-0 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.