This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm 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 $ (\sigma, \tau) $-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.
Citation: Weiran Ding, Jiansong Li, Yumeng Jia, Wanru Yang. Tractability of $ L_2 $-approximation and integration over weighted Korobov spaces of increasing smoothness in the worst case setting[J]. Electronic Research Archive, 2025, 33(2): 1160-1184. doi: 10.3934/era.2025052
This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm 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 $ (\sigma, \tau) $-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.
| [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 doi: 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 doi: 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 doi: 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 doi: 10.3390/axioms13020108
|
| [11] |
G. Leobacher, F. Pillichshammer, A. Ebert, Tractability of $L_2$-approximation and integration in weighted Hermite spaces of finite smoothness, J. Complexity, 78 (2023) 101768. https://doi.org/10.1016/j.jco.2023.101768 doi: 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 doi: 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 doi: 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 doi: 10.1016/j.jco.2020.101544
|
| [16] |
W. Lu, H. Wang, On the power of standard information for tractability for $L_2$-approximation in the randomized setting, Contemp. Math., 3 (2022), 1–29. https://doi.org/10.37256/cm.3120221229 doi: 10.37256/cm.3120221229
|
| [17] |
M. Dolbeault, D. Krieg, M. Ullrich, A sharp upper bound for sampling numbers in $L_2$, Appl. Comput. Harmon. Anal., 63 (2023), 113–134. https://doi.org/10.1016/j.acha.2022.12.001 doi: 10.1016/j.acha.2022.12.001
|
Weiran Ding, Jiansong Li, Yumeng Jia, Wanru Yang. Tractability of $ L_2 $-approximation and integration over weighted Korobov spaces of increasing smoothness in the worst case setting[J]. Electronic Research Archive, 2025, 33(2): 1160-1184. doi: 10.3934/era.2025052
DownLoad: