Tractability of L₂-approximation and integration over weighted Korobov spaces of increasing smoothness in the worst case setting

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

This paper is devoted to the study of tractability of the L₂-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class Λ^all, including all continuous linear functionals, and from the class Λ^std, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and (σ, τ)-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.

Keywords

L₂-approximation / integration / tractability / Korobov space / increasing smoothness

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume I: Linear Information , EMS, Zurich, 2008. https://doi.org/10.4171/026

[2] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume II: Standard Information for Functionals , EMS, Zurich, 2010. https://doi.org/10.4171/084

[3] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume III: Standard Information for Operators , EMS, Zurich, 2012. https://doi.org/10.4171/116

[4] 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. https://doi.org/10.1007/s10208-002-0074-6

[5] G. W. Wasilkowski, H. Woźniakowski, Weighted tensor product algorithms for linear multivariate problems, J. Complexity, 15 (1999), 402-447. https://doi.org/10.1006/jcom.1999.0512

[6] G. W. Wasilkowski, H. Woźniakowski, On the power of standard information for weighted approximation, Found. Comput. Math., 1 (2001), 417-434. https://doi.org/10.1007/s102080010016

[7] H. Woźniakowski, Tractability of multivariate integration for weighted Korobov spaces: My 15 year partnership with Ian Sloan, in Monte Carlo and Quasi-Monte Carlo Methods 2008, (eds. Henryk Woźniakowski), Springer, Berlin, Heidelberg, (2009), 637-653.

[8] J. Dick, P. Kritzer, F. Pillichshammer, Lattice Rules: Numerical Integration, Approximation, and Discrepancy , Springer, 2022. https://doi.org/10.1007/978-3-031-09951-9

[9] R. Guo, H. Wang, Tractability of non-homogeneous tensor product problems in the worst case setting, preprint, arXiv:1901.05752. https://doi.org/10.48550/arXiv.1901.05752

[10] H. Yan, J. Chen, Tractability of approximation of functions defined over weighted Hilbert spaces, Axioms, 13 (2024). https://doi.org/10.3390/axioms13020108

[11] G. Leobacher, F. Pillichshammer, A. Ebert, Tractability of L₂-approximation and integration in weighted Hermite spaces of finite smoothness , J. Complexity, 78 (2023) 101768. https://doi.org/10.1016/j.jco.2023.101768

[12] A. Ebert, F. Pillichshammer, Tractability of approximation in the weighted Korobov space in the worst-case setting-a complete picture. J. Complexity, 67 (2021), 15. https://doi.org/10.1016/j.jco.2021.101571

[13] J. F. Traub, G. W. Wasilkowski, H. Woźniakowski, Information-Based Complexity , Academic Press, New York, 1988.

[14] P. Kritzer, H. Woźniakowski, Simple characterizations of exponential tractability for linear multivariate problems, J. Complexity, 51 (2019), 110-128. https://doi.org/10.1016/j.jco.2018.10.004

[15] A. Hinrichs, D. Krieg, E. Novak, J. Vybíral, Lower bounds for the error of quadrature formulas for Hilbert spaces, J. Complexity, 65 (2021), 101544. https://doi.org/10.1016/j.jco.2020.101544

[16] W. Lu, H. Wang, On the power of standard information for tractability for L₂-approximation in the randomized setting , Contemp. Math., 3 (2022), 1-29. https://doi.org/10.37256/cm.3120221229

[17] M. Dolbeault, D. Krieg, M. Ullrich, A sharp upper bound for sampling numbers in L₂ , Appl. Comput. Harmon. Anal., 63 (2023), 113-134. https://doi.org/10.1016/j.acha.2022.12.001