PaperlayerView exact revision on arXiv

Source-linked AI summary

Random nodes with positive weights: Richter-Tchakaloff rules and optimal positive quadrature

Sebastian Neumayer, Martin Schäfer, Tino Ullrich

arXiv:2610.32699v1math.NAcs.NA

TL;DR

Positive exact quadrature rules are known to exist, but classical existence results are non-constructive and do not address errors outside the exactness space. This paper constructs positive rules from random nodes and shows that, after compression, they attain universally optimal RKHS error bounds in terms of embedding singular numbers.

  • Problem

    Classical positive exact quadrature rules are guaranteed to exist, but their proofs are non-constructive and they say nothing about error outside the finite-dimensional exactness space.

    Source: §1 · p. 1

  • Method

    The paper combines independent sampling from a suitable density with duality and an L1-norm discretization result to construct exact positive rules.

    Source: §1 · p. 1, §2 · p. 9

  • Results

    With O(n) nodes after compression, positive rules attain the optimal worst-case RKHS error order in singular numbers without requiring singular-number decay assumptions.

    Source: §1 · p. 2, §1.2 · p. 8

  • Takeaways & Limitations

    For separable RKHSs with finite trace, positive weights do not restrict the universally optimal error bound expressed through embedding singular numbers.

    Source: §1 · p. 2

    For individual spaces, a gap between positive-rule and unrestricted widths is not excluded and can be exponential in dimension.

    Source: §1.2 · p. 6

Abstract

from arXiv · show

We show that independent random points support exact quadrature rules with positive weights. For any $n$-dimensional space $V$ of integrable functions a constant multiple of $n\log n$ points sampled from a suitable density yields, with high probability, positive weights which integrate the functions in the space exactly. The weights stay close to the natural importance sampling weights according to the Lewis density with respect to $V$. They are the result of a weight adaptation procedure which requires an explicit $L_1$-norm discretization result that is proved on the way. As an application, we study numerical integration in reproducing kernel Hilbert spaces. Combining the random rules with a subsampling step, we show that positive quadrature rules with constantly oversampled nodes achieve the best possible worst-case error bound in terms of the singular numbers of the embedding into $L_2$.

1 Introduction

The introduction presents positive, exact quadrature rules from independent random nodes, positioning them among prior kernel-quadrature and positive cubature methods. For separable finite-trace RKHSs, it highlights combining random sampling with compression to obtain optimal worst-case error bounds using positive weights.

1 Introduction

  • Richter’s and Tchakaloff’s theorems guarantee positive exact rules but are non-constructive and do not address error outside the exactness space.Non-negative weights are preferred because they provide numerical stability, preserve positivity of the integrand, and sum to one when constants are integrated under a probability measure.Source: §1 · p. 1
  • A constant multiple of n log n independent nodes drawn from a suitable density yield, with high probability, positive weights integrating every function in an n-dimensional space exactly.The construction uses an L1-norm discretization result and adapts importance-sampling weights while keeping them within a fixed relative box.Source: §1 · pp. 1–2, §1.1 · p. 2

1.1 Main results

  • The construction also yields almost-equal weights with m ≥ 34τ^-2γn log(4n/δ), and random uniform points that are almost spherical t-designs with high probability.For spherical polynomials of degree at most t, the stated node count is m ≍d τ^-2td log(t/δ); compression also gives exact rules on 2n nodes with weights 0 ≤ wi ≲ 1/n.Source: §1.1 · p. 3
  • With m ≍ n log(en) random nodes, the RKHS result gives high-probability positive rules exact on V′n, with weights summing to one and an error bound in terms of the singular-number tail.The nodes are drawn from a mixture involving the uniform density, the L1-Lewis density, and the normalized kernel-diagonal tail.Source: §1.1 · pp. 3–4
  • With m ≥ Cn nodes, positive quadrature rules attain the universally optimal RKHS error bound in terms of embedding singular numbers, even though the bound also holds for arbitrary real weights [45].The result applies to separable RKHSs with finite trace; C = 39 is given as a loose choice for a semi-constructive proof.Source: §1.1 · p. 4

1.2 Discussion and related work

  • Theorem 1.1’s n log(n/δ) oversampling is optimal in general: piecewise-constant functions on n equal-measure cells require a node in every cell, and the coupon collector bound gives ≳ n log n samples.Prior randomized least-squares results either require polynomially more samples under an Lr condition [6] or quadratic oversampling to guarantee positive weights.Source: §1.2 · p. 5
  • Theorems 1.3 and 1.4 hold for every separable RKHS with finite trace, relying on no structure of Ω, μ, or K beyond the singular system.Source: §1.2 · p. 7
  • Belhadji, Bardenet and Chainais [5] use a projection DPP for kernel quadrature and bound error with optimal, possibly negative weights by the eigenvalue tail, without a 1/n factor.Source: §1.2 · p. 7
  • The rules have positive weights, are exact on V'_n, require no singular-number decay assumption, and achieve the optimal order with O(n) nodes after compression.This is stated as the paper’s contrast with earlier work (Theorem 1.4).Source: §1.2 · p. 8
  • Hayakawa, Oberhauser and Lyons [37] obtain positive weights by random subsampling and recombination, while Glaubitz reports positivity and exactness for sufficiently large deterministic point sets.The former bound includes the full eigenvalue tail plus a Monte Carlo term, without a 1/n factor; the latter gives no explicit point-count bound and observes that a quadratic number of points in dim V may be necessary.Source: §1.2 · p. 8

2 A probabilistic Richter-Tchakaloff construction

This section develops a probabilistic Richter–Tchakaloff construction that uses independent samples from a suitable density, simultaneous L1-norm discretization, and bounded weight adaptation to produce positive exact quadrature rules with high probability. The resulting weights stay close to the natural importance-sampling weights, and a corollary gives an almost-equal-weight version.

2 A probabilistic Richter-Tchakaloff construction

  • With m ≥ 134n log(40n) Lewis-density samples, a positive Richter-Tchakaloff rule exists with probability at least 90%.More generally, Theorem 2.4 gives exact rules when m ≥ 67γn, with weights between 1/2 and 3/2 times the reference weights mϱ(yi).Source: §2 · pp. 9–10
  • Uniformly sampled spherical polynomials of degree at most t admit exact positive rules with m ≥ 134n log(4n/δ) nodes, and more oversampling yields almost spherical t-designs.For the almost-design result, m ≥ 34τ^-2n log(4n/δ) suffices.Source: §2 · p. 10

2.1 An Lp-bound for the L1-coefficient body

  • A deterministic Lp bound for the support function of the L1-coefficient body provides a key tool for analyzing the sampled rules.The bound is used in the stochastic-process estimates underlying simultaneous discretization.Source: §2.1 · p. 11

2.2 Quadrature error and simultaneous L1-norm discretization

  • For m ≥ 67γn, Proposition 2.10 states that, with probability at least 1 − 4n exp(−m/(134γn)), both of its stated bounds hold simultaneously.The argument of Corollary 2.13 gives constants 1 ± τ for m ≥ 34τ^-2γn log(4n/δ).Source: §2.2 · p. 14

2.3 Richter-Tchakaloff quadrature with high probability

  • Weight adaptation is characterized by when reference weights can be corrected within [(1 − τ)w0_i, (1 + τ)w0_i] while preserving exactness and positivity.The criterion provides two-sided weight bounds together with exactness.Source: §2.3 · pp. 14–15
  • For m ≥ 67γn, with probability at least 1 − 4n exp(−m/(134γn)), exact weights satisfy 1/(2mϱ(yi)) ≤ wi ≤ 3/(2mϱ(yi)) for i = 1, . . . , m.Source: §2.3 · p. 15
  • The resulting rule is exact on the original space V, since sampled nodes outside ΩN do not affect the probability bound.Source: §2.3 · p. 15
  • Corollary 2.13 establishes an almost-equal-weight Richter-Tchakaloff rule with probability at least 1 − δ.The supplied passage does not include the corollary’s weight bounds or full sampling condition.Source: §2.3 · p. 15

3 Positive quadrature in RKHS from random nodes

The section establishes random-node positive quadrature rules in an RKHS, relating their worst-case error to the singular-system tail and bounding that tail for independently sampled nodes.

3 Positive quadrature in RKHS from random nodes

  • With m ≥ 402n independent nodes sampled from ϱnµ, positive weights exist with probability at least 1 − 8n exp(−m/(804n)) and yield exactness on V′n.The weights satisfy 1/(2mϱn(yi)) ≤ wi ≤ 3/(2mϱn(yi)) ≤ 9/(2m).Source: §3 · pp. 17–18

3.2 Tail Gram estimate

  • The tail Gram estimate uses independently sampled nodes and the density component En/Tn to control the contribution of modes beyond Vn.The proof applies a concentration bound to the sampled tail sequences; the excerpt does not provide the proposition’s complete bound.Source: §3 · p. 18, §3.2 · p. 19

3.3 Proof of Theorem 3.1

  • The proof combines exactness, the weight bounds, and the tail estimate to obtain the stated RKHS error bound for the random rule.The argument also treats n ≥ r separately, where ψn vanishes and exactness on Vn suffices for exactness on H.Source: §3 · p. 18, §3.3 · p. 20

3.1 An error identity for exact rules on Vn

  • For rules exact on Vn, the worst-case error is controlled through the tail of the singular system, separating the first n modes from the remaining components.The section derives this error identity before estimating the tail Gram matrix.Source: §3.1 · p. 18, §3 · p. 18

4 Compression to constant oversampling

The section constructively compresses positive exact rules to O(n) nodes. In the RKHS setting, this compression retains the stated singular-number error bound with constant oversampling.

4.1 A constructive compression lemma

  • The constructive compression lemma reduces a positive weight vector while preserving its linear constraints, producing a vector with fewer than k + d nonzero entries.Its iterative procedure moves along directions in ker L until coordinates reach 0 or 1/k.Source: §4.1 · p. 21
  • For an n-dimensional space over a probability measure, a positive exact Richter-Tchakaloff rule exists on at most 2n nodes with weights bounded above by 3/n.The theorem’s weight and exactness statements appear across the supplied theorem passages.Source: §4.1 · p. 22

4.2 A “compressed” version of Theorem 3.1

  • An exact positive rule with weights bounded by 3/(2mϱn(yi)) can be compressed to at most k + n nodes while preserving exactness on Vn.The compressed rule is supported on a subset of the original nodes.Source: §4.2 · p. 23

4.3 Proof of Theorem 1.4

  • For all m ≥ ϕ²(n + 1), κ⁺m(H, µ)² ≤ Tn/(n + 1), and the construction provides a positive rule with fewer than ϕ²(n + 1) nodes.The proof uses a density-based existence argument and a separate constructive route from an O(n log(en)) candidate pool.Source: §4.3 · p. 25

A Tools from probability

This appendix collects probability tools used in the article, including contraction and symmetrization principles, concentration estimates, and an infinite-matrix Chernoff inequality.

A Tools from probability

  • The contraction principle compares expected suprema of related stochastic processes under convexity, monotonicity, and contraction conditions.The appendix identifies it as a classical result [46, Thm. 4.12].Source: A Tools from probability · p. 30
  • The symmetrization principle is stated for independent random vectors in a normed finite-dimensional space, using independent Rademacher variables.The appendix cites [28, Lem. 8.4] and [46, Lem. 6.3].Source: A Tools from probability · p. 30
  • A moments-and-tails proposition recites a standard relationship between tail bounds and moment estimates.The appendix cites [28, Prop. 7.13], [51, Cor. 4.3], and a converse in [28, Prop. 7.11].Source: A Tools from probability · p. 30
  • A Bernstein moment-generating-function bound for independent centered bounded variables is presented as the key step in proving Bernstein’s inequality.The variables are bounded by L and have individual second-moment bounds σ_i^2.Source: A Tools from probability · p. 30
  • A moment estimate is derived from the preceding lemma for independent centered variables with bounded magnitudes and a bound on their summed variances.The stated estimate applies for p ≥ 1.Source: A Tools from probability · pp. 30–31
  • The appendix’s final result is an infinite matrix Chernoff inequality for independent, identically distributed ℓ2(N)-valued sequences with bounded norms and a common second-moment matrix.The theorem is attributed to Moeller and Ullrich [52, Prop. 3.8].Source: A Tools from probability · p. 31
Loading 2610.32699v1…