Fully symmetric kernel quadrature. (English) Zbl 1385.65024
Summary: Kernel quadratures and other kernel-based approximation methods typically suffer from prohibitive cubic time and quadratic space complexity in the number of function evaluations. The problem arises because a system of linear equations needs to be solved. In this article we show that the weights of a kernel quadrature rule can be computed efficiently and exactly for up to tens of millions of nodes if the kernel, integration domain, and measure are fully symmetric and the node set is a union of fully symmetric sets. This is based on the observations that in such a setting there are only as many distinct weights as there are fully symmetric sets and that these weights can be solved from a linear system of equations constructed out of row sums of certain submatrices of the full kernel matrix. We present several numerical examples that show feasibility, both for a large number of nodes and in high dimensions, of the developed fully symmetric kernel quadrature rules. Most prominent of the fully symmetric kernel quadrature rules we propose are those that use sparse grids.
MSC:
| 65D32 | Numerical quadrature and cubature formulas |
| 41A55 | Approximate quadratures |
| 46E22 | Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) |
Keywords:
numerical integration; kernel quadrature; Bayesian quadrature; reproducing kernel Hilbert spaces; fully symmetric sets; sparse grids; numerical examplesReferences:
| [1] | N. Aronszajn, {\it Theory of reproducing kernels}, Trans. Amer. Math. Soc., 68 (1950), pp. 337-404. · Zbl 0037.20701 |
| [2] | A. Berlinet and C. Thomas-Agnan, {\it Reproducing Kernel Hilbert Spaces in Probability and Statistics}, Springer, 2004. · Zbl 1145.62002 |
| [3] | A. Yu. Bezhaev, {\it Cubature formulae on scattered meshes}, Soviet J. Numer. Anal. Math. Modelling, 6 (1991), pp. 95-106. · Zbl 0816.65008 |
| [4] | F.-X. Briol, C. J. Oates, J. Cockayne, W. Y. Chen, and M. Girolami, {\it On the sampling problem for kernel quadrature}, in 34th International Conference on Machine Learning, Proceedings of Machine Learning Research 70, 2017, pp. 586-595. |
| [5] | F.-X. Briol, C. J. Oates, M. Girolami, and M. A. Osborne, {\it Frank-Wolfe Bayesian quadrature: Probabilistic integration with theoretical guarantees}, in Advances in Neural Information Processing Systems, Vol. 25, 2015, pp. 1162-1170. |
| [6] | F.-X. Briol, C. J. Oates, M. Girolami, M. A. Osborne, and D. Sejdinovic, {\it Probabilistic Integration: A Role for Statisticians in Numerical Analysis?}, preprint, , 2016. |
| [7] | H.-J. Bungartz and M. Griebel, {\it Sparse grids}, Acta Numer., 13 (2004), pp. 147-269. · Zbl 1118.65388 |
| [8] | R. E. Caflisch, {\it Monte Carlo and quasi-Monte Carlo methods}, Acta Numer., 7 (1998), pp. 1-49. · Zbl 0949.65003 |
| [9] | J. Cockayne, C. Oates, T. Sullivan, and M. Girolami, {\it Bayesian Probabilistic Numerical Methods}, preprint, , 2017. · Zbl 1451.65179 |
| [10] | T. D. Cook and M. K. Clayton, {\it Sequential Bayesian Quadrature}, tech. report, Department of Statistics, University of Wisconsin, 1998. |
| [11] | R. Cools, {\it Constructing cubature formulae: The science behind the art}, Acta Numer., 6 (1997), pp. 1-54. · Zbl 0887.65028 |
| [12] | P. J. Davis and P. Rabinowitz, {\it Methods of Numerical Integration}, 2nd ed., Academic Press, 1984. · Zbl 0537.65020 |
| [13] | C. de Boor and A. Ron, {\it On multivariate polynomial interpolation}, Constr. Approx., 6 (1990), pp. 287-302. · Zbl 0719.41006 |
| [14] | P. Diaconis, {\it Bayesian numerical analysis}, in Statistical Decision Theory and Related Topics IV, Vol. 1, Springer-Verlag, New York, 1988, pp. 163-175. · Zbl 0671.65117 |
| [15] | Z. Dong, E. H. Georgoulis, J. Levesley, and F. Usta, {\it Fast Multilevel Sparse Gaussian Kernels for High-Dimensional Approximation and Integration}, preprint, , 2015. |
| [16] | G. E. Fasshauer and J. G. Zhang, {\it On choosing “optimal” shape parameters for RBF approximation}, Numer. Algorithms, 45 (2007), pp. 345-368. · Zbl 1127.65009 |
| [17] | J. Garcke, {\it A dimension adaptive sparse grid combination technique for machine learning}, ANZIAM J., 48 (2006), pp. 725-740. · Zbl 1334.68183 |
| [18] | A. Genz, {\it Fully symmetric interpolatory rules for multiple integrals}, SIAM J. Numer. Anal., 23 (1986), pp. 1273-1283, . · Zbl 0613.65021 |
| [19] | A. Genz and B. D. Keister, {\it Fully symmetric interpolatory rules for multiple integrals over infinite regions with Gaussian weight}, J. Comput. Appl. Math., 71 (1996), pp. 299-309. · Zbl 0856.65011 |
| [20] | A. Genz and J. Monahan, {\it Stochastic integration rules for infinite regions}, SIAM J. Sci. Comput., 19 (1998), pp. 426-439, . · Zbl 0916.65019 |
| [21] | A. Genz and J. Monahan, {\it A stochastic algorithm for high-dimensional integrals over unbounded regions with Gaussian weight}, J. Comput. Appl. Math., 112 (1999), pp. 71-81. · Zbl 0943.65034 |
| [22] | E. H. Georgoulis, J. Levesley, and F. Subhan, {\it Multilevel sparse kernel-based interpolation}, SIAM J. Sci. Comput., 35 (2013), pp. A815-A831, . · Zbl 1266.65051 |
| [23] | T. Gerstner and M. Griebel, {\it Numerical integration using sparse grids}, Numer. Algorithms, 18 (1998), pp. 209-232. · Zbl 0921.65022 |
| [24] | T. Gunter, M. A. Osborne, R. Garnett, P. Hennig, and S. J. Roberts, {\it Sampling for inference in probabilistic models with fast Bayesian quadrature}, in Advances in Neural Information Processing Systems, Vol. 24, 2014, pp. 2789-2797. |
| [25] | P. Hennig, M. A. Osborne, and M. Girolami, {\it Probabilistic numerics and uncertainty in computations}, Proc. Roy. Soc. London A Math. Phys. Engrg. Sci., 471 (2015), 20150142. · Zbl 1372.65010 |
| [26] | M. Holtz, {\it Sparse Grid Quadrature in High Dimensions with Applications in Finance and Insurance}, Lecture Notes in Comput. Sci. Engrg. 77, Springer, 2011. · Zbl 1221.65080 |
| [27] | F. Huszár and D. Duvenaud, {\it Optimally-weighted herding is Bayesian quadrature}, in 28th Conference on Uncertainty in Artificial Intelligence, 2012, pp. 377-385. |
| [28] | M. Kanagawa, B. K. Sriperumbudur, and K. Fukumizu, {\it Convergence guarantees for kernel-based quadrature rules in misspecified settings}, in Advances in Neural Information Processing Systems, Vol. 29, 2016, pp. 3288-3296. |
| [29] | M. Kanagawa, B. K. Sriperumbudur, and K. Fukumizu, {\it Convergence Analysis of Deterministic Kernel-Based Quadrature Rules in Misspecified Settings}, preprint, , 2017. · Zbl 07161204 |
| [30] | T. Karvonen and S. Särkkä, {\it Classical quadrature rules via Gaussian processes}, in 27th IEEE International Workshop on Machine Learning for Signal Processing, 2017. |
| [31] | A. Klimke and B. Wohlmuth, {\it Algorithm 847: Spinterp: Piecewise multilinear hierarchical sparse grid interpolation in MATLAB}, ACM Trans. Math. Software, 31 (2005), pp. 561-579. · Zbl 1136.65308 |
| [32] | F. M. Larkin, {\it Optimal approximation in Hilbert spaces with reproducing kernel functions}, Math. Comp., 24 (1970), pp. 911-921. · Zbl 0225.65025 |
| [33] | F. M. Larkin, {\it Gaussian measure in Hilbert space and applications in numerical analysis}, Rocky Mountain J. Math., 2 (1972), pp. 379-422. · Zbl 0258.65058 |
| [34] | J. Lu and D. L. Darmofal, {\it Higher-dimensional integration with Gaussian weight for applications in probabilistic design}, SIAM J. Sci. Comput., 26 (2004), pp. 613-624, . · Zbl 1075.65014 |
| [35] | J. N. Lyness, {\it Symmetric integration rules for hypercubes I. Error coefficients}, Math. Comp., 19 (1965), pp. 260-276. · Zbl 0142.12301 |
| [36] | J. McNamee and F. Stenger, {\it Construction of fully symmetric numerical integration formulas}, Numer. Math., 10 (1967), pp. 327-344. · Zbl 0155.21702 |
| [37] | T. Minka, {\it Deriving Quadrature Rules from Gaussian Processes}, tech. report, Statistics Department, Carnegie Mellon University, 2000. |
| [38] | K. Muandet, K. Fukumizu, B. Sriperumbudur, and B. Schölkopf, {\it Kernel mean embedding of distributions: A review and beyond}, Found. Trends Mach. Learning, 10 (2017), pp. 1-141. |
| [39] | A. Narayan and D. Xiu, {\it Stochastic collocation methods on unstructured grids in high dimensions via interpolation}, SIAM J. Sci. Comput., 34 (2012), pp. A1729-A1752, . · Zbl 1246.65029 |
| [40] | S. Ninomiya and S. Tezuka, {\it Toward real-time pricing of complex financial derivatives}, Appl. Math. Finance, 3 (1996), pp. 1-20. · Zbl 1097.91530 |
| [41] | E. Novak and K. Ritter, {\it High dimensional integration of smooth functions over cubes}, Numer. Math., 75 (1996), pp. 79-97. · Zbl 0883.65016 |
| [42] | E. Novak and K. Ritter, {\it The curse of dimension and a universal method for numerical integration}, in Multivariate Approximation and Splines, Birkhäuser, Basel, 1997, pp. 177-187. · Zbl 0889.65016 |
| [43] | E. Novak and K. Ritter, {\it Simple cubature formulas with high polynomial exactness}, Constr. Approx., 15 (1999), pp. 499-522. · Zbl 0942.41018 |
| [44] | E. Novak, K. Ritter, R. Schmitt, and A. Steinbauer, {\it On an interpolatory method for high dimensional integration}, J. Comput. Appl. Math., 112 (1999), pp. 215-228. · Zbl 0958.65030 |
| [45] | E. Novak and H. Woźniakowski, {\it Tractability of Multivariate Problems, Volume II: Standard Information for Functionals}, EMS Tracts Math. 12, European Mathematical Society, 2010. · Zbl 1241.65025 |
| [46] | J. Oettershagen, {\it Construction of Optimal Cubature Algorithms with Applications to Econometrics and Uncertainty Quantification}, Ph.D. thesis, Institut für Numerische Simulation, Universität Bonn, 2017. · Zbl 1378.90001 |
| [47] | A. O’Hagan, {\it Curve fitting and optimal design for prediction}, J. Roy. Statist. Soc. Ser. B, 40 (1978), pp. 1-42. · Zbl 0374.62070 |
| [48] | A. O’Hagan, {\it Bayes-Hermite quadrature}, J. Statist. Plann. Inference, 29 (1991), pp. 245-260. · Zbl 0829.65024 |
| [49] | A. O’Hagan, {\it Some Bayesian numerical analysis}, Bayesian Statist., 4 (1992), pp. 345-363. |
| [50] | J. Prüher and O. Straka, {\it Gaussian process quadrature moment transform}, IEEE Trans. Automat. Control, 2017, . |
| [51] | J. Prüher, F. Tronarp, T. Karvonen, S. Särkkä, and O. Straka, {\it Student-t process quadratures for filtering of non-linear systems with heavy-tailed noise}, in 20th International Conference on Information Fusion, 2017. |
| [52] | C. E. Rasmussen and Z. Ghahramani, {\it Bayesian Monte Carlo}, in Advances in Neural Information Processing Systems, Vol. 15, 2002, pp. 505-512. |
| [53] | C. E. Rasmussen and C. K. I. Williams, {\it Gaussian Processes for Machine Learning}, Adaptive Computation and Machine Learning, MIT Press, 2006. · Zbl 1177.68165 |
| [54] | S. Rippa, {\it An algorithm for selecting a good value for the parameter c in radial basis function interpolation}, Adv. Comput. Math., 11 (1999), pp. 193-210. · Zbl 0943.65017 |
| [55] | K. Ritter, {\it Average-Case Analysis of Numerical Problems}, Lecture Notes in Math. 1733, Springer, 2000. · Zbl 0949.65146 |
| [56] | S. A. Smolyak, {\it Quadrature and interpolation formulas for tensor products of certain classes of functions}, Dokl. Akad. Nauk SSSR, 4 (1963), pp. 240-243. · Zbl 0202.39901 |
| [57] | A. Sommariva and M. Vianello, {\it Numerical cubature on scattered data by radial basis functions}, Computing, 76 (2006), pp. 295-310. · Zbl 1091.65026 |
| [58] | S. Särkkä, J. Hartikainen, L. Svensson, and F. Sandblom, {\it On the relation between Gaussian process quadratures and sigma-point methods}, J. Adv. Inform. Fusion, 11 (2016), pp. 31-46. |
| [59] | F. Usta and J. Levesley, {\it Multilevel quasi-interpolation on a sparse grid with the Gaussian}, Numer. Algorithms, . · Zbl 1392.65073 |
| [60] | H. Wendland, {\it Scattered Data Approximation}, Cambridge Monogr. Appl. Comput. Math. 17, Cambridge University Press, 2010. · Zbl 1185.65022 |
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.
