Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling. (English) Zbl 1320.65204
Summary: We present algorithms for the approximation of multivariate periodic functions by trigonometric polynomials. The approximation is based on sampling of multivariate functions on rank-1 lattices. To this end, we study the approximation of periodic functions of a certain smoothness. Our considerations include functions from periodic Sobolev spaces of generalized mixed smoothness. Recently an algorithm for the trigonometric interpolation on generalized sparse grids for this class of functions was investigated by M. Griebel and J. Hamaekers [Lect. Notes Comput. Sci. Eng. 97, 75–107 (2014; Zbl 1316.65119)]. The main advantage of our method is that the algorithm is based mainly on a single one-dimensional fast Fourier transform, and that the arithmetic complexity of the algorithm depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Therefore, we investigate trigonometric polynomials with frequencies supported on hyperbolic crosses and energy norm based hyperbolic crosses in more detail. Furthermore, we present an algorithm for sampling multivariate functions on perturbed rank-1 lattices and show the numerical stability of the suggested method. Numerical results are presented up to dimension \(d = 10\), which confirm the theoretical findings.
MSC:
| 65T40 | Numerical methods for trigonometric approximation and interpolation |
| 42C40 | Nontrigonometric harmonic analysis involving wavelets and other special systems |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
Keywords:
approximation of multivariate functions; trigonometric polynomials; Taylor approximation; hyperbolic cross; lattice rule; fast Fourier transformCitations:
Zbl 1316.65119References:
| [1] | Anderson, C.; Dahleh, M., Rapid computation of the discrete Fourier transform, SIAM J. Sci. Comput., 17, 913-919 (1996) · Zbl 0858.65144 |
| [2] | Baszenski, G.; Delvos, F.-J., A discrete Fourier transform scheme for Boolean sums of trigonometric operators, (Chui, C. K.; Schempp, W.; Zeller, K., Multivariate Approximation Theory IV. Multivariate Approximation Theory IV, ISNM 90 (1989), Birkhäuser: Birkhäuser Basel), 15-24 · Zbl 0689.42011 |
| [3] | Björck, Å., Numerical Methods for Least Squares Problems (1996), SIAM: SIAM Philadelphia, PA, USA · Zbl 0847.65023 |
| [4] | Bungartz, H.-J.; Griebel, M., A note on the complexity of solving Poisson’s equation for spaces of bounded mixed derivatives, J. Complexity, 15, 167-199 (1999) · Zbl 0954.65078 |
| [5] | Bungartz, H.-J.; Griebel, M., Sparse grids, Acta Numer., 13, 147-269 (2004) |
| [6] | 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 |
| [7] | Cools, R.; Nuyens, D., Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces, Math. Comp., 75, 903-920 (2004) · Zbl 1094.65004 |
| [8] | Dick, J.; Kuo, F. Y.; Sloan, I. H., High-dimensional integration: the quasi-Monte Carlo way, Acta Numer., 22, 133-288 (2013) · Zbl 1296.65004 |
| [9] | Döhler, M.; Kunis, S.; Potts, D., Nonequispaced hyperbolic cross fast Fourier transform, SIAM J. Numer. Anal., 47, 4415-4428 (2010) · Zbl 1207.65168 |
| [10] | Feichtinger, H. G.; Gröchenig, K., Theory and practice of irregular sampling, (Benedetto, J.; Frazier, M., Wavelets: Mathematics and Applications (1993), CRC Press), 305-363 · Zbl 1090.94524 |
| [11] | Gradinaru, V., Fourier transform on sparse grids: code design and the time dependent Schrödinger equation, Computing, 80, 1-22 (2007) · Zbl 1117.65137 |
| [12] | Griebel, M.; Hamaekers, J., Fast discrete Fourier transform on generalized sparse grids, (Garcke, J.; Pflüger, D., Sparse Grids and Applications—Munich 2012. Sparse Grids and Applications—Munich 2012, Lect. Notes Comput. Sci. Eng., vol. 97 (2014), Springer International Publishing), 75-107 · Zbl 1316.65119 |
| [13] | Griebel, M.; Knapek, S., Optimized tensor-product approximation spaces, Constr. Approx., 16, 525-540 (2000) · Zbl 0969.65107 |
| [14] | Gröchenig, K., Reconstruction algorithms in irregular sampling, Math. Comp., 59, 181-194 (1992) · Zbl 0756.65159 |
| [15] | Hallatschek, K., Fouriertransformation auf dünnen Gittern mit hierarchischen Basen, Numer. Math., 63, 83-97 (1992) · Zbl 0762.65098 |
| [16] | Hassanieh, H.; Indyk, P.; Katabi, D.; Price, E., Nearly optimal sparse Fourier transform, (Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (2012), ACM), 563-578 · Zbl 1286.94046 |
| [17] | Hassanieh, H.; Indyk, P.; Katabi, D.; Price, E., Simple and practical algorithm for sparse Fourier transform, (Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (2012), SIAM), 1183-1194 · Zbl 1458.94097 |
| [18] | Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0729.15001 |
| [19] | Jiang, Y.; Xu, Y., Fast discrete algorithms for sparse Fourier expansions of high dimensional functions, J. Complexity, 26, 51-81 (2010) · Zbl 1184.65124 |
| [20] | 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 |
| [21] | Kämmerer, L., Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices, (Fasshauer, G. E.; Schumaker, L. L., Approximation Theory XIV: San Antonio 2013 (2014), Springer International Publishing), 255-271 · Zbl 1325.65189 |
| [22] | Kämmerer, L.; Kunis, S., On the stability of the hyperbolic cross discrete Fourier transform, Numer. Math., 117, 581-600 (2011) · Zbl 1213.65159 |
| [23] | Kämmerer, L.; Kunis, S.; Potts, D., Interpolation lattices for hyperbolic cross trigonometric polynomials, J. Complexity, 28, 76-92 (2012) · Zbl 1335.65105 |
| [24] | Knapek, S., Approximation und Kompression mit Tensorprodukt-Multiskalenräumen (2000), Universität Bonn, (dissertation) |
| [25] | Kühn, T.; Sickel, W.; Ullrich, T., Approximation numbers of Sobolev embeddings—sharp constants and tractability, J. Complexity, 30, 95-116 (2014) · Zbl 1334.47028 |
| [26] | Kunis, S., Nonequispaced fast Fourier transforms without oversampling, Proc. Appl. Math. Mech., 8, 10977-10978 (2008) · Zbl 1395.94225 |
| [27] | Li, D.; Hickernell, F. J., Trigonometric spectral collocation methods on lattices, (Cheng, S. Y.; Shu, C.-W.; Tang, T., Recent Advances in Scientific Computing and Partial Differential Equations. Recent Advances in Scientific Computing and Partial Differential Equations, Contemp. Math., vol. 330 (2003), AMS), 121-132 · Zbl 1036.65093 |
| [28] | Munthe-Kaas, H.; Sørevik, T., Multidimensional pseudo-spectral methods on lattice grids, Appl. Numer. Math., 62, 155-165 (2012) · Zbl 1237.65130 |
| [29] | Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems Volume II: Standard Information for Functionals. Tractability of Multivariate Problems Volume II: Standard Information for Functionals, EMS Tracts in Mathematics, vol. 12 (2010), Eur. Math. Society) · Zbl 1241.65025 |
| [30] | Potts, D.; Tasche, M., Numerical stability of nonequispaced fast Fourier transforms, J. Comput. Appl. Math., 222, 655-674 (2008) · Zbl 1210.65208 |
| [31] | 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 |
| [32] | Sloan, I. H.; Joe, S., (Lattice Methods for Multiple Integration. Lattice Methods for Multiple Integration, Oxford Science Publications (1994), The Clarendon Press, Oxford University Press: The Clarendon Press, Oxford University Press New York) · Zbl 0855.65013 |
| [33] | Sloan, I. H.; Reztsov, A. V., Component-by-component construction of good lattice rules, Math. Comp., 71, 263-273 (2002) · Zbl 0985.65018 |
| [34] | Sprengel, F., A class of function spaces and interpolation on sparse grids, Numer. Funct. Anal. Optim., 21, 273-293 (2000) · Zbl 0991.42014 |
| [35] | Temlyakov, V. N., Approximation of functions with bounded mixed derivative, Proc. Steklov Inst. Math. (1989), A translation of Trudy Mat. Inst. Steklov 178 (1986) · Zbl 0668.41024 |
| [36] | Volkmer, T., Taylor and rank-1 lattice based nonequispaced fast Fourier transform, (10th International Conference on Sampling Theory and Applications. 10th International Conference on Sampling Theory and Applications, (SampTA 2013) (2013), Bremen: Bremen Germany), 576-579 |
| [37] | Zenger, C., Sparse grids, (Parallel Algorithms for Partial Differential Equations (Kiel, 1990). Parallel Algorithms for Partial Differential Equations (Kiel, 1990), Notes Numer. Fluid Mech., vol. 31 (1991), Vieweg: Vieweg Braunschweig, Germany), 241-251 · Zbl 0763.65091 |
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.
