Top

Published in:

2024 | OriginalPaper | Chapter

Comparison of Two Search Criteria for Lattice-Based Kernel Approximation

Authors : Frances Y. Kuo, Weiwen Mo, Dirk Nuyens, Ian H. Sloan, Abirami Srikumar

Published in: Monte Carlo and Quasi-Monte Carlo Methods

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The kernel interpolant in a reproducing kernel Hilbert space is optimal in the worst-case sense among all approximations of a function using the same set of function values. In this paper, we compare two search criteria to construct lattice point sets for use in lattice-based kernel approximation. The first candidate, \({\mathcal {P}}_n^*\), is based on the power function that appears in machine learning literature. The second, \({\mathcal {S}}_n^*\), is a search criterion used for generating lattices for approximation using truncated Fourier series. We find that the empirical difference in error between the lattices constructed using \({\mathcal {P}}_n^*\) and \({\mathcal {S}}_n^*\) is marginal. The criterion \({\mathcal {S}}_n^*\) is preferred as it is computationally more efficient and has a bound with a superior convergence rate.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Sequential Estimation Using Hierarchically Stratified Domains with Latin Hypercube Sampling

next chapter A-Posteriori QMC-FEM Error Estimation for Bayesian Inversion and Optimal Control with Entropic Risk Measure

Belhadji, A., Bardenet, R., Chainais., P.: Kernel interpolation with continuous volume sampling. In: Proceedings of the 37th International Conference on Machine Learning (ICML’20). JMLR.org, Article 68, pp. 725–735 (2020)

Bartel, F., Kämmerer, L., Potts, D., Ullrich, T.: On the reconstruction of functions from values at subsampled quadrature points. Math. Comp. 93, 785–809 (2024)

Byrenheid, G., Kämmerer, L., Ullrich, T., Volkmer, T.: Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness. Numer. Math. 136, 993–1034 (2017)MathSciNetCrossRef

Cools, R., Kuo, F.Y., Nuyens, D., Sloan, I.H.: Lattice algorithms for multivariate approximation in periodic spaces with general weights. In: Brenner, S.C., Shparlinski, I., Shu, C.-W., Szyld, D. (eds.) Celebrating 75 Years of Mathematics of Computation, Contemporary Mathematics, vol. 754, pp. 93–113. AMS (2020)

Cools, R., Kuo, F.Y., Nuyens, D., Sloan, I.H.: Fast CBC construction of lattice algorithms for multivariate approximation with POD and SPOD weights. Math. Comp. 90, 787–812 (2021)MathSciNetCrossRef

Cools, R., Nuyens, D.: A Belgian view on lattice rules. In: Keller, A., Heinrich, S., Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2006, pp. 3–21. Springer (2008)

De Marchi, S., Schaback, R., Wendland, H.: Near-optimal data-independent point locations for radial basis function interpolation. Adv. Comput. Math. 23, 317–330 (2005)MathSciNetCrossRef

Dick, J., Kritzer, P., Kuo. F.Y., Sloan, I.H.: Lattice-Nystrom method for Fredholm integral equations of the second kind with convolution type kernels. J. Complexity 23, 752 – 772 (2007)

Dick, J., Kuo, F.Y., Sloan, I.H.: High-dimensional integration: the Quasi-Monte Carlo way. Acta Numer. 22, 133–288 (2013)MathSciNetCrossRef

10.

Dolbeault, M., Krieg, D., Ullrich, M.: A sharp upper bound for sampling numbers in \(L_2\). Appl. Comput. Harmon. Anal. 63, 113–134 (2023)MathSciNetCrossRef

11.

Gross, C., Iwen, M.A., Kämmerer, L., Volkmer, T.: A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size. Adv. Comput. Math. 47, 86 (2021)MathSciNetCrossRef

12.

Kaarnioja, V., Kazashi, Y., Kuo, F.Y., Nobile, F., Sloan, I.H.: Fast approximation by periodic kernel-based lattice-point interpolation with application in uncertainty quantification. Numer. Math. 150, 33–77 (2022)MathSciNetCrossRef

13.

Kämmerer, L., Volkmer, T.: Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices. J. Approx. Theory 246, 1–27 (2019)MathSciNetCrossRef

14.

Krieg, D., Pozharska, K., Ullrich, M., Ullrich, T.: Sampling recovery in \(L_2\) and other norms (2023). https://doi.org/10.48550/arXiv.2305.07539

15.

Krieg, D., Ullrich, M.: Function values are enough for \(L_2\)-approximation: Part II. J. Complexity 66, 101569 (2021)CrossRef

16.

Kuo, F.Y., Mo, W., Nuyens, D.: Constructing embedded lattice-based algorithms for multivariate function approximation with a composite number of points. Appeared online in Constr. Approx. (2024). https://doi.org/10.1007/s00365-024-09688-y

17.

Kuo, F.Y., Sloan, I.H., Woźniakowski, H.: Lattice rules for multivariate approximation in the worst case setting. In: Niederreiter, H., Talay, D. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2004, pp. 289–330. Springer (2006)

18.

L’Ecuyer, P., Munger, D.: On figures of merit for randomly shifted lattice rules. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 133–159. Springer (2012)

19.

Nuyens, D.: The construction of good lattice rules and polynomial lattice rules. In: Kritzer, P., Niederreiter, H., Pillichshammer, F., Winterhof, A. (eds.) Uniform Distribution and Quasi-Monte Carlo Methods. Radon Series on Computational and Applied Mathematics, vol. 15, pp. 223–256. De Gruyter (2014)

20.

Nuyens, D., Cools, R.: Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comp. 75, 903–920 (2006)MathSciNetCrossRef

21.

Nuyens, D., Cools, R.: Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points. J. Complexity 22, 4–28 (2006)MathSciNetCrossRef

22.

Novak, E., Sloan, I.H., Woźniakowski, H.: Tractability of approximation for weighted Korobov spaces on classical and quantum computers. Found. Comput. Math. 4, 121–156 (2004)MathSciNetCrossRef

23.

Olver, F.W.J., et al.: NIST Digital Library of Mathematical Functions. http://dlmf.nist.gov/ (2022). Accessed 07 December 2022

24.

Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Oxford University Press, Oxford (1994)CrossRef

25.

Schaback, R.: Error estimates and condition numbers for radial basis function interpolation. Adv. Comput. Math. 3, 251–264 (1995)MathSciNetCrossRef

26.

Schaback, R., Wendland, H.: Kernel techniques: from machine learning to meshless methods. Acta Numer. 15, 543–639 (2006)MathSciNetCrossRef

27.

Wu, Z.M., Schaback, R.: Local error estimates for radial basis function interpolation of scattered data. IMA J. Numer. Anal. 13, 13–27 (1993)MathSciNetCrossRef

28.

Zeng, X.Y., Kritzer, P., Hickernell, F.J.: Spline methods using integration lattices and digital nets. Constr. Approx. 30, 529–555 (2009)MathSciNetCrossRef

29.

Zeng, X.Y., Leung, K.T., Hickernell, F.J.: Error analysis of splines for periodic problems using lattice designs. In: Niederreiter, H., Talay, D. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2004, pp. 501–514. Springer (2006)

Title: Comparison of Two Search Criteria for Lattice-Based Kernel Approximation
Authors: Frances Y. Kuo
Weiwen Mo
Dirk Nuyens
Ian H. Sloan
Abirami Srikumar
Publisher: Springer International Publishing
Book: Monte Carlo and Quasi-Monte Carlo Methods
Print ISBN: 978-3-031-59761-9

Electronic ISBN: 978-3-031-59762-6

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-3-031-59762-6_20

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"