{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:44:28Z","timestamp":1778496268834,"version":"3.51.4"},"reference-count":49,"publisher":"American Mathematical Society (AMS)","issue":"346","license":[{"start":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T00:00:00Z","timestamp":1724803200000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    This paper is concerned with function reconstruction from samples. The sampling points used in several approaches are (1) structured points connected with fast algorithms or (2) unstructured points coming from, e.g., an initial random draw to achieve an improved information complexity. We connect both approaches and propose a subsampling of structured points in an offline step. In particular, we start with quasi-Monte Carlo (QMC) points with inherent structure and stable\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper L 2\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>L<\/mml:mi>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">L_2<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    reconstruction properties. The subsampling procedure consists of a computationally inexpensive random step followed by a deterministic procedure to further reduce the number of points while keeping its information. In these points functions (belonging to a reproducing kernel Hilbert space of bounded functions) will be sampled and reconstructed from whilst achieving state of the art error decay.\n                  <\/p>\n                  <p>\n                    Our method is dimension-independent and is applicable as soon as we know some initial quadrature points. We apply our general findings on the\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"d\">\n                        <mml:semantics>\n                          <mml:mi>d<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">d<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -dimensional torus to subsample rank-1 lattices, where it is known that full rank-1 lattices lose half the optimal order of convergence (expressed in terms of the size of the lattice). In contrast to that, our subsampled version regains the optimal rate since many of the lattice points are not needed. Moreover, we utilize fast and memory efficient Fourier algorithms in order to compute the approximation. Numerical experiments in several dimensions support our findings.\n                  <\/p>","DOI":"10.1090\/mcom\/3896","type":"journal-article","created":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T09:53:46Z","timestamp":1690970026000},"page":"785-809","source":"Crossref","is-referenced-by-count":9,"title":["On the reconstruction of functions from values at subsampled quadrature points"],"prefix":"10.1090","volume":"93","author":[{"given":"Felix","family":"Bartel","sequence":"first","affiliation":[]},{"given":"Lutz","family":"K\u00e4mmerer","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Potts","sequence":"additional","affiliation":[]},{"given":"Tino","family":"Ullrich","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2023,8,28]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.acha.2023.02.004","article-title":"Constructive subsampling of finite frames with applications in optimal function recovery","volume":"65","author":"Bartel, Felix","year":"2023","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"key":"2","isbn-type":"print","first-page":"255","article-title":"Twice-Ramanujan sparsifiers","author":"Batson, Joshua D.","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9781605586137"},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9096-9","volume-title":"Reproducing kernel Hilbert spaces in probability and statistics","author":"Berlinet, Alain","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/1402076797"},{"issue":"4","key":"4","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1007\/s00211-016-0861-7","article-title":"Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness","volume":"136","author":"Byrenheid, Glenn","year":"2017","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"5","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.jat.2016.02.012","article-title":"Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in \ud835\udc3b^{\ud835\udefe}","volume":"207","author":"Byrenheid, Glenn","year":"2016","journal-title":"J. Approx. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9045","issn-type":"print"},{"key":"6","unstructured":"A. Christmann and I. Steinwart, Support Vector Machines, Springer, 2008."},{"issue":"5","key":"7","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s10208-013-9142-3","article-title":"On the stability and accuracy of least squares approximations","volume":"13","author":"Cohen, Albert","year":"2013","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.5802\/smai-jcm.24","article-title":"Optimal weighted least-squares methods","volume":"3","author":"Cohen, Albert","year":"2017","journal-title":"SMAI J. Comput. Math."},{"key":"9","doi-asserted-by":"crossref","unstructured":"R. Cools and D. Nuyens, An overview of fast component-by-component constructions of lattice rules and lattice sequences, PAMM 7 (2007), 1022609\u20131022610.","DOI":"10.1002\/pamm.200700919"},{"key":"10","series-title":"Advanced Courses in Mathematics. CRM Barcelona","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92240-9","volume-title":"Hyperbolic cross approximation","author":"D\u0169ng, Dinh","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319922393"},{"key":"11","series-title":"Springer Series in Computational Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09951-9","volume-title":"Lattice rules---numerical integration, approximation, and discrepancy","volume":"58","author":"Dick, Josef","year":"[2022] \\copyright2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031099502"},{"key":"12","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1017\/S0962492913000044","article-title":"High-dimensional integration: the quasi-Monte Carlo way","volume":"22","author":"Dick, Josef","year":"2013","journal-title":"Acta Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0962-4929","issn-type":"print"},{"key":"13","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.acha.2022.12.001","article-title":"A sharp upper bound for sampling numbers in \ud835\udc3f\u2082","volume":"63","author":"Dolbeault, Matthieu","year":"2023","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"issue":"6","key":"14","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/j.jco.2011.03.002","article-title":"Marcinkiewicz-Zygmund measures on manifolds","volume":"27","author":"Filbir, F.","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"15","series-title":"Frontiers in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970937","volume-title":"Iterative methods for solving linear systems","volume":"17","author":"Greenbaum, Anne","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/089871396X"},{"key":"16","doi-asserted-by":"publisher","first-page":"105455","DOI":"10.1016\/j.jat.2020.105455","article-title":"Sampling, Marcinkiewicz-Zygmund inequalities, approximation, and quadrature rules","volume":"257","author":"Gr\u00f6chenig, Karlheinz","year":"2020","journal-title":"J. Approx. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9045","issn-type":"print"},{"issue":"335","key":"17","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1090\/mcom\/3710","article-title":"Boosted optimal weighted least-squares","volume":"91","author":"Haberstich, C\u00e9cile","year":"2022","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"18","doi-asserted-by":"publisher","first-page":"Paper No. 101662, 15","DOI":"10.1016\/j.jco.2022.101662","article-title":"Lower bounds for integration and recovery in \ud835\udc3f\u2082","volume":"72","author":"Hinrichs, Aicke","year":"2022","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"19","doi-asserted-by":"crossref","unstructured":"T. Jahn, T. Ullrich, and F. Voigtlaender, Sampling numbers of smoothness classes via \u2113\u2081-minimization, to appear in J. Complexity,  arXiv:2212.00445 (2022).","DOI":"10.1016\/j.jco.2023.101786"},{"issue":"1","key":"20","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00211-021-01242-3","article-title":"Fast approximation by periodic kernel-based lattice-point interpolation with application in uncertainty quantification","volume":"150","author":"Kaarnioja, Vesa","year":"2022","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"21","unstructured":"L. K\u00e4mmerer, High Dimensional Fast Fourier Transform Based on Rank-1 Lattice Sampling, Dissertation, Universit\u00e4tsverlag Chemnitz, 2014."},{"key":"22","unstructured":"L. K\u00e4mmerer, A fast probabilistic component-by-component construction of exactly integrating rank-1 lattices and applications,  arXiv:2012.14263 (2020)."},{"issue":"4","key":"23","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.jco.2015.02.004","article-title":"Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling","volume":"31","author":"K\u00e4mmerer, Lutz","year":"2015","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"24","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.acha.2020.11.002","article-title":"High-dimensional sparse FFT based on sampling along multiple rank-1 lattices","volume":"51","author":"K\u00e4mmerer, Lutz","year":"2021","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"issue":"2","key":"25","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00365-021-09555-0","article-title":"Worst-case recovery guarantees for least squares approximation using random samples","volume":"54","author":"K\u00e4mmerer, Lutz","year":"2021","journal-title":"Constr. Approx.","ISSN":"https:\/\/id.crossref.org\/issn\/0176-4276","issn-type":"print"},{"key":"26","doi-asserted-by":"publisher","first-page":"Paper No. 101653, 55","DOI":"10.1016\/j.jco.2022.101653","article-title":"Sampling discretization and related problems","volume":"71","author":"Kashin, B.","year":"2022","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"4","key":"27","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s00041-006-6915-y","article-title":"Efficient reconstruction of functions on the sphere from scattered data","volume":"13","author":"Keiner, Jens","year":"2007","journal-title":"J. Fourier Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1069-5869","issn-type":"print"},{"issue":"4","key":"28","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1007\/s10208-020-09481-w","article-title":"Function values are enough for \ud835\udc3f\u2082-approximation","volume":"21","author":"Krieg, David","year":"2021","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"29","doi-asserted-by":"publisher","first-page":"Paper No. 101569, 14","DOI":"10.1016\/j.jco.2021.101569","article-title":"Function values are enough for \ud835\udc3f\u2082-approximation: Part II","volume":"66","author":"Krieg, David","year":"2021","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"30","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00365-015-9299-x","article-title":"Approximation of mixed order Sobolev functions on the \ud835\udc51-torus: asymptotics, preasymptotics, and \ud835\udc51-dependence","volume":"42","author":"K\u00fchn, Thomas","year":"2015","journal-title":"Constr. Approx.","ISSN":"https:\/\/id.crossref.org\/issn\/0176-4276","issn-type":"print"},{"issue":"1","key":"31","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0377-0427(03)00546-6","article-title":"Fast spherical Fourier algorithms","volume":"161","author":"Kunis, Stefan","year":"2003","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"330","key":"32","doi-asserted-by":"publisher","first-page":"1861","DOI":"10.1090\/mcom\/3595","article-title":"Function integration, reconstruction and approximation using rank-1 lattices","volume":"90","author":"Kuo, Frances Y.","year":"2021","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"33","doi-asserted-by":"publisher","first-page":"Paper No. 126457, 14","DOI":"10.1016\/j.jmaa.2022.126457","article-title":"On sampling discretization in \ud835\udc3f\u2082","volume":"515","author":"Limonova, I.","year":"2022","journal-title":"J. Math. Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-247X","issn-type":"print"},{"key":"34","doi-asserted-by":"crossref","unstructured":"J. Marcinkiewicz and A. Zygmund, Sur les fonctions ind\u00e9pendantes, Fund. Math. 29 (1937), no. 1, 60\u201390 (fre).","DOI":"10.4064\/fm-29-1-60-90"},{"issue":"235","key":"35","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1090\/S0025-5718-00-01240-0","article-title":"Spherical Marcinkiewicz-Zygmund inequalities and positive quadrature","volume":"70","author":"Mhaskar, H. N.","year":"2001","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"36","doi-asserted-by":"publisher","first-page":"Paper No. 13, 31","DOI":"10.1007\/s43670-021-00013-3","article-title":"\ud835\udc3f\u2082-norm sampling discretization and recovery of functions from RKHS with finite trace","volume":"19","author":"Moeller, Moritz","year":"2021","journal-title":"Sampl. Theory Signal Process. Data Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/2730-5716","issn-type":"print"},{"issue":"2","key":"37","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10208-021-09504-0","article-title":"A new upper bound for sampling numbers","volume":"22","author":"Nagel, Nicolas","year":"2022","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"306","key":"38","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1090\/mcom\/3192","article-title":"A Christoffel function weighted least squares algorithm for collocation approximations","volume":"86","author":"Narayan, Akil","year":"2017","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"39","series-title":"Applied and Numerical Harmonic Analysis","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04306-3","volume-title":"Numerical Fourier analysis","author":"Plonka, Gerlind","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030043056"},{"key":"40","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/S0024-3795(02)00592-X","article-title":"Fast algorithms for discrete polynomial transforms on arbitrary grids","volume":"366","author":"Potts, Daniel","year":"2003","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"3","key":"41","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s11075-009-9277-0","article-title":"A fast algorithm for nonequispaced Fourier transforms on the rotation group","volume":"52","author":"Potts, Daniel","year":"2009","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"key":"42","series-title":"Oxford Science Publications","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198534723.001.0001","volume-title":"Lattice methods for multiple integration","author":"Sloan, I. H.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0198534728"},{"key":"43","series-title":"Computational Mathematics and Analysis Series","isbn-type":"print","volume-title":"Approximation of periodic functions","author":"Temlyakov, V. N.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/1560721316"},{"issue":"2","key":"44","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00365-018-9446-2","article-title":"The Marcinkiewicz-type discretization theorems","volume":"48","author":"Temlyakov, V. N.","year":"2018","journal-title":"Constr. Approx.","ISSN":"https:\/\/id.crossref.org\/issn\/0176-4276","issn-type":"print"},{"key":"45","doi-asserted-by":"publisher","first-page":"Paper No. 101545, 11","DOI":"10.1016\/j.jco.2020.101545","article-title":"On optimal recovery in \ud835\udc3f\u2082","volume":"65","author":"Temlyakov, V.","year":"2021","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"46","doi-asserted-by":"publisher","first-page":"Paper No. 101575, 19","DOI":"10.1016\/j.jco.2021.101575","article-title":"Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness","volume":"67","author":"Temlyakov, V.","year":"2021","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"47","doi-asserted-by":"publisher","first-page":"Paper No. 105718, 23","DOI":"10.1016\/j.jat.2022.105718","article-title":"Approximation of functions with small mixed smoothness in the uniform norm","volume":"277","author":"Temlyakov, Vladimir N.","year":"2022","journal-title":"J. Approx. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9045","issn-type":"print"},{"key":"48","isbn-type":"print","volume-title":"Approximation theory and approximation practice","author":"Trefethen, Lloyd N.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781611972399"},{"issue":"4","key":"49","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10208-011-9099-z","article-title":"User-friendly tail bounds for sums of random matrices","volume":"12","author":"Tropp, Joel A.","year":"2012","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-346\/S0025-5718-2023-03896-0\/S0025-5718-2023-03896-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:13:03Z","timestamp":1776834783000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-346\/S0025-5718-2023-03896-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,28]]},"references-count":49,"journal-issue":{"issue":"346","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S0025-5718-2023-03896-0"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3896","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2023,8,28]]}}}