PaperlayerView exact revision on arXiv

Source-linked AI summary

QMC designs: optimal order Quasi Monte Carlo Integration schemes on the sphere

Johann S. Brauchart, Edward B. Saff, Ian H. Sloan, Rob S. Womersley

arXiv:1208.3267v1math.NAcs.NA

TL;DR

Equal-weight integration on the sphere calls for point sequences with optimal-order Sobolev worst-case error. The paper defines QMC designs and proves construction results using kernel-energy minimizers and generalized-distance maximizers. It also proves that QMC-design status carries over to lower Sobolev smoothness.

  • Problem

    The paper seeks point sequences whose equal-weight integration rules achieve optimal-order worst-case error for Sobolev functions on the sphere.

    Source: §1 · pp. 2–3

  • Method

    It defines QMC designs and proves sufficient construction results based on reproducing-kernel energy minimization and, over a restricted smoothness interval, generalized-distance maximization.

    Source: §1 · pp. 2, 4

  • Results

    Kernel-energy minimizers form QMC-design sequences for s>d/2, while generalized-distance maximizers do so for d/2<s<d/2+1.

    Source: §1 · p. 4

  • Takeaways & Limitations

    QMC-design status at smoothness s extends to every s′ with d/2<s′≤s.

    Source: §1 · p. 3

    Asymptotic uniformity alone does not ensure a useful quadrature rate: convergence can be arbitrarily slow.

    Source: Uniform distribution · p. 15

Abstract

from arXiv · show

We study equal weight numerical integration, or Quasi Monte Carlo (QMC) rules, for functions in a Sobolev space $H^s(S^d)$ with smoothness parameter $s>d/2$ defined over the unit sphere $S^d$ in $R^{d+1}$. Focusing on $N$-point sets 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 node sets $X_N$ on $S^d$ such that the worst-case error of the corresponding QMC rules satisfy a bound of order $O(N^{-s/d})$ as $N\to\infty$ with an implied constant that depends on the $H^s(S^d)$-norm. We provide methods for generation and numerical testing of QMC designs. As a consequence of 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 the reproducing kernel for $H^s(S^d)$, $s>d/2$, form a sequence of QMC designs for $H^s(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 $H^s(S^d)$ with $s\in(d/2,d/2+1)$. Numerical experiments suggest that many familiar sequences of point sets on the sphere (equal area, spiral, minimal [Coulomb or log.] energy, and Fekete points) are QMC designs for appropriate values of $s$. For comparison purposes we show that sets 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 $H^s(S^d)$, we prove that it is also a sequence of QMC designs for $\mathbb{H}^{s'}(S^d)$ for all $s'\in(d/2,s)$. This leads to the question of determining the supremum of such $s$, for which we provide estimates based on computations for the aforementioned sequences.

1. Introduction

The paper defines QMC designs as point-set sequences that provide optimal-order equal-weight integration for Sobolev functions on the sphere. It establishes theoretical construction criteria and examines how familiar point sets perform.

1. Introduction

  • QMC designs provide optimal-order equal-weight integration for Sobolev spaces on the sphere.The definition concerns sequences of point sets and the worst-case error of their QMC rules.Source: §1 · pp. 2–3
  • A QMC-design sequence for H^s(S^d) is also one for every H^s′(S^d) with d/2<s′≤s.This follows from a result attributed to Brandolini et al. [13].Source: §1 · p. 3
  • Minimizers of the reproducing-kernel energy form QMC-design sequences for the corresponding Sobolev space.The result applies for s>d/2.Source: §1 · p. 4
  • For d/2<s<d/2+1, maximizing suitable sums of pairwise Euclidean distances yields QMC-design sequences.The result uses a reproducing kernel of the form C − |x − y|^(2s−d), for sufficiently large C.Source: §1 · p. 4
  • A kernel-truncation criterion also suffices for QMC-design status when the point configurations satisfy Property R.The criterion controls the suppressed kernel tail under the stated regularity condition.Source: §1 · p. 4
  • Numerical evidence suggests equal-area, spiral, Coulomb- or logarithmic-energy, and Fekete sequences are QMC designs on S2 up to sequence-dependent smoothness thresholds.The paper reports conjectured threshold values for some sequences.Source: §1 · p. 4
  • Low-discrepancy sequences on the sphere have almost optimal worst-case-error order for d/2<s<(d+1)/2, apart from a power of log N.The passage notes that explicit constructions of such spherical configurations were not known to the authors.Source: §1 · pp. 4–5

2. Background

The background reviews spherical designs and the spherical-harmonic framework, then introduces Sobolev spaces and their reproducing kernels on the sphere.

2.1. Spherical designs.

  • A spherical t-design is a finite node set whose equal-weight rule integrates exactly every polynomial of degree at most t; such designs exist with N at least c_d t^d points.The cited existence result gives c_d depending only on d; earlier lower bounds of order t^d are attained only for a few small t values.Source: §2.1 · p. 5

2.2. Spherical harmonics.

  • Spherical harmonics form a complete orthonormal system for L2(S^d), and spherical polynomials of degree at most t span harmonics through degree t.The degree-ℓ harmonics are homogeneous harmonic polynomials in d+1 variables restricted to S^d.Source: §2.2 · p. 6

2.3. Sobolev spaces.

  • For s > d/2, H^s(S^d) is nested inside H^s′(S^d) when s′ < s, and embeds into C^k(S^d) when s > k + d/2.Equivalent Sobolev norms may be used; changing the norm changes the QMC-design constant, not the definition.Source: §2.3 · p. 7

2.4. Sobolev spaces as reproducing kernel Hilbert spaces.

  • Because point evaluation is bounded for s > d/2, H^s(S^d) has a reproducing kernel K^(s) satisfying (f, K^(s)(·, x)) = f(x).The kernel is zonal, depending only on x·y; the paper also identifies a canonical kernel for H^s(S^d).Source: §2.4 · pp. 7–8

3. Numerical integration and worst-case error

The section characterizes equal-weight integration error through worst-case error and reproducing kernels. It connects kernel energy minimization and truncated-kernel tests to QMC-design guarantees.

3.1. Worst-case error.

  • Worst-case error bounds the integration error for any f in the function space by the error times the function's norm.For reproducing kernel Hilbert spaces, the reproducing property gives a computable expression for worst-case error when the integration functional is bounded.Source: §3.1 · p. 8, §3.2 · pp. 8–9

3.3. Worst-case error in Hs(Sd).

  • The squared worst-case error in H^s(S^d) equals the normalized K^(s)-energy of the node set, yielding a computational expression when the kernel is available in closed form.This identity also links the RKHS error calculation to the corresponding kernel energy functional.Source: §3.3 · p. 10
  • Minimizers of the N-point energy for the reproducing kernel of H^s(S^d) form a sequence of QMC designs under the theorem's assumptions.The theorem supplies a constant independent of N for the error bound.Source: §3.3 · p. 10
  • For a QMC-design sequence in H^s′(S^d), with d/2 < s′ < s, the H^s worst-case error is bounded between rates O(N^-s/d) and O(N^-s′/d).The constants depend on the Sobolev norms but not on N.Source: §3.3 · p. 10

3.4. Truncations of the Laplace-Fourier series.

  • For sequences satisfying Property R, Theorem 15 characterizes QMC designs through a condition on the truncated kernel at degrees t ≍ N^1/d.Property R bounds the number of nodes in caps of radius on the order of N^-1/d, uniformly in N and cap location.Source: §3.4 · p. 11

4. Cui and Freeden kernel

The Cui and Freeden kernel provides a worst-case-error interpretation of its discrepancy for H^3/2(S^2), connecting discrepancy minimization with QMC designs.

5. Cui and Freeden kernel.

  • For H^3/2(S^2), the Cui and Freeden discrepancy is proportional to the corresponding worst-case error, and its minimizers form QMC designs by Theorem 12.The kernel's constant series term is 1, giving the stated worst-case-error relation.Source: §4 · p. 12
  • The Cui and Freeden discrepancy has been used to test uniformity and to analyze quadrature properties of extremal or Fekete points.Fekete points here maximize the interpolation-matrix determinant for polynomials of degree t.Source: §4 · p. 12
  • Numerical data in suggested O(t^-3/2) decay of the discrepancy for spherical t-designs generated from Fekete starting points, prompting Theorem 1.The passage describes this as a numerical suggestion, not a proof of the decay rate.Source: §4 · p. 12

5. Generalized distance kernel

The section explains how powers of pairwise distance can be used to construct reproducing kernels for Sobolev spaces on the sphere.

5. Generalized distance kernel.

  • When s > d/2 and 2s − d is not an even integer, a signed power of distance has a Laplace-Fourier expansion useful for constructing an H^s(S^d) reproducing kernel.The sign is (−1)^(L+1), where L = floor(s − d/2).Source: §5 · p. 12
  • In that expansion, coefficients are positive for degrees ℓ ≥ L + 1 and alternate in sign for ℓ ≤ L.The coefficient behavior supports the kernel construction after suitable modification of early terms.Source: §5 · pp. 12–13
  • Thus, by modifying some of the early coefficients if necessary, one can derive a reproducing kernel for H^s(S^d) for s > d/2 when 2s − d is not an even integer‡.Source: §5 · p. 13

Case I.

For d/2 < s < d/2+1, maximizing the generalized sum of Euclidean distances yields QMC designs. For larger smoothness ranges, the paper uses kernel-energy minimization and identifies restrictions on the distance-based construction.

Case I.

  • For d/2 < s < d/2+1, adding a constant to the distance-based kernel produces the generalized distance kernel for H^s(S^d).In this range, only the constant term in the expansion is negative.Source: Case I · p. 13
  • For d/2 < s < d/2+1, maximizing the generalized sum of Euclidean distances yields QMC designs for H^s(S^d).This also gives an independent proof that does not rely on the spherical-design existence result.Source: Case I · p. 13
  • When 2s−d is an even integer, the expansion terminates and its coefficients do not have the asymptotic behavior required for H^s(S^d).The cited passages describe this as a limitation of the expansion used for the kernel construction.Source: Case I · p. 13
  • For s > d/2+1, unconstrained maximizers of the generalized distance sum concentrate in two opposite points and do not yield QMC designs.The point-set limit is attributed to Björck [10].Source: Case I · p. 14

Case II.

For higher smoothness ranges, the paper constructs a reproducing kernel from a signed distance power and polynomial terms. Minimizing the associated worst-case error yields QMC designs, with spherical L-design constraints simplifying the error expression.

Case II.

  • For s > d/2+1, the kernel representation combines a polynomial term with a signed distance-power term.The construction changes the signs of the negative coefficients for degrees ℓ ≥ 1.Source: Case II · p. 14
  • For d/2+L < s < d/2+L+1, minimizing the worst-case error yields QMC designs for H^s(S^d).The result applies for positive integer L.Source: Case II · p. 14
  • For fixed L ≥ 1, restricting node sets to spherical L-designs removes the Q_L-energy term from the worst-case error formula.The resulting formula is stated to reduce accordingly.Source: Case II · p. 14
  • Spherical L-design configurations that minimize the stated criterion yield QMC designs whenever 2s−d is not an even integer.Source: Case II · p. 14
  • When 2s−d is an even integer, the expansion terminates as a polynomial of degree L in x·y.A logarithmic distance function is discussed as an alternative kernel approach.Source: Case II · pp. 14–15

6. Uniform distribution and low-discrepancy sequences on the sphere

The section defines asymptotic uniform distribution for sequences of point sets on the sphere.

6. Uniform distribution and low-discrepancy sequences on the sphere

  • A sequence is asymptotically uniformly distributed when its node averages converge to the surface integral for every continuous function on the sphere.Source: Uniform distribution · p. 15

Uniform distribution.

QMC designs are asymptotically uniformly distributed, but uniformity alone does not ensure rapid quadrature convergence or the paper’s Property R. The section connects spherical-cap discrepancy to worst-case error and discusses low-discrepancy sequences.

Uniform distribution.

  • QMC design sequences for H^s(S^d), s > d/2, are asymptotically uniformly distributed on S^d.The argument uses convergence for polynomials and their density in the continuous functions.Source: Uniform distribution · p. 15
  • Asymptotic uniformity can coexist with quadrature-error convergence as slow as desired, even for nonconstant functions in every H^s(S^d).The passage describes slowly correcting an imbalance in point counts between regions where a smooth function is positive and negative.Source: Uniform distribution · p. 15
  • Asymptotic uniformity does not imply Property R, and Property R does not imply asymptotic uniformity.Adding o(N) arbitrary points can preserve the limit while breaking Property R; deleting points inside a fixed cap can preserve Property R without uniformity.Source: Uniform distribution · p. 15
  • On the sphere, the paper notes there is no single Koksma–Hlawka inequality; worst-case error provides an integration-error bound for sufficiently smooth functions.Source: Uniform distribution · p. 15
  • At s=(d+1)/2, the worst-case error for the specified Sobolev kernel has an interpretation as spherical-cap L2 discrepancy.Stolarsky’s invariance principle supplies the stated connection.Source: Uniform distribution · pp. 15–16
  • Minimizers of spherical-cap L2 discrepancy form QMC designs for H^(d+1)/2(S^d).Source: Uniform distribution · p. 16
  • Low-discrepancy sequences have almost optimal worst-case-error order for d/2 < s < (d+1)/2, except for a power of log N.The authors state that, to their knowledge, explicit constructions of low-discrepancy configurations on the sphere are not known.Source: Uniform distribution · p. 17

7. QMC designs are better than average

The section compares QMC designs with average-case random sampling and shows how stratification changes the result. Independent uniform points do not form QMC designs, whereas stratified sampling does so over a bounded smoothness range.

  • Independent uniform random points have expected squared worst-case error K(s)(1)/N and do not form QMC designs for s>d/2.Source: §7 · p. 18
  • For random point sets, the stated error expression has order N^-1 regardless of t, whereas it vanishes for spherical t-designs.Source: §7 · p. 18
  • Randomly selecting one point from each small-diameter equal-area cell yields QMC designs on average for d/2<s<d/2+1.The cells have diameter at most c/N^(1/d), with c independent of cell and N.Source: §7 · p. 19
  • This stratification strategy does not yield QMC designs on average for s>d/2+1, under the stated condition that 2s−d is not an even integer.Source: §7 · p. 19

8. Numerical Experiments

The experiments compare spherical point-set sequences using worst-case error and Franke-function integration, then use the observed rates to estimate their smoothness thresholds. At s=3/2, nonrandom sequences show similar apparent decay, while at s=4.5 most tested sequences fall short of the optimal rate.

8.1. Point sets.

  • The experiments include equal-area, Fekete, Coulomb- and log-energy, spiral, distance, spherical-design, and uniformly random point sets.Optimized criteria can have many local optima, so larger point sets may be near, but not at, the global optimum; distance sums were optimized only for s=3/2.Source: §8.1 · pp. 19–20

8.2. Worst case error.

  • At s=3/2, apart from random points, all point sets’ worst-case errors seem to decay like N^-3/4; spherical designs are QMC designs for all s>1, and distance points are provably QMC designs at s=1.5.Source: §8.2 · p. 20
  • At s=4.5, every tested point set except spherical designs has worst-case error decay slower than the optimal O(N^-2.25) rate.Random points still decay like N^-1/2.Source: §8.2 · pp. 20–21

8.3. Integrating a smooth function.

  • For the Franke function, spherical-design integration error shows faster-than-algebraic decay.The test function belongs to Hs(S2) for all s>1.Source: §8.3 · p. 22, Figure 3 · p. 23

8.4. Estimating s*.

  • For equal-area points, the estimated rates are N^-0.95 for worst-case error at s=4.5 and N^-0.96 for Franke-function error, suggesting s*≈2.The precise value of s* remains an open question.Source: Table 1 · p. 23, §8.4 · pp. 23–24

9. Proofs

The proofs establish smoothness transfer and connect QMC error bounds to conditions on point sets. They also justify the energy and stratification results through kernel and partition estimates.

9.1. Proofs of Section 1 results.

  • A QMC-design sequence for Hs(Sd) remains one for every Hs′(Sd) with d/2<s′≤s.The proof uses a bound whose constant depends on the Sobolev norms but not on N.Source: §9.1 · pp. 24, 26
  • Spherical designs with suitable cardinalities provide a sequence of generic QMC designs.Source: §9.1 · pp. 26–27

9.2. Proofs of Section 3 results.

  • QMC-design sequences must satisfy the necessary conditions of Proposition 27, while Property R supplies a sufficient worst-case-error estimate.Source: §9.2 · pp. 27–28

9.3. Proofs of Section 6 results.

  • The kernel comparison proof uses equivalence up to constant factors and monotonicity of the canonical-kernel error in s, for s≥(d+1)/2.Source: §9.3 · p. 28

9.4. Proofs of Section 7 results.

  • The stratification proofs use equal-area cells of diameter O(N^-1/d) and expected-error estimates to obtain the stated smoothness-range bounds.The higher-smoothness result is stated for 2s−d not an even positive integer.Source: §9.4 · pp. 29, 30, 32
Loading 1208.3267v1…