QMC designs: Optimal order Quasi Monte Carlo integration schemes on the sphere
HTML articles powered by AMS MathViewer
- by J. S. Brauchart, E. B. Saff, I. H. Sloan and R. S. Womersley PDF
- Math. Comp. 83 (2014), 2821-2851 Request permission
Abstract:
We study equal weight numerical integration, or Quasi Monte Carlo (QMC) rules, for functions in a Sobolev space $\mathbb {H}^s( \mathbb {S}^d)$ with smoothness parameter $s > d/2$ defined over the unit sphere $\mathbb {S}^d$ in $\mathbb {R}^{d+1}$. Focusing on $N$-point configurations that achieve optimal order QMC error bounds (as is the case for efficient spherical designs), we are led to introduce the concept of QMC designs: these are sequences of $N$-point configurations $X_N$ on $\mathbb {S}^d$ such that the worst-case error satisfies \begin{equation*} \sup _{\substack {f \in \mathbb {H}^s( \mathbb {S}^d ), \\ \| f \|_{\mathbb {H}^s} \leq 1}} \Bigg | \frac {1}{N} \sum _{\mathbf {x} \in X_N} f( \mathbf {x} ) - \int _{\mathbb {S}^d} f( \mathbf {x} ) \mathrm {d} \sigma _d( \mathbf {x} ) \Bigg | = \mathcal {O}\big ( N^{-s/d} \big ), \qquad N \to \infty , \end{equation*} with an implied constant that depends on the $\mathbb {H}^s( \mathbb {S}^d )$-norm, but is independent of $N$. Here $\sigma _d$ is the normalized surface measure on $\mathbb {S}^d$.
We provide methods for generation and numerical testing of QMC designs. An essential tool is an expression for the worst-case error in terms of a reproducing kernel for the space $\mathbb {H}^s( \mathbb {S}^d )$ with $s > d/2$. As a consequence of this and a recent result of Bondarenko et al. on the existence of spherical designs with appropriate number of points, we show that minimizers of the $N$-point energy for this kernel form a sequence of QMC designs for $\mathbb {H}^s( \mathbb {S}^d )$. Furthermore, without appealing to the Bondarenko et al. result, we prove that point sets that maximize the sum of suitable powers of the Euclidean distance between pairs of points form a sequence of QMC designs for $\mathbb {H}^s( \mathbb {S}^d )$ with $s$ in the interval ${(d/2,d/2+1)}$. For such spaces there exist reproducing kernels with simple closed forms that are useful for numerical testing of optimal order Quasi Monte Carlo integration.
Numerical experiments suggest that many familiar sequences of point sets on the sphere (equal area points, spiral points, minimal [Coulomb or logarithmic] energy points, and Fekete points) are QMC designs for appropriate values of $s$. For comparison purposes we show that configurations of random points that are independently and uniformly distributed on the sphere do not constitute QMC designs for any $s>d/2$.
If $(X_N)$ is a sequence of QMC designs for $\mathbb {H}^s( \mathbb {S}^d)$, we prove that it is also a sequence of QMC designs for $\mathbb {H}^{s’}( \mathbb {S}^d)$ for all $s’\in (d/2,s)$. This leads to the question of determining the supremum of such $s$ (here called the QMC strength of the sequence), for which we provide estimates based on computations for the aforementioned sequences.
References
- Digital Library of Mathematical Functions. 2010-05-07. National Institute of Standards and Technology from http://dlmf.nist.gov/
- C. Aistleitner, J. S. Brauchart, and J. Dick, Point sets on the sphere $\Bbb {S}^2$ with small spherical cap discrepancy, Discrete Comput. Geom. 48 (2012), no. 4, 990–1024. MR 3000572, DOI 10.1007/s00454-012-9451-3
- Clemens Amstler and Peter Zinterhof, Uniform distribution, discrepancy, and reproducing kernel Hilbert spaces, J. Complexity 17 (2001), no. 3, 497–515. MR 1851057, DOI 10.1006/jcom.2001.0580
- Diego Armentano, Carlos Beltrán, and Michael Shub, Minimizing the discrete logarithmic energy on the sphere: the role of random polynomials, Trans. Amer. Math. Soc. 363 (2011), no. 6, 2955–2965. MR 2775794, DOI 10.1090/S0002-9947-2011-05243-8
- E. Bannai and R. M. Damerell, Tight spherical designs. I, J. Math. Soc. Japan 31 (1979), no. 1, 199–207. MR 519045, DOI 10.2969/jmsj/03110199
- E. Bannai and R. M. Damerell, Tight spherical designs. II, J. London Math. Soc. (2) 21 (1980), no. 1, 13–30. MR 576179, DOI 10.1112/jlms/s2-21.1.13
- R. Bauer. Distribution of points on a sphere with application to star catalogs, J. Guidance Control Dynamics, 23(1):130–137, 2000.
- József Beck, Sums of distances between points on a sphere—an application of the theory of irregularities of distribution to discrete geometry, Mathematika 31 (1984), no. 1, 33–41. MR 762175, DOI 10.1112/S0025579300010639
- József Beck and William W. L. Chen, Irregularities of distribution, Cambridge Tracts in Mathematics, vol. 89, Cambridge University Press, Cambridge, 1987. MR 903025, DOI 10.1017/CBO9780511565984
- Göran Björck, Distributions of positive mass, which maximize a certain generalized energy integral, Ark. Mat. 3 (1956), 255–269. MR 78470, DOI 10.1007/BF02589412
- Andriy Bondarenko, Danylo Radchenko, and Maryna Viazovska, Optimal asymptotic bounds for spherical designs, Ann. of Math. (2) 178 (2013), no. 2, 443–452. MR 3071504, DOI 10.4007/annals.2013.178.2.2
- J. Bourgain and J. Lindenstrauss, Distribution of points on spheres and approximation by zonotopes, Israel J. Math. 64 (1988), no. 1, 25–31. MR 981745, DOI 10.1007/BF02767366
- L. Brandolini, C. Choirat, L. Colzani, G. Gigante, R. Seri, and G. Travaglini, Quadrature rules and distribution of points on manifolds, Ann. Sc. Norm. Super. Pisa Cl. Sci. (to appear), arXiv:1012.5409v1 [math.NT], Dec 2010.
- Johann S. Brauchart and Josef Dick, Quasi-Monte Carlo rules for numerical integration over the unit sphere $\Bbb S^2$, Numer. Math. 121 (2012), no. 3, 473–502. MR 2929076, DOI 10.1007/s00211-011-0444-6
- Johann S. Brauchart and Josef Dick, A simple proof of Stolarsky’s invariance principle, Proc. Amer. Math. Soc. 141 (2013), no. 6, 2085–2096. MR 3034434, DOI 10.1090/S0002-9939-2013-11490-5
- Johann S. Brauchart and Kerstin Hesse, Numerical integration over spheres of arbitrary dimension, Constr. Approx. 25 (2007), no. 1, 41–71. MR 2263736, DOI 10.1007/s00365-006-0629-4
- J. S. Brauchart and R. S. Womersley, Weighted QMC designs: Numerical integration over the unit sphere, $\mathbb {L}_2$-discrepancy and sum of distances. In preparation.
- Xiaojun Chen, Andreas Frommer, and Bruno Lang, Computational existence proofs for spherical $t$-designs, Numer. Math. 117 (2011), no. 2, 289–305. MR 2754852, DOI 10.1007/s00211-010-0332-5
- Jianjun Cui and Willi Freeden, Equidistribution on the sphere, SIAM J. Sci. Comput. 18 (1997), no. 2, 595–609. MR 1433797, DOI 10.1137/S1064827595281344
- P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), no. 3, 363–388. MR 485471, DOI 10.1007/bf03187604
- Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
- Kerstin Hesse, A lower bound for the worst-case cubature error on spheres of arbitrary dimension, Numer. Math. 103 (2006), no. 3, 413–433. MR 2221056, DOI 10.1007/s00211-006-0686-x
- K. Hesse, H. N. Mhaskar, and I. H. Sloan, Quadrature in Besov spaces on the Euclidean sphere, J. Complexity 23 (2007), no. 4-6, 528–552. MR 2372012, DOI 10.1016/j.jco.2006.10.004
- Kerstin Hesse and Ian H. Sloan, Optimal lower bounds for cubature error on the sphere $S^2$, J. Complexity 21 (2005), no. 6, 790–803. MR 2182445, DOI 10.1016/j.jco.2005.07.004
- Kerstin Hesse and Ian H. Sloan, Worst-case errors in a Sobolev space setting for cubature over the sphere $S^2$, Bull. Austral. Math. Soc. 71 (2005), no. 1, 81–105. MR 2127668, DOI 10.1017/S0004972700038041
- Kerstin Hesse and Ian H. Sloan, Cubature over the sphere $S^2$ in Sobolev spaces of arbitrary order, J. Approx. Theory 141 (2006), no. 2, 118–133. MR 2252093, DOI 10.1016/j.jat.2006.01.004
- Brad J. C. Baxter and Simon Hubbert, Radial basis functions for the sphere, Recent progress in multivariate approximation (Witten-Bommerholz, 2000) Internat. Ser. Numer. Math., vol. 137, Birkhäuser, Basel, 2001, pp. 33–47. MR 1877496
- J. Korevaar and J. L. H. Meyers, Spherical Faraday cage for the case of equal point charges and Chebyshev-type quadrature on the sphere, Integral Transform. Spec. Funct. 1 (1993), no. 2, 105–117. MR 1421438, DOI 10.1080/10652469308819013
- A. B. J. Kuijlaars and E. B. Saff, Asymptotics for minimal discrete energy on the sphere, Trans. Amer. Math. Soc. 350 (1998), no. 2, 523–538. MR 1458327, DOI 10.1090/S0002-9947-98-02119-9
- Paul Leopardi, Diameter bounds for equal area partitions of the unit sphere, Electron. Trans. Numer. Anal. 35 (2009), 1–16. MR 2582801
- Claus Müller, Spherical harmonics, Lecture Notes in Mathematics, vol. 17, Springer-Verlag, Berlin-New York, 1966. MR 0199449, DOI 10.1007/BFb0094775
- E. A. Rakhmanov, E. B. Saff, and Y. M. Zhou, Minimal discrete energy on the sphere, Math. Res. Lett. 1 (1994), no. 6, 647–662. MR 1306011, DOI 10.4310/MRL.1994.v1.n6.a3
- Robert J. Renka, Multivariate interpolation of large sets of scattered data, ACM Trans. Math. Software 14 (1988), no. 2, 139–148. MR 946761, DOI 10.1145/45054.45055
- I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96–108. MR 5922, DOI 10.1215/S0012-7094-42-00908-6
- P. D. Seymour and Thomas Zaslavsky, Averaging sets: a generalization of mean values and spherical designs, Adv. in Math. 52 (1984), no. 3, 213–240. MR 744857, DOI 10.1016/0001-8708(84)90022-7
- Ian H. Sloan and Robert S. Womersley, Extremal systems of points and numerical integration on the sphere, Adv. Comput. Math. 21 (2004), no. 1-2, 107–125. MR 2065291, DOI 10.1023/B:ACOM.0000016428.25905.da
- Ian H. Sloan and Robert S. Womersley, A variational characterisation of spherical designs, J. Approx. Theory 159 (2009), no. 2, 308–318. MR 2562747, DOI 10.1016/j.jat.2009.02.014
- Kenneth B. Stolarsky, Sums of distances between points on a sphere. II, Proc. Amer. Math. Soc. 41 (1973), 575–582. MR 333995, DOI 10.1090/S0002-9939-1973-0333995-9
- N. Th. Varopoulos, Small time Gaussian estimates of heat diffusion kernels. II. The theory of large deviations, J. Funct. Anal. 93 (1990), no. 1, 1–33. MR 1070036, DOI 10.1016/0022-1236(90)90136-9
- Gerold Wagner, On means of distances on the surface of a sphere. II. Upper bounds, Pacific J. Math. 154 (1992), no. 2, 381–396. MR 1159518, DOI 10.2140/pjm.1992.154.381
- R. S. Womersley, Numerical integration, approximation and point sets on the sphere. [http://www.maths.unsw.edu.au/~rsw/Sphere/; accessed August-2012]
Additional Information
- J. S. Brauchart
- Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, NSW, 2052, Australia
- MR Author ID: 730033
- Email: j.brauchart@unsw.edu.au
- E. B. Saff
- Affiliation: Center for Constructive Approximation, Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240
- MR Author ID: 152845
- Email: edward.b.saff@vanderbilt.edu
- I. H. Sloan
- Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, NSW, 2052, Australia
- MR Author ID: 163675
- ORCID: 0000-0003-3769-0538
- Email: i.sloan@unsw.edu.au
- R. S. Womersley
- Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, NSW, 2052, Australia
- Email: r.womersley@unsw.edu.au
- Received by editor(s): August 15, 2012
- Received by editor(s) in revised form: February 26, 2013
- Published electronically: April 21, 2014
- Additional Notes: This research was supported by an Australian Research Council Discovery Project. The research of the second author was also supported by U.S. National Science Foundation grant DMS-1109266.
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 83 (2014), 2821-2851
- MSC (2010): Primary 65D30, 65D32; Secondary 11K38, 41A55
- DOI: https://doi.org/10.1090/S0025-5718-2014-02839-1
- MathSciNet review: 3246811