$D$-optimal designs originate in statistics literature as an approach for optimal experimental designs. In numerical analysis points and weights resulting from maximal determinants turned out to be useful for quadrature and interpolation. Also recently, two of the present authors and coauthors investigated a connection to the discretization problem for the uniform norm. Here we use this approach of maximizing the determinant of a certain Gramian matrix with respect to points and weights for the construction of tight frames and exact Marcinkiewicz–Zygmund inequalities in $L_2$. We present a direct and constructive approach resulting in a discrete measure with at most $N \le n^2+1$ atoms, which discretely and accurately subsamples the $L_2$-norm of complex-valued functions contained in a given $n$-dimensional subspace. This approach can as well be used for the reconstruction of functions from general RKHS in $L_2$ where one only has access to the most important eigenfunctions. We verifiably and deterministically construct points and weights for a weighted least squares recovery procedure and pay in the rate of convergence compared to earlier optimal, however probabilistic approaches. The general results apply to the $d$-sphere or multivariate trigonometric polynomials on $\mathbb{T}^d$ spectrally supported on arbitrary finite index sets $I \subset \mathbb{Z}^d$. They can be discretized using at most $|I|^2-|I|+1$ points and weights. Numerical experiments indicate the sharpness of this result. As a negative result we prove that, in general, it is not possible to control the number of points in a reconstructing lattice rule only in the cardinality $|I|$ without additional condition on the structure of $I$. We support our findings with numerical experiments.
Keywords: Integral norm discretization, exact quadrature, sampling recovery, $D$-optimal designs
Felix Bartel 1; Lutz Kämmerer 2; Kateryna Pozharska 3; Martin Schäfer 2; Tino Ullrich 2
@article{SMAI-JCM_2025__11__607_0,
author = {Felix Bartel and Lutz K\"ammerer and Kateryna Pozharska and Martin Sch\"afer and Tino Ullrich},
title = {Exact discretization, tight frames and recovery via $D$-optimal designs},
journal = {The SMAI Journal of computational mathematics},
pages = {607--636},
year = {2025},
publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
volume = {11},
doi = {10.5802/smai-jcm.136},
language = {en},
url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.136/}
}
TY - JOUR AU - Felix Bartel AU - Lutz Kämmerer AU - Kateryna Pozharska AU - Martin Schäfer AU - Tino Ullrich TI - Exact discretization, tight frames and recovery via $D$-optimal designs JO - The SMAI Journal of computational mathematics PY - 2025 SP - 607 EP - 636 VL - 11 PB - Société de Mathématiques Appliquées et Industrielles UR - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.136/ DO - 10.5802/smai-jcm.136 LA - en ID - SMAI-JCM_2025__11__607_0 ER -
%0 Journal Article %A Felix Bartel %A Lutz Kämmerer %A Kateryna Pozharska %A Martin Schäfer %A Tino Ullrich %T Exact discretization, tight frames and recovery via $D$-optimal designs %J The SMAI Journal of computational mathematics %D 2025 %P 607-636 %V 11 %I Société de Mathématiques Appliquées et Industrielles %U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.136/ %R 10.5802/smai-jcm.136 %G en %F SMAI-JCM_2025__11__607_0
Felix Bartel; Lutz Kämmerer; Kateryna Pozharska; Martin Schäfer; Tino Ullrich. Exact discretization, tight frames and recovery via $D$-optimal designs. The SMAI Journal of computational mathematics, Volume 11 (2025), pp. 607-636. doi: 10.5802/smai-jcm.136
[1] Well Conditioned Spherical Designs for Integration and Interpolation on the Two-Sphere, SIAM J. Numer. Anal., Volume 48 (2010) no. 6, pp. 2135-2157 | DOI | Zbl | MR
[2] On the reconstruction of functions from values at subsampled quadrature points, Math. Comput., Volume 93 (2024) no. 346, pp. 785-809 | DOI | MR | Zbl
[3] Constructive subsampling of finite frames with applications in optimal function recovery, Appl. Comput. Harmon. Anal., Volume 65 (2023), pp. 209-248 | DOI | MR | Zbl
[4] Twice-Ramanujan sparsifiers, SIAM J. Comput., Volume 41 (2012) no. 6, pp. 1704-1721 | DOI | MR | Zbl
[5] Transfinite diameter notions in and integrals of Vandermonde determinants, Ark. Mat., Volume 48 (2010) no. 1, pp. 17-40 | DOI | Zbl | MR
[6] Optimal asymptotic bounds for spherical designs, Ann. Math., Volume 178 (2013) no. 2, pp. 443-452 (Accessed 2024-08-04) | DOI | Zbl
[7] On optimal designs for a -cube, Dolomites Res. Notes Approx., Volume 15 (2022) no. 4, pp. 20-34 | Zbl | MR
[8] On Fekete points for a real simplex, Indag. Math., Volume 34 (2023) no. 2, pp. 274-293 (special issue on the occasion of Jaap Korevaar’s 100-th anniversary) | DOI | Zbl
[9] Near G-optimal Tchakaloff designs, Comput. Stat., Volume 35 (2020) no. 2, pp. 803-819 | MR | Zbl
[10] Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness, Numer. Math., Volume 136 (2017) no. 4, pp. 993-1034 | DOI | MR | Zbl
[11] A note on scalable frames, Conference proceedings of SampTA, Zenodo (2013), pp. 93-96 | DOI
[12] Frame scalings: A condition number approach, Linear Algebra Appl., Volume 523 (2017), pp. 152-168 | DOI | Zbl | MR
[13] Remarks on scalable frames, Oper. Matrices, Volume 17 (2023) no. 2, pp. 327-342 | DOI | Zbl | MR
[14] Auto-tuning unit norm frames, Appl. Comput. Harmon. Anal., Volume 32 (2012) no. 1, pp. 1-15 | DOI | Zbl
[15] Equal-norm tight frames with erasures, Adv. Comput. Math., Volume 18 (2003) no. 2/4, pp. 387-430 | DOI | MR | Zbl
[16] Optimal approximation of multivariate periodic Sobolev functions in the sup-norm, J. Funct. Anal., Volume 270 (2016) no. 11, pp. 4196-4212 | DOI | MR | Zbl
[17] Constructing cubature formulae: the science behind the art, Acta numerica, 1997 (Acta Numerica), Volume 6, Cambridge University Press, 1997, pp. 1-54 | DOI | MR | Zbl
[18] Integral norm discretization and related problems, Russ. Math. Surv., Volume 74 (2019) no. 4, pp. 579-630 | DOI | Zbl
[19] Approximation Theory and Harmonic Analysis on Spheres and Balls, Springer Monographs in Mathematics, Springer, 2013 | DOI | Zbl | MR
[20] Spherical codes and designs, Geom. Dedicata, Volume 6 (1977) no. 3, pp. 363-388 | DOI | Zbl | MR
[21] Unbiased estimators for random design regression, J. Mach. Learn. Res., Volume 23 (2022), 167, 46 pages | MR | Zbl
[22] The theory of canonical moments with applications in statistics, probability, and analysis, Wiley Series in Probability and Statistics, John Wiley & Sons, 1997, xx+327 pages | MR | Zbl
[23] High-dimensional integration: the quasi-Monte Carlo way, Acta Numer., Volume 22 (2013), pp. 133-288 | DOI | MR | Zbl
[24] A sharp upper bound for sampling numbers in , Appl. Comput. Harmon. Anal., Volume 63 (2023), pp. 113-134 | MR | DOI | Zbl
[25] Hyperbolic cross approximation, Advanced Courses in Mathematics – CRM Barcelona, Birkhäuser/Springer, 2018, xi+218 pages (edited and with a foreword by Sergey Tikhonov) | DOI | MR
[26] Marcinkiewicz-Zygmund inequalities for scattered and random data on the -sphere, Appl. Comput. Harmon. Anal., Volume 71 (2024), 101651, 18 pages | DOI | MR | Zbl
[27] Discretizing norms and frame theory, J. Math. Anal. Appl., Volume 519 (2023) no. 2, 126846 | DOI | MR
[28] The discretization problem for continuous frames, Adv. Math., Volume 345 (2019), pp. 784-813 | DOI | MR
[29] On the computation of spherical designs by a new optimization approach based on fast spherical Fourier transforms, Numer. Math., Volume 119 (2011) no. 4, pp. 699-724 | MR | DOI
[30] Iterative methods for solving linear systems, Frontiers in Applied Mathematics, 17, Society for Industrial and Applied Mathematics, 1997, xiv+220 pages | DOI | MR
[31] Sampling, Marcinkiewicz–Zygmund inequalities, approximation, and quadrature rules, J. Approx. Theory, Volume 257 (2020), 105455 | DOI | MR
[32] Reconstructing hyperbolic cross trigonometric polynomials by sampling along rank-1 lattices, SIAM J. Numer. Anal., Volume 51 (2013), pp. 2773-2796 | MR | DOI
[33] Reconstructing Multivariate Trigonometric Polynomials from Samples Along Rank-1 Lattices, Approximation Theory XIV: San Antonio 2013 (Gregory E. Fasshauer; Larry L. Schumaker, eds.) (Springer Proceedings in Mathematics & Statistics), Springer (2014), pp. 255-271
[34] Approximation of multivariate periodic functions by trigonometric polynomials based on sampling along rank-1 lattice with generating vector of Korobov form, J. Complexity, Volume 31 (2015) no. 3, pp. 424-456 | MR | DOI
[35] Worst-case recovery guarantees for least squares approximation using random samples, Constr. Approx., Volume 54 (2021) no. 2, pp. 295-352 | DOI | MR
[36] The equivalence of two extremum problems, Can. J. Math., Volume 12 (1960), pp. 363-366 | DOI | MR
[37] Remarks on sampling discretization of integral norms of functions, Tr. Mat. Inst. Steklova, Volume 319 (2022), pp. 202-212 | DOI | MR
[38] Sampling projections in the uniform norm (2024) | arXiv
[39] Function values are enough for -approximation, Found. Comput. Math., Volume 21 (2021) no. 4, pp. 1141-1151 | DOI | MR
[40] Function integration, reconstruction and approximation using rank- lattices, Math. Comput., Volume 90 (2021) no. 330, pp. 1861-1897 | MR | DOI
[41] Scalable frames and convex geometry, Operator methods in wavelets, tilings, and frames. AMS special session on harmonic analysis of frames, wavelets, and tilings (Contemporary Mathematics), Volume 626, Springer, 2014, pp. 19-32
[42] Sur les fonctions indépendantes, Fundam. Math., Volume 29 (1937) no. 1, pp. 60-90 | DOI
[43] Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem, Ann. Math. (2), Volume 182 (2015) no. 1, pp. 327-350 | DOI | MR
[44] Stable high-order randomized cubature formulae in arbitrary dimension, J. Approx. Theory, Volume 275 (2022), 105706 | MR | DOI
[45] A new upper bound for sampling numbers, Found. Comput. Math., Volume 22 (2022) no. 2, pp. 445-468 | DOI | MR
[46] Exponential frames on unbounded sets, Proc. Am. Math. Soc., Volume 144 (2016) no. 1, pp. 109-118 | DOI | MR
[47] Quadrature and widths, J. Approx. Theory, Volume 47 (1986) no. 3, pp. 195-202 | MR | DOI
[48] Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, 6, European Mathematical Society, 2008, xii+384 pages | DOI | MR
[49] Caratheodory-Tchakaloff subsampling, Dolomites Res. Notes Approx., Volume 10 (2017) no. 1, pp. 5-14 | MR
[50] A note on Tchakaloff’s theorem, Proc. Am. Math. Soc., Volume 125 (1997) no. 8, pp. 2409-2414 | DOI | MR
[51] Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and Its Applications, 151, Cambridge University Press, 2014, xxii+736 pages | MR
[52] Topics in approximation theory, Lecture Notes in Mathematics, 187, Springer, 1971, viii+275 pages (with appendices by Jan Boman and Torbjörn Hedberg) | DOI | MR
[53] The Smolyak algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness, East J. Approx., Volume 13 (2007) no. 4, pp. 387-425 | MR
[54] The Representation of Lattice Quadrature Rules as Multiple Sums, Math. Comput., Volume 52 (1989) no. 185, pp. 81-94 | MR | DOI
[55] Orthogonal Polynomials, American Mathematical Society, 1975 | MR
[56] Formules de cubatures mécaniques à coefficients non négatifs, Bull. Sci. Math. (2), Volume 81 (1957), pp. 123-134 | MR
[57] The Marcinkiewicz-type discretization theorems for the hyperbolic cross polynomials, Jaen J. Approx., Volume 9 (2017) no. 1, pp. 37-63 | MR
[58] User-friendly tail bounds for sums of random matrices, Found. Comput. Math., Volume 12 (2012) no. 4, pp. 389-434 | DOI | MR
[59] On the power of standard information for weighted approximation, Found. Comput. Math., Volume 1 (2001) no. 4, pp. 417-434 | DOI | MR
[60] Efficient Spherical Designs with Good Geometric Properties, Springer (2018), pp. 1243-1285 | DOI
Cited by Sources: