{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:46:43Z","timestamp":1778496403903,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Johannes Kepler University Linz"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2021,8]]},"abstract":"Abstract<\/jats:title>We study the$$L_2$$<\/jats:tex-math>L<\/mml:mi>2<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation of functions from a Hilbert space and compare the sampling numbers with the approximation numbers. The sampling number$$e_n$$<\/jats:tex-math>e<\/mml:mi>n<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is the minimal worst-case error that can be achieved withn<\/jats:italic>function values, whereas the approximation number$$a_n$$<\/jats:tex-math>a<\/mml:mi>n<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is the minimal worst-case error that can be achieved withn<\/jats:italic>pieces of arbitrary linear information (like derivatives or Fourier coefficients). We show that$$\\begin{aligned} e_n \\,\\lesssim \\, \\sqrt{\\frac{1}{k_n} \\sum _{j\\ge k_n} a_j^2}, \\end{aligned}$$<\/jats:tex-math>e<\/mml:mi>n<\/mml:mi><\/mml:msub>\u2272<\/mml:mo>1<\/mml:mn>k<\/mml:mi>n<\/mml:mi><\/mml:msub><\/mml:mfrac>\u2211<\/mml:mo>j<\/mml:mi>\u2265<\/mml:mo>k<\/mml:mi>n<\/mml:mi><\/mml:msub><\/mml:mrow><\/mml:munder>a<\/mml:mi>j<\/mml:mi>2<\/mml:mn><\/mml:msubsup><\/mml:mrow><\/mml:msqrt>,<\/mml:mo><\/mml:mrow><\/mml:mtd><\/mml:mtr><\/mml:mtable><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:disp-formula>where$$k_n \\asymp n\/\\log (n)$$<\/jats:tex-math>k<\/mml:mi>n<\/mml:mi><\/mml:msub>\u224d<\/mml:mo>n<\/mml:mi>\/<\/mml:mo>log<\/mml:mo>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This proves that the sampling numbers decay with the same polynomial rate as the approximation numbers and therefore that function values are basically as powerful as arbitrary linear information if the approximation numbers are square-summable. Our result applies, in particular, to Sobolev spaces$$H^s_\\mathrm{mix}(\\mathbb {T}^d)$$<\/jats:tex-math>H<\/mml:mi>mix<\/mml:mi>s<\/mml:mi><\/mml:msubsup>(<\/mml:mo>T<\/mml:mi><\/mml:mrow>d<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>with dominating mixed smoothness$$s>1\/2$$<\/jats:tex-math>s<\/mml:mi>><\/mml:mo>1<\/mml:mn>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and dimension$$d\\in \\mathbb {N}$$<\/jats:tex-math>d<\/mml:mi>\u2208<\/mml:mo>N<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and we obtain$$\\begin{aligned} e_n \\,\\lesssim \\, n^{-s} \\log ^{sd}(n). \\end{aligned}$$<\/jats:tex-math>e<\/mml:mi>n<\/mml:mi><\/mml:msub>\u2272<\/mml:mo>n<\/mml:mi>-<\/mml:mo>s<\/mml:mi><\/mml:mrow><\/mml:msup>log<\/mml:mo>sd<\/mml:mi><\/mml:mrow><\/mml:msup>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow>.<\/mml:mo><\/mml:mrow><\/mml:mtd><\/mml:mtr><\/mml:mtable><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:disp-formula>For$$d>2s+1$$<\/jats:tex-math>d<\/mml:mi>><\/mml:mo>2<\/mml:mn>s<\/mml:mi>+<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, this improves upon all previous bounds and disproves the prevalent conjecture that Smolyak\u2019s (sparse grid) algorithm is optimal.<\/jats:p>","DOI":"10.1007\/s10208-020-09481-w","type":"journal-article","created":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T19:45:12Z","timestamp":1607370312000},"page":"1141-1151","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":60,"title":["Function Values Are Enough for $$L_2$$-Approximation"],"prefix":"10.1007","volume":"21","author":[{"given":"David","family":"Krieg","sequence":"first","affiliation":[]},{"given":"Mario","family":"Ullrich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,12,7]]},"reference":[{"key":"9481_CR1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484","volume-title":"Numerical methods for least squares problems","author":"\u00c5 Bj\u00f6rk","year":"1996","unstructured":"\u00c5.\u00a0Bj\u00f6rk. Numerical methods for least squares problems. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1996."},{"key":"9481_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.5802\/smai-jcm.24","volume":"3","author":"A Cohen","year":"2017","unstructured":"A.\u00a0Cohen, G.\u00a0Migliorati. Optimal weighted least-squares methods. SMAI-Journal of Computational Mathematics, 3:181\u2013203, 2017.","journal-title":"SMAI-Journal of Computational Mathematics"},{"key":"9481_CR3","doi-asserted-by":"crossref","unstructured":"D. D\u0169ng, V.N.\u00a0Temlyakov, and T.\u00a0Ullrich. Hyperbolic Cross Approximation. Advanced Courses in Mathematics - CRM Barcelona. Springer International Publishing, 2018.","DOI":"10.1007\/978-3-319-92240-9"},{"key":"9481_CR4","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1515\/9783110635461-004","volume-title":"Multivariate Algorithms and Information-Based Complexity","author":"A Hinrichs","year":"2020","unstructured":"A.\u00a0Hinrichs, D.\u00a0Krieg, E.\u00a0Novak, J.\u00a0Prochno, and M.\u00a0Ullrich. On the power of random information. In F.\u00a0J. Hickernell and P.\u00a0Kritzer, editors, Multivariate Algorithms and Information-Based Complexity, pages 43\u201364. De Gruyter, Berlin\/Boston, 2020."},{"key":"9481_CR5","unstructured":"A.\u00a0Hinrichs, D.\u00a0Krieg, E.\u00a0Novak, J.\u00a0Prochno, and M.\u00a0Ullrich. Random sections of ellipsoids and the power of random information. arXiv:1901.06639, 2019."},{"key":"9481_CR6","doi-asserted-by":"crossref","unstructured":"A.\u00a0Hinrichs, E.\u00a0Novak, and J.\u00a0Vyb\u00edral. Linear information versus function evaluations for $$\\ell _2$$-approximation. J. Approx. Theory, 153:97\u2013107, 07 2008.","DOI":"10.1016\/j.jat.2008.02.003"},{"key":"9481_CR7","unstructured":"L.\u00a0K\u00e4mmerer, T.\u00a0Ullrich, T.\u00a0Volkmer. Worst case recovery guarantees for least squares approximation using random samples. arXiv:1911.10111, 2019."},{"key":"9481_CR8","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s00365-018-9428-4","volume":"49","author":"D Krieg","year":"2019","unstructured":"D.\u00a0Krieg. Optimal Monte Carlo methods for $$L_2$$-approximation. Constr.\u00a0Approx., 49:385\u2013403, 2019.","journal-title":"Constr. Approx."},{"key":"9481_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jat.2008.01.011","volume":"158","author":"F Kuo","year":"2009","unstructured":"F.\u00a0Kuo, G.\u00a0W.\u00a0Wasilkowski, and H.\u00a0Wo\u017aniakowski. On the power of standard information for multivariate approximation in the worst case setting. J. Approx. Theory, 158:97\u2013125, 2009.","journal-title":"J. Approx. Theory"},{"issue":"5","key":"9481_CR10","doi-asserted-by":"publisher","first-page":"761","DOI":"10.3150\/bj\/1161614945","volume":"12","author":"S Mendelson","year":"2006","unstructured":"S.\u00a0Mendelson and A.\u00a0Pajor. On singular values of matrices with independent rows. Bernoulli, 12(5):761\u2013773, 2006.","journal-title":"Bernoulli"},{"key":"9481_CR11","doi-asserted-by":"crossref","unstructured":"E.\u00a0Novak and H.\u00a0Wo\u017aniakowski. Tractability of multivariate problems. Vol. 1: Linear information, volume\u00a06 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Z\u00fcrich, 2008.","DOI":"10.4171\/026"},{"key":"9481_CR12","doi-asserted-by":"crossref","unstructured":"E.\u00a0Novak and H.\u00a0Wo\u017aniakowski. Tractability of multivariate problems. Volume II: Standard information for functionals, volume\u00a012 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Z\u00fcrich, 2010.","DOI":"10.4171\/084"},{"key":"9481_CR13","doi-asserted-by":"crossref","unstructured":"E.\u00a0Novak and H.\u00a0Wo\u017aniakowski. Tractability of multivariate problems. Volume III: Standard information for operators, volume\u00a018 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Z\u00fcrich, 2012.","DOI":"10.4171\/116"},{"key":"9481_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.jat.2016.02.017","volume":"207","author":"E Novak","year":"2016","unstructured":"E.\u00a0Novak and H.\u00a0Wo\u017aniakowski. Tractability of multivariate problems for standard and linear information in the worst case setting: Part I. J.\u00a0Approx.\u00a0Theory, 207:177\u2013192, 2016.","journal-title":"J. Approx. Theory"},{"key":"9481_CR15","unstructured":"W.\u00a0Sickel. Approximate recovery of functions and Besov spaces of dominating mixed smoothness. Constructive theory of functions, 404\u2013411, DARBA, Sofia, 2003."},{"key":"9481_CR16","doi-asserted-by":"crossref","unstructured":"W.\u00a0Sickel. Approximation from sparse grids and function spaces of dominating mixed smoothness. Approximation and probability, 271\u2013283, Banach Center Publ., 72, Polish Acad. Sci. Inst. Math., Warsaw, 2006.","DOI":"10.4064\/bc72-0-18"},{"issue":"4","key":"9481_CR17","first-page":"387","volume":"13","author":"W Sickel","year":"2007","unstructured":"W.\u00a0Sickel and T.\u00a0Ullrich. The Smolyak algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness. East J. Approx., 13(4):387\u2013425, 2007.","journal-title":"East J. Approx."},{"key":"9481_CR18","volume-title":"Approximation of periodic functions","author":"VN Temlyakov","year":"1993","unstructured":"V.\u00a0N. Temlyakov. Approximation of periodic functions, Computational Mathematics and Analysis Series, Nova Science Publishers, Inc., Commack, NY, 1993."},{"key":"9481_CR19","unstructured":"V.\u00a0N. Temlyakov. Multivariate Approximation, volume\u00a032 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2018."},{"key":"9481_CR20","doi-asserted-by":"crossref","unstructured":"H.\u00a0Triebel. Bases in Function Spaces, Sampling, Discrepancy, Numerical Integration, volume\u00a011 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Z\u00fcrich, 2010.","DOI":"10.4171\/085"},{"key":"9481_CR21","doi-asserted-by":"publisher","unstructured":"M. Ullrich, On the worst-case error of least squares algorithms for $$L_2$$-approximation with high probability, J. Complexity 60, 2020, https:\/\/doi.org\/10.1016\/j.jco.2020.101484.","DOI":"10.1016\/j.jco.2020.101484"},{"issue":"1","key":"9481_CR22","first-page":"1","volume":"14","author":"T Ullrich","year":"2008","unstructured":"T.\u00a0Ullrich. Smolyak\u2019s algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness. East J. Approx., 14(1):1\u201338, 2008.","journal-title":"East J. Approx."},{"key":"9481_CR23","doi-asserted-by":"crossref","unstructured":"G.\u00a0W.\u00a0Wasilkowski and H.\u00a0Wo\u017aniakowski. The power of standard information for multivariate approximation in the randomized setting. Math.\u00a0Comp., 76:965\u2013988, 2006.","DOI":"10.1090\/S0025-5718-06-01944-2"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09481-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-020-09481-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09481-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,3]],"date-time":"2022-12-03T03:35:36Z","timestamp":1670038536000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-020-09481-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,7]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["9481"],"URL":"https:\/\/doi.org\/10.1007\/s10208-020-09481-w","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,7]]},"assertion":[{"value":"2 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}