×

Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness. (English) Zbl 1422.65467

Error bounds for the reconstruction of multivariate periodic functions sampled on rank-1 lattices \(\Lambda(\pmb{z},M)\), with generating vector \(\pmb{z} \in \mathbb{Z}^d\) and lattice size \(M\), are developed. The weighted Hilbert spaces \(\mathcal{H}^{\alpha,\beta}(\mathbb{T}^d)\) of complex functions \(f:\mathbb{T}^d\rightarrow \mathbb{C}\), defined on the \(d\)-dimensional torus \(\mathbb{T}^d\), depend on smoothness parameters \(\alpha,\beta \in \mathbb{R}\). Specific errors \(g_M^{\mathrm{latt}_1}(\mathcal{F},Y)\) for functions of the class \(\mathcal{F}\) and the operator norm in the functions class \(Y\) are introduced. For functions \(f\in\mathcal{F}\), reconstructed by an operator \(A:\mathbb{C}^M\rightarrow Y\) from its samples on the lattice \(\Lambda(\pmb{z},M)=\{\mathbf{x}^1,\dots,\mathbf{x}^M\}\subset \mathbb{T}^d\), the errors are defined as \[ g^{\mathrm{latt}_1}_M({\mathcal{F}},Y)=\inf_{\pmb{z}\in\mathbb{Z}^d}\text{Samp}_{\Lambda(\pmb{z},M)}({\mathcal{F}},Y), \] with the quantity \(\text{Samp}_{\Lambda(\pmb{z},M)}\) given as \[ \text{Samp}_{\Lambda(\pmb{z},M)}({\mathcal{F}},Y)=\inf_{ A:\mathbb{C}^M\to Y}\sup_{\|f|{\mathcal{F}}\|\leq 1} \left\|f-A\big(f(\mathbf{x}^i)\big)_{i=1}^M\right\|_Y\,. \] Lower and upper bounds for various combinations of the spaces \(\mathcal{F}\) and \(Y\) are derived, notably the following bounds for \(M\in \mathbb{N}\) are stated: \[ 2^{-\frac{\alpha+1}{2}} M^{-\frac{\alpha}{2}} \leq g^{\mathrm{latt}_1}_M(\mathcal{H}^{\alpha,0}(\mathbb{T}^d),\qquad L_2(\mathbb{T}^d)) \lesssim M^{-\frac{\alpha}{2}}(\log M)^{\frac{d-2}{2}\alpha+\frac{d-1}{2}}. \] Upper bounds for the special case \(d=2\) are further developed. The results are numerically tested on a specific model function \(f\) and for a specific fast approximate reconstruction algorithm.

MSC:

65T40 Numerical methods for trigonometric approximation and interpolation
42A10 Trigonometric approximation
65D30 Numerical integration
65D32 Numerical quadrature and cubature formulas
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
42B35 Function spaces arising in harmonic analysis
65T50 Numerical methods for discrete and fast Fourier transforms
65Y20 Complexity and performance of numerical algorithms

Software:

MPAWL
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bergmann, R.: The fast Fourier transform and fast wavelet transform for patterns on the torus. Appl. Comput. Harmon. Anal. 35, 39-51 (2013) · Zbl 1432.65205 · doi:10.1016/j.acha.2012.07.007
[2] Bungartz, H.J., Griebel, M.: Sparse grids. Acta Numer. 13, 1-123 (2004) · Zbl 1122.65405 · doi:10.1017/S0962492904000182
[3] Byrenheid, G., Dũng, D., Sickel, W., Ullrich, T.: Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in \[{H}^{\gamma }\] Hγ. J. Approx. Theory 207, 207-231 (2016) · Zbl 1347.42003 · doi:10.1016/j.jat.2016.02.012
[4] Cools, R., Kuo, F.Y., Nuyens, D.: Constructing lattice rules based on weighted degree of exactness and worst-case error. Computing 87, 63-89 (2010) · Zbl 1190.65037 · doi:10.1007/s00607-009-0076-1
[5] Cools, R., Nuyens, D.: An overview of fast component-by-component constructions of lattice rules and lattice sequences. PAMM 7, 1022,609-1022,610 (2007) · doi:10.1002/pamm.200700083
[6] Dũng, D., Ullrich, T.: N-widths and \[\varepsilon\] ε-dimensions for high-dimensional approximations. Found. Comput. Math. 13, 965-1003 (2013) · Zbl 1284.42001 · doi:10.1007/s10208-013-9149-9
[7] Dũng, D.: Sampling and cubature on sparse grids based on a B-spline quasi-interpolation. Found. Comput. Math. 16, 1193-1240 (2016) · Zbl 1359.41001
[8] Dung, D., Temlyakov, V.N., Ullrich, T.: Hyperbolic Cross Approximation. ArXiv e-prints (2015). ArXiv:1601.03978 [math.NA] · Zbl 1414.41001
[9] Griebel, M., Hamaekers, J.: Fast discrete Fourier transform on generalized sparse grids. In: Garcke, J., Pflüger, D. (eds.) Sparse Grids and Applications—Munich 2012. Lecture Notes in Computational Science and Engineering, vol. 97, pp. 75-107. Springer International Publishing (2014) · Zbl 1316.65119
[10] Griebel, M., Knapek, S.: Optimized general sparse grid approximation spaces for operator equations. Math. Comput. 78, 2223-2257 (2009) · Zbl 1198.65053 · doi:10.1090/S0025-5718-09-02248-0
[11] Hinrichs, A., Markhasin, L., Oettershagen, J., Ullrich, T.: Optimal quasi-Monte Carlo rules on higher order digital nets for the numerical integration of multivariate periodic functions. Numer. Math 134, 163-196 (2016) · Zbl 1358.65004 · doi:10.1007/s00211-015-0765-y
[12] Kämmerer, L.: Reconstructing hyperbolic cross trigonometric polynomials by sampling along rank-1 lattices. SIAM J. Numer. Anal. 51, 2773-2796 (2013) · Zbl 1291.42011 · doi:10.1137/120871183
[13] Kämmerer, L.: High dimensional fast Fourier transform based on rank-1 lattice sampling. Dissertation. Universitätsverlag Chemnitz (2014). http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-157673
[14] Kämmerer, L.: Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices. In: G.E. Fasshauer, L.L. Schumaker (eds.) Approximation Theory XIV: San Antonio 2013, pp. 255-271. Springer International Publishing (2014) · Zbl 1325.65189
[15] Kämmerer, L.: Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials. J. Fourier Anal. Appl. 1-28 (2016). doi:10.1007/s00041-016-9520-8 · Zbl 1401.65155
[16] Kämmerer, L., Kunis, S., Potts, D.: Interpolation lattices for hyperbolic cross trigonometric polynomials. J. Complex. 28, 76-92 (2012) · Zbl 1335.65105 · doi:10.1016/j.jco.2011.05.002
[17] Kämmerer, L., Potts, D., Volkmer, T.: Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling. J. Complex. 31, 543-576 (2015) · Zbl 1320.65204 · doi:10.1016/j.jco.2015.02.004
[18] Kämmerer, L., Potts, D., Volkmer, T.: Approximation of multivariate periodic functions by trigonometric polynomials based on sampling along rank-1 lattice with generating vector of Korobov form. J. Complex. 31, 424-456 (2015) · Zbl 1318.42006 · doi:10.1016/j.jco.2014.09.001
[19] Knapek, S.: Approximation und Kompression mit Tensorprodukt-Multiskalenräumen. Dissertation, Universität Bonn (2000) · Zbl 1097.65133
[20] Kühn, T., Sickel, W., Ullrich, T.: Approximation of mixed order Sobolev functions on the d-torus asymptotics, preasymptotics and d-dependence. Constr. Approx. 42, 353-398 (2015) · Zbl 1485.47025 · doi:10.1007/s00365-015-9299-x
[21] Kuo, FY; Sloan, IH; Woźniakowski, H.; Niederreiter, H. (ed.); Talay, D. (ed.), Lattice rules for multivariate approximation in the worst-case setting, 289-330 (2006), Berlin · Zbl 1097.65133 · doi:10.1007/3-540-31186-6_18
[22] Kuo, F.Y., Sloan, I.H., Woźniakowski, H.: Lattice rule algorithms for multivariate approximation in the average-case setting. J. Complex. 24, 283-323 (2008) · Zbl 1141.65012 · doi:10.1016/j.jco.2006.10.006
[23] Kuo, F.Y., Wasilkowski, G.W., Woźniakowski, H.: Lattice algorithms for multivariate \[L_{\infty }\] L∞ approximation in the worst-case setting. Constr. Approx. 30, 475-493 (2009) · Zbl 1182.65025 · doi:10.1007/s00365-009-9075-x
[24] Li, D., Hickernell, F.J.: Trigonometric spectral collocation methods on lattices. In: Recent Advances in Scientific Computing and Partial Differential Equations, Hong Kong, 2002. Contemporary Mathematics, vol. 330, pp. 121-132. American Mathematical Society, Providence (2003) · Zbl 1036.65093
[25] Niederreiter, H.: Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Am. Math. Soc. 84, 957-1041 (1978) · Zbl 0404.65003 · doi:10.1090/S0002-9904-1978-14532-7
[26] Schmeisser, H.J., Triebel, H.: Topics in Fourier Analysis and Function Spaces. Wiley, Chichester (1987) · Zbl 0661.46025
[27] Sickel, W., Ullrich, T.: The Smolyak algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness. East J. Approx. 13, 387-425 (2007) · Zbl 1487.41025
[28] Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Oxford Science Publications, New York (1994) · Zbl 0855.65013
[29] Sloan, I.H., Reztsov, A.V.: Component-by-component construction of good lattice rules. Math. Comput. 71, 263-273 (2002) · Zbl 0985.65018 · doi:10.1090/S0025-5718-01-01342-4
[30] Temlyakov, V.N.: Reconstruction of periodic functions of several variables from the values at the nodes of number-theoretic nets. Anal. Math. 12, 287-305 (1986). In Russian · Zbl 0621.41004 · doi:10.1007/BF01909367
[31] Temlyakov, V.N.: Approximation of functions with bounded mixed derivative. Trudy Mat. Inst. Steklov. 178, 3-113 (1986) (In Russian). [English transl. in Proc. Steklov Inst. Math., 1 (1989)] · Zbl 0625.41028
[32] Temlyakov, V.N.: Approximation of Periodic Functions. Computational Mathematics and Analysis Series. Nova Science Publishers Inc., Commack (1993) · Zbl 0899.41001
[33] Yserentant, H.: Regularity and Approximability of Electronic Wave Functions. Lecture Notes in Mathematics, vol. 2000. Springer, Berlin (2010) · Zbl 1204.35003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.