{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T08:22:20Z","timestamp":1772180540222,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,7]],"date-time":"2023-03-07T00:00:00Z","timestamp":1678147200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,7]],"date-time":"2023-03-07T00:00:00Z","timestamp":1678147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["F5506"],"award-info":[{"award-number":["F5506"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Adv Comput Math"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the complexity of high-dimensional approximation in the <jats:italic>L<\/jats:italic><jats:sub>2<\/jats:sub>-norm when different classes of information are available; we compare the power of function evaluations with the power of arbitrary continuous linear measurements. Here, we discuss the situation when the number of linear measurements required to achieve an error <jats:italic>\u03b5<\/jats:italic> \u2208 (0,1) in dimension <jats:inline-formula><jats:alternatives><jats:tex-math>$d\\in \\mathbb {N}$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>d<\/mml:mi>\n                  <mml:mo>\u2208<\/mml:mo>\n                  <mml:mi>\u2115<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> depends only poly-logarithmically on <jats:italic>\u03b5<\/jats:italic><jats:sup>\u2212\u20091<\/jats:sup>. This corresponds to an exponential order of convergence of the approximation error, which often happens in applications. However, it does not mean that the high-dimensional approximation problem is easy, the main difficulty usually lies within the dependence on the dimension <jats:italic>d<\/jats:italic>. We determine to which extent the required amount of information changes if we allow only function evaluation instead of arbitrary linear information. It turns out that in this case we only lose very little, and we can even restrict to linear algorithms. In particular, several notions of tractability hold simultaneously for both types of available information.<\/jats:p>","DOI":"10.1007\/s10444-023-10021-7","type":"journal-article","created":{"date-parts":[[2023,3,7]],"date-time":"2023-03-07T09:02:56Z","timestamp":1678179776000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Exponential tractability of L2-approximation with function values"],"prefix":"10.1007","volume":"49","author":[{"given":"David","family":"Krieg","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7352-9253","authenticated-orcid":false,"given":"Pawe\u0142","family":"Siedlecki","sequence":"additional","affiliation":[]},{"given":"Mario","family":"Ullrich","sequence":"additional","affiliation":[]},{"given":"Henryk","family":"Wo\u017aniakowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,3,7]]},"reference":[{"issue":"1","key":"10021_CR1","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1137\/130908221","volume":"52","author":"B Adcock","year":"2014","unstructured":"Adcock, B., Hansen, A.C., Shadrin, A.: A stability barrier for reconstructions from Fourier samples. SIAM J. Numer. Anal. 52(1), 125\u2013139 (2014)","journal-title":"SIAM J. Numer. Anal."},{"key":"10021_CR2","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/s10208-013-9158-8","volume":"14","author":"B Adcock","year":"2014","unstructured":"Adcock, B., Huybrechs, D., Martin-Vaquero, J.: On the numerical stability of Fourier extensions. Found. Comput. Math. 14, 635\u2013687 (2014)","journal-title":"Found. Comput. Math."},{"issue":"3","key":"10021_CR3","doi-asserted-by":"publisher","first-page":"1360","DOI":"10.1093\/imanum\/dry024","volume":"39","author":"B Adcock","year":"2018","unstructured":"Adcock, B., Platte, R.B., Shadrin, A.: Optimal sampling rates for approximating analytic functions from pointwise samples. IMA J. Numer. Anal. 39(3), 1360\u20131390 (2018)","journal-title":"IMA J. Numer. Anal."},{"issue":"3","key":"10021_CR4","doi-asserted-by":"publisher","first-page":"1457","DOI":"10.1137\/100795772","volume":"43","author":"P Binev","year":"2011","unstructured":"Binev, P., Cohen, A., Dahmen, W., DeVore, R., Petrova, G., Wojtaszczyk, P.: Convergence rates for greedy algorithms in reduced basis methods. SIAM J. Math. Anal. 43(3), 1457\u20131472 (2011)","journal-title":"SIAM J. Math. Anal."},{"issue":"3","key":"10021_CR5","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1051\/m2an\/2011056","volume":"46","author":"A Buffa","year":"2012","unstructured":"Buffa, A., Maday, Y., Patera, A.T., Prud\u2019homme C., Turinici, G.: A priori convergence of the greedy algorithm for the parametrized reduced basis method. ESAIM:, Mathematical modelling and numerical analysis \u2013 mod\u00e9lisation math\u00e9matique et analyse num\u00e9rique 46(3), 595\u2013603 (2012)","journal-title":"ESAIM:, Mathematical modelling and numerical analysis \u2013 mod\u00e9lisation math\u00e9matique et analyse num\u00e9rique"},{"key":"10021_CR6","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1016\/j.jco.2004.05.003","volume":"20","author":"J Creutzig","year":"2004","unstructured":"Creutzig, J., Wojtaszczyk, P.: Linear vs. nonlinear algorithms for linear problems. J. Complex. 20, 807\u2013820 (2004)","journal-title":"J. Complex."},{"key":"10021_CR7","doi-asserted-by":"publisher","first-page":"101537","DOI":"10.1016\/j.jco.2020.101537","volume":"64","author":"JJA Deimer","year":"2021","unstructured":"Deimer, J.J.A., Sergio, A.T.: Estimates for n-widths of sets of smooth functions on complex spheres. J. Complex. 64, 101537 (2021)","journal-title":"J. Complex."},{"issue":"2","key":"10021_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jco.2013.05.001","volume":"30","author":"J Dick","year":"2014","unstructured":"Dick, J., Kritzer, P., Pillichshammer, F., Wo\u017aniakowski, H.: Approximation of analytic functions in Korobov spaces. J. Complex. 30(2), 2\u201328 (2014)","journal-title":"J. Complex."},{"key":"10021_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.acha.2022.12.001","volume":"63","author":"M Dolbeault","year":"2023","unstructured":"Dolbeault, M., Krieg, D., Ullrich, M.: A sharp upper bound for sampling numbers in l2. Appl. Comput. Harmon. Anal. 63, 113\u2013134 (2023)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"10021_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92240-9","volume-title":"Hyperbolic Cross Approximation. Advanced Courses in Mathematics - CRM Barcelona","author":"D D\u0169ng","year":"2018","unstructured":"D\u0169ng, D., Temlyakov, V.N., Ullrich, T.: Hyperbolic Cross Approximation. Advanced Courses in Mathematics - CRM Barcelona. Springer, Heidelberg (2018)"},{"key":"10021_CR11","doi-asserted-by":"publisher","first-page":"101571","DOI":"10.1016\/j.jco.2021.101571","volume":"67","author":"A Ebert","year":"2021","unstructured":"Ebert, A., Pillichshammer, F.: Tractability of approximation in the weighted Korobov space in the worst-case setting \u2013 a complete picture. J. Complex. 67, 101571 (2021)","journal-title":"J. Complex."},{"issue":"1","key":"10021_CR12","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1137\/10080138X","volume":"50","author":"GE Fasshauer","year":"2012","unstructured":"Fasshauer, G.E., Hickernell, F.J., Wo\u017aniakowski, H.: On dimension-independent rates of convergence for function approximation with Gaussian kernels. SIAM J. Numer. Anal. 50(1), 247\u2013271 (2012)","journal-title":"SIAM J. Numer. Anal."},{"key":"10021_CR13","unstructured":"Gabcke, W.: Neue Herleitung Und Explizite Restabsch\u00e4tzung Der Riemann-Siegel-Formel PhD thesis. University of G\u00f6ttingen (1979)"},{"key":"10021_CR14","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.jat.2016.02.006","volume":"207","author":"M Griebel","year":"2016","unstructured":"Griebel, M., Oettershagen, J.: On tensor product approximation of analytic functions. J. Approx. Theory 207, 348\u2013379 (2016)","journal-title":"J. Approx. Theory"},{"issue":"3","key":"10021_CR15","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1051\/m2an\/2012045","volume":"47","author":"B Haasdonk","year":"2013","unstructured":"Haasdonk, B.: Convergence rates of the pod\u2013greedy method. ESAIM:, Mathematical Modelling and Numerical Analysis - Mod\u00e9lisation Math\u00e9matique et Analyse Num\u00e9rique 47(3), 859\u2013873 (2013)","journal-title":"ESAIM:, Mathematical Modelling and Numerical Analysis - Mod\u00e9lisation Math\u00e9matique et Analyse Num\u00e9rique"},{"issue":"4","key":"10021_CR16","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1016\/j.jco.2007.03.007","volume":"23","author":"W Hackbusch","year":"2007","unstructured":"Hackbusch, W., Khoromskij, B.N.: Tensor-product approximation to operators and functions in high dimensions. J. Complex. 23(4), 697\u2013714 (2007). Festschrift for the 60th Birthday of Henryk Wo\u017aniakowski","journal-title":"J. Complex."},{"issue":"1","key":"10021_CR17","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.jfa.2010.02.001","volume":"259","author":"T Hangelbroek","year":"2010","unstructured":"Hangelbroek, T., Ron, A.: Nonlinear approximation using Gaussian kernels. J. Funct. Anal. 259(1), 203\u2013219 (2010)","journal-title":"J. Funct. Anal."},{"issue":"12","key":"10021_CR18","doi-asserted-by":"publisher","first-page":"8691","DOI":"10.1090\/tran\/8502","volume":"374","author":"A Hinrichs","year":"2021","unstructured":"Hinrichs, A., Krieg, D., Novak, E., Prochno, J., Ullrich, M.: Random sections of ellipsoids and the power of random information. Trans. Am. Math. Soc. 374(12), 8691\u20138713 (2021)","journal-title":"Trans. Am. Math. Soc."},{"key":"10021_CR19","doi-asserted-by":"publisher","first-page":"101544","DOI":"10.1016\/j.jco.2020.101544","volume":"65","author":"A Hinrichs","year":"2021","unstructured":"Hinrichs, A., Krieg, D., Novak, E., Vyb\u00edral, J.: Lower bounds for the error of quadrature formulas for Hilbert spaces. J. Complex. 65, 101544 (2021)","journal-title":"J. Complex."},{"key":"10021_CR20","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.jat.2014.03.012","volume":"183","author":"A Hinrichs","year":"2014","unstructured":"Hinrichs, A., Novak, E., Ullrich, M.: On weak tractability of the clenshaw\u2013Curtis Smolyak algorithm. J. Approx. Theory 183, 31\u201344 (2014)","journal-title":"J. Approx. Theory"},{"issue":"290","key":"10021_CR21","doi-asserted-by":"publisher","first-page":"2853","DOI":"10.1090\/S0025-5718-2014-02855-X","volume":"83","author":"A Hinrichs","year":"2014","unstructured":"Hinrichs, A., Novak, E., Ullrich, M., Wo\u017aniakowski, H.: The curse of dimensionality for numerical integration of smooth functions. Math. Comput. 83(290), 2853\u20132863 (2014)","journal-title":"Math. Comput."},{"key":"10021_CR22","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jco.2016.09.001","volume":"38","author":"A Hinrichs","year":"2017","unstructured":"Hinrichs, A., Novak, E., Ullrich, M., Wo\u017aniakowski, H.: Product rules are optimal for numerical integration in classical smoothness spaces. J. Complex. 38, 39\u201349 (2017)","journal-title":"J. Complex."},{"key":"10021_CR23","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jco.2018.08.003","volume":"50","author":"A Hinrichs","year":"2019","unstructured":"Hinrichs, A., Prochno, J., Ullrich, M.: The curse of dimensionality for numerical integration on general domains. J. Complex. 50, 25\u201342 (2019)","journal-title":"J. Complex."},{"key":"10021_CR24","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.jat.2016.02.008","volume":"207","author":"C Irrgeher","year":"2016","unstructured":"Irrgeher, C., Kritzer, P., Pillichshammer, F., Wo\u017aniakowski, H.: Approximation in Hermite spaces of smooth functions. J. Approx. Theory 207, 98\u2013126 (2016)","journal-title":"J. Approx. Theory"},{"key":"10021_CR25","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.jat.2016.02.020","volume":"207","author":"C Irrgeher","year":"2016","unstructured":"Irrgeher, C., Kritzer, P., Pillichshammer, F., Wo\u017aniakowski, H.: Tractability of multivariate approximation defined over Hilbert spaces with exponential weights. J. Approx. Theory 207, 301\u2013338 (2016)","journal-title":"J. Approx. Theory"},{"key":"10021_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10444-020-09767-1","volume":"46","author":"T Karvonen","year":"2020","unstructured":"Karvonen, T., S\u00e4rkk\u00e4, S.: Worst-case optimal approximation with increasingly flat Gaussian kernels. Adv. Comput. Math. 46, 1\u201317 (2020)","journal-title":"Adv. Comput. Math."},{"key":"10021_CR27","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.jco.2018.10.002","volume":"50","author":"D Krieg","year":"2019","unstructured":"Krieg, D.: Uniform recovery of high-dimensional cr-functions. J. Complex. 50, 116\u2013126 (2019)","journal-title":"J. Complex."},{"issue":"4","key":"10021_CR28","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1007\/s10208-020-09481-w","volume":"21","author":"D Krieg","year":"2021","unstructured":"Krieg, D., Ullrich, M.: Function values are enough for l2-approximation. Found. Comput. Math. 21(4), 1141\u20131151 (2021)","journal-title":"Found. Comput. Math."},{"key":"10021_CR29","doi-asserted-by":"publisher","first-page":"101569","DOI":"10.1016\/j.jco.2021.101569","volume":"66","author":"D Krieg","year":"2021","unstructured":"Krieg, D., Ullrich, M.: Function values are enough for l2-approximation: Part II. J. Complex. 66, 101569 (2021)","journal-title":"J. Complex."},{"key":"10021_CR30","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.jco.2018.10.004","volume":"51","author":"P Kritzer","year":"2019","unstructured":"Kritzer, P., Wo\u017aniakowski, H.: Simple characterizations of exponential tractability for linear multivariate problems. J. Complex. 51, 110\u2013128 (2019)","journal-title":"J. Complex."},{"issue":"1","key":"10021_CR31","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0885-064X(90)90011-2","volume":"6","author":"P Math\u00e9","year":"1990","unstructured":"Math\u00e9, P.: S-numbers in information-based complexity. J. Complex. 6(1), 41\u201366 (1990)","journal-title":"J. Complex."},{"key":"10021_CR32","unstructured":"Nagel, N., Sch\u00e4fer, M., Ullrich, T.: A new upper bound for sampling numbers. arXiv:2010.00327 (2020)"},{"key":"10021_CR33","doi-asserted-by":"crossref","unstructured":"Novak, E., Wo\u017aniakowski, H: Tractability of Multivariate Problems. Vol 1: Linear information, volume 6 of EMS tracts in mathematics. European Mathematical Society (EMS), Z\u00fcrich (2008)","DOI":"10.4171\/026"},{"key":"10021_CR34","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1016\/j.jco.2008.11.002","volume":"25","author":"E Novak","year":"2009","unstructured":"Novak, E., Wo\u017aniakowski, H.: Approximation of infinitely differentiable multivariate functions is intractable. J. Complex. 25, 398\u2013404 (2009)","journal-title":"J. Complex."},{"key":"10021_CR35","doi-asserted-by":"crossref","unstructured":"Novak, E., Wo\u017aniakowski, H.: Tractability of multivariate problems volume II : Standard information for functionals, volume 12 of EMS tracts in mathematics. European Mathematical Society, (EMS), Z\u00fcrich (2010)","DOI":"10.4171\/084"},{"key":"10021_CR36","doi-asserted-by":"crossref","unstructured":"Novak, E., Wo\u017aniakowski, H.: Tractability of multivariate problems volume III : Standard information for operators, volume 18 of EMS tracts in mathematics. European Mathematical Society, (EMS), Z\u00fcrich (2012)","DOI":"10.4171\/116"},{"key":"10021_CR37","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.jat.2016.02.017","volume":"207","author":"E Novak","year":"2016","unstructured":"Novak, E., Wo\u017aniakowski, H.: Tractability of multivariate problems for standard and linear information in the worst case setting: part i. J. Approx. Theory 207, 177\u2013192 (2016)","journal-title":"J. Approx. Theory"},{"key":"10021_CR38","unstructured":"Pietsch, A.: Operator ideals. Deutscher Verlag, Wiss. Berlin (1978)"},{"issue":"2","key":"10021_CR39","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1137\/090774707","volume":"53","author":"RB Platte","year":"2011","unstructured":"Platte, R.B., Trefethen, L.N., Kuijlaars, A.B.J.: Impossibility of fast stable approximation of analytic functions from equispaced samples. SIAM Rev. 53(2), 308\u2013318 (2011)","journal-title":"SIAM Rev."},{"key":"10021_CR40","doi-asserted-by":"publisher","first-page":"107140","DOI":"10.1016\/j.aim.2020.107140","volume":"368","author":"J Vyb\u00edral","year":"2020","unstructured":"Vyb\u00edral, J.: A variant of Schur\u2019s product theorem and its applications. Adv. Math. 368, 107140 (2020)","journal-title":"Adv. Math."},{"key":"10021_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jco.2017.11.001","volume":"45","author":"I Sloan","year":"2018","unstructured":"Sloan, I., Wo\u017aniakowski, H.: Multivariate approximation for analytic functions with Gaussian kernels. J. Complex. 45, 1\u201321 (2018)","journal-title":"J. Complex."},{"key":"10021_CR42","unstructured":"Temlyakov, V.N.: Approximation of periodic functions. Computational Mathematics and Analysis Series, Nova Science Publishers, Inc, Commack, NY (1993)"},{"key":"10021_CR43","unstructured":"Temlyakov, V.N.: Multivariate Approximation, volume 32 of Cambridge Monographs on Applied and Computational Mathematics Cambridge University Press (2018)"},{"key":"10021_CR44","doi-asserted-by":"crossref","unstructured":"Ullrich, M.: On the worst-case error of least squares algorithms for l2-approximation with high probability. Journal of Complexity, p. 60 (2020)","DOI":"10.1016\/j.jco.2020.101484"},{"key":"10021_CR45","volume-title":"Scattered data approximation, vol. 17 of Cambridge monographs on applied and computational mathematics","author":"H Wendland","year":"2005","unstructured":"Wendland, H.: Scattered data approximation, vol. 17 of Cambridge monographs on applied and computational mathematics. Cambridge University Press, Cambridge (2005)"},{"key":"10021_CR46","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.jat.2014.10.016","volume":"192","author":"G Xu","year":"2015","unstructured":"Xu, G.: On weak tractability of the Smolyak algorithm for approximation problems. J. Approx. Theory 192, 347\u2013361 (2015)","journal-title":"J. Approx. Theory"},{"key":"10021_CR47","doi-asserted-by":"crossref","unstructured":"Zhang, J.: A note on EC-tractability of multivariate approximation in weighted Korobov spaces for the standard information class. Journal of Complexity, p. 67 (2021)","DOI":"10.1016\/j.jco.2021.101573"}],"container-title":["Advances in Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10444-023-10021-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10444-023-10021-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10444-023-10021-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T16:19:03Z","timestamp":1682007543000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10444-023-10021-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,7]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10021"],"URL":"https:\/\/doi.org\/10.1007\/s10444-023-10021-7","relation":{},"ISSN":["1019-7168","1572-9044"],"issn-type":[{"value":"1019-7168","type":"print"},{"value":"1572-9044","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,7]]},"assertion":[{"value":"31 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of interest"}}],"article-number":"18"}}