Constructive Tchakaloff results and well-conditioned quadrature through randomized least squares

1. Introduction

• Positive weights support Lebesgue-type approximation bounds, avoid cancellation, and give immediate uniform-norm stability, while multidimensional unstructured domains pose a more difficult construction problem.The introduction contrasts these settings with classical one-dimensional positive rules and product-structure-dependent alternatives.Source: §1 · p. 1

1.1. Summary of contributions.

• Finite-sample weight concentration yields stable quadrature rules and, under positivity conditions, interpolatory-size positive rules through pruning.The contribution summary describes bounded condition numbers and positive rules with M ≤ N.Source: §1.1 · p. 2, §1 · p. 2
• Relative admissibility controls large values of k(x)/L(x)^2 probabilistically, while reference weight concentration is additionally required for stability guarantees.The paper notes that a sampler satisfying relative admissibility alone can be augmented to meet both conditions.Source: §1.1 · p. 2
• The trial-based procedure samples an M-point least-squares rule, tests stability or positivity, and prunes successful rules to obtain an N-point rule.For the sample sizes covered by the results, success occurs with high probability.Source: §1.1 · p. 2
• Compared with, the setup and assumptions are more general, while the results are less general than [26] but explicitly constructive.The stated scope includes infinite measures, unbounded Christoffel-type functions, flexible sampling, integration-type functionals, approximation weights, and complex-valued functions.Source: §1.1 · p. 2

2.1.2. The sampling measure ρ

• Sampling uses dρ = τ² dµ with coverage wherever evaluations on V are nonzero; the induced distribution attains the minimum stability parameter Q = N.A different sampler may be used, for example when only an approximation to the induced distribution is available.Source: §2.1.2 · p. 4

2.1.4. Quadrature rules

• Quadrature stability is measured in a weighted supremum norm, and deterministic Carathéodory–Steinitz pruning can reduce an exact rule to at most N active nodes while preserving positivity.The weighted formulation supports stability and approximation estimates even on unbounded domains when weighted functions remain bounded.Source: §2 · p. 3, §2.1.4 · p. 5

2.2. The main procedure: “intermediate” least squares quadrature

• The procedure applies L to the weighted least-squares approximation from M iid samples, yielding an exact-on-V quadrature rule with weights independent of the input function.The least-squares solution is unique when the sample set provides sufficient stability, which the analysis accounts for.Source: §2.2 · pp. 6–7

2.3.1. Relative admissibility

• Relative admissibility controls the risk of evaluations nearly orthogonal to L, which can amplify relative errors in the least-squares weights.Relative weight accuracy below one preserves positivity when the limiting weights are nonnegative.Source: §2.3.1 · p. 7, §2.3 · p. 7

2.3.2. Reference-weight concentration

• Reference-weight concentration requires the weighted evaluation quantity KL,ρ,W(X) to be sub-exponential, controlling its fluctuations around a mean independent of the sampling measure.This concentration condition supports bounds on the quadrature condition number.Source: §2.3.2 · p. 8

2.4. Main result: Stability of intermediate least squares quadrature

• For any prescribed 0 < ξ < 1, suitable finite sample sizes yield a well-defined rule exact on V whose weights approximate their limiting values with probability at least 1 −ξ.The sample size must lie in a valid interval: increasing M is not always permitted because all random weights must be controlled simultaneously.Source: §2.4 · p. 8
• Stronger integrability, with some r > 2, gives a more transparent quantitative sample-complexity bound for the relative-error case.Relative admissibility alone guarantees existence of a suitable threshold J but does not specify its rate.Source: §2.4 · p. 8

2.4. Main result: Stability of intermediate least squares quadrature.

• Under relative admissibility and reference-weight concentration, the rule is well-defined and exact on V with probability at least 1 −ξ, with stable weights and controlled weighted condition number.The weights are close to their limiting values.Source: §2.4 · pp. 8–9

2.5. Quadrature with real and positive weights.

• For a nonnegative pair, finite-sample weights close to their limits are real and nonnegative, and strictly positive at nodes where L is positive.The setup requires V to be closed under conjugation, L to be real-preserving, and its Riesz representer to be nonnegative; relative error σ < 1 suffices.Source: §2.5 · p. 9

2.6. Main results: Positive quadrature.

• Relative admissibility and a nonnegative pair yield a constructive rule with at most N positive-weight nodes exact on V; conjugate closure permits at most dimC eV ≤ 2N nodes exact on V.The construction uses randomized least-squares trials followed, upon success, by Carathéodory–Steinitz-type pruning; for a non-conjugation-closed V, the rule is exact on its conjugate closure.Source: §2.6 · p. 10

2.6.1. Relation to previous work.

• Unlike general L1 Tchakaloff results [26], this L2_µ approach imposes sampling and admissibility hypotheses tailored to weighted least squares but gains a randomized construction.The paper characterizes its result as a constructive L2_µ-based result rather than the most general abstract existence theorem.Source: §2.6.1 · p. 10

2.7. Discussion: Relative/absolute admissibility and reference-weight concentration.

• Relative admissibility holds when sampling probability around zeros is not too large: if ρ has bounded Lebesgue density and L has finitely many isolated zeros of algebraic order α > 0, α < d/2.The text says the asymptotic characterizations JpJ → 0 and JqJ → 0 are stronger than necessary, and weaker conditions suffice to replace their roles.Source: §2.7 · pp. 10–11

2.7.1. Mixture sampling.

• Mixture sampling can ensure both relative admissibility and reference-weight concentration, while retaining near-optimal Gramian control and making the weighted reference magnitude uniformly bounded.For every θ ∈ (0, 1), the mixture measure ρθ has both properties when the induced measure satisfies relative admissibility.Source: §2.7.1 · p. 11, §B.3 · p. 32

2.7.2. Distinctions between the conditions.

• Relative admissibility, absolute admissibility, and reference-weight concentration control different probabilistic tails; the first two do not necessarily imply the third.The conditions concern tail behavior of distinct quantities under X ∼ ρ.Source: §2.7.2 · p. 12

2.8. Comparison to results in [21, 26].

• Compared with, these results guarantee prescribed-probability stability of individual sampled rules rather than expected errors; compared with [26], they provide explicit randomized construction under relative admissibility.The choice of J under relative admissibility may remain implicit in more general scenarios.Source: §2.8 · p. 12

3. Least squares approximations

• When the empirical Gramian is invertible, applying the functional to the sampled weighted least-squares approximation gives a quadrature rule exact on V.The procedure first samples nodes and forms the approximation in V.Source: §3 · p. 12, §3.1 · p. 13

3.2. Empirical Gramian.

• The empirical Gramian has expectation I and converges almost surely to I.Source: §3.2 · p. 13

3.3. Least squares weights and their limit.

• If V is closed under complex conjugation and L is real-preserving, invertibility of the empirical Gramian makes the least-squares weights real.Source: §3.3 · p. 13
• Least-squares weights inherit the limiting magnitude, and in the real-preserving case the limiting sign, of the reference-weight function.The idealized rule formed from the limiting weights is unbiased for L on V.Source: §3.3 · p. 14
• The mean weighted reference magnitude is independent of the sampling measure, whereas its fluctuations and the finite-sample Gramian depend on the sampling measure.Source: §3.3 · p. 14

4. Concentration results

• For each fixed sampled index, the least-squares weights converge to the reference weight, and the section quantifies this approximation at finite sample size.The finite-sample analysis combines inverse-Gramian control with relative or absolute admissibility.Source: §4 · p. 14

4.1. Concentration of the empirical Gramian.

• Empirical Gramian concentration and a corresponding inverse-Gramian estimate provide the probabilistic input for controlling least-squares weights.A finite bound on the inverse-Gramian deviation entails that the Gramian is invertible.Source: §4.1 · p. 15

4.2. Deterministic absolute and relative weight bounds.

• The deterministic perturbation bound relates least-squares weight errors to stability factors, and the two admissibility conditions control the corresponding amplification factors.These bounds connect inverse-Gramian concentration to pointwise weight control.Source: §4.2 · pp. 15–16

4.3. An admissible sample-size window.

• An admissible sample-size window makes inverse-Gramian concentration and the event that all sampled nodes are good compatible.The section establishes this window for the relative and absolute admissibility conditions.Source: §4.3 · p. 16, §4.4 · p. 17

4.4. Finite-sample weight approximation.

• With probability at least 1 −ξ, the least-squares rule can be well-defined and exact on V, with weights close to their reference values; for a nonnegative pair, its weights are nonnegative.If L is positive at every sampled node, the weights are strictly positive.Source: §4.4 · pp. 17–18

4.5. Condition numbers of intermediate rules.

• Relative admissibility and reference-weight concentration yield finite-sample weighted stability bounds; an analogous result under absolute weight control additionally requires concentration of W(X)^−1.Weighted stability also converts approximation in B∞_W(D) into a quadrature-error bound.Source: §4.5 · pp. 19–20

5.1. Positive pruning.

• A nonnegative exact M-point rule can be deterministically compressed to a nested exact rule with at most N = dim(V) active nodes, preserving nonnegativity.The constructive reduction uses linear dependence in the moment equations.Source: §5 · p. 21, §5.1 · p. 21
• When 1 ∈ V, positive pruning preserves the sharp stability bound associated with exactness on constants.For a probability measure, the resulting rule has condition number 1.Source: §5.1 · p. 21

5.2. Variants and interpretations.

• Algebraic pruning yields an exact nested rule with at most N nonzero weights, but in general it does not preserve positivity or stability.The stated general role is interpolatory-size exactness when arbitrary signed or complex weights are permitted.Source: §5.2 · p. 22
• For an N-dimensional complex-valued space with real nonnegative weights, a nested real nonnegative exact rule exists with at most 2N active nodes.The real and imaginary parts span a real-valued space of dimension at most 2N.Source: §5.2 · p. 22

6. Numerical example

• Although induced sampling attains the optimal stability parameter Q = N, it struggles when limiting weights collapse near singularities, and induced and mixture sampling can concentrate weights close to zero.The example has an unbounded basis; limiting weights approach zero near Riesz-representer zeros, basis singularities, and tails where k(x) is large.Source: §6 · pp. 23–24
• For N ≥ 8, standard sampling rarely achieves Gramian concentration, while induced and θ = 0.5 mixture sampling concentrate markedly better; the mixture incurs the predicted factor-of-two increase in the upper bound Q ≤ N/θ.The comparison is over the range considered, where mixture concentration also shows some dependence on N.Source: §6 · p. 23, Figure 2 · p. 24
• Standard sampling produces significantly worse-conditioned intermediate rules and larger maximum absolute weights than induced or mixture sampling, whose conditioning differs relatively little.The figure reports median condition numbers and the 95th percentile of maximum absolute weight rescaled by M.Source: §6 · p. 24
• For N = 10 and M = 500, induced- and mixture-sampled intermediate weights lie closer to their limiting weights than standard-sampled weights, and mixture sampling reduces the largest limiting weights relative to induced sampling.The plotted pruned rules are strictly positive; intermediate weights are scaled by M and pruned weights by N.Source: Figure 3 · p. 24, §6 · p. 24

7. Disclosures

• Julia software reproducing the figures in Section 6 is provided, with pseudorandom-number-generator seeds fixed so plots can be exactly reproduced.The software is available at the stated GitHub repository.Source: §7.1 · p. 25

7.1. Reproducibility Statement.

• All plot-generating data are provided in the repository, and no external or extra data are required.Source: §7.2 · p. 25

7.2. Data Availability Statement.

• The authors used AI tools to proofread near-final drafts, identify typographical errors, and clean up the software repository.The authors accept responsibility for all content and numerical results.Source: §7.3 · p. 25

7.3. Statement on the use of AI.

• The authors acknowledge support from AFOSR award FA9550-23-1-0749 and NSF DMS-2136198.Source: §7.4 · p. 25

8. Conclusion

• Under small-ball relative admissibility and reference-weight concentration, finite-sample weights achieve relative accuracy and weighted stability with high probability; a sampling mixture can preserve these conditions.With a nonnegative pair condition, relative weight concentration yields positive rules, and Carathéodory–Steinitz pruning gives interpolatory-size positive rules as a constructive generalized Tchakaloff result.Source: §8 · p. 25
• The theory assumes sub-exponential reference-weight concentration, and future work includes weakening this assumption and extending results to Hilbert-valued integrands.Examples indicate relative and absolute admissibility can hold with polynomial tails, suggesting useful high-probability estimates may remain possible under weaker tail assumptions.Source: §8 · p. 25

Appendix A. Admissible subspaces

• Appendix A treats three relative-admissibility regimes: bounded Christoffel function with nonvanishing representer, isolated zeros, and unbounded Christoffel function with nonvanishing representer.The last regime includes polynomial spaces over unbounded domains under exponentially decaying measures when L ≡ 1.Source: Appendix A · p. 28

A.1. Bounded Christoffel function and a nonvanishing representer.

• When k is uniformly bounded and L is bounded away from zero, relative admissibility holds for every sampling measure with Q < ∞.This setting also admits sharper sample-complexity bounds for Theorem 4.Source: §A.1 · p. 28

A.2. Bounded Christoffel function and isolated zeros.

• For finitely many isolated zeros, relative admissibility holds when each zero’s order α_j is less than d/2; in dimensions d ≤ 2, this excludes simple roots.Source: §A.2 · p. 29

A.3. Unbounded Christoffel function and a nonvanishing representer.

• With induced sampling, polynomial subspaces under suitable exponentially decaying measures can be relatively admissible even when K = ∞; an isolated singularity also satisfies the Christoffel-tail condition when α < d/4.The latter threshold is stronger than α < d/2, which ensures the singular function belongs to L2.Source: §A.3 · pp. 29–30

B.1. Proof of Lemma 5: Quantitative sample complexity.

• For r > 2, the lemma provides a sample-size choice that satisfies the upper-bound requirement on A_J p_J.The passage identifies this as the relative case of Theorem 4.Source: §B.1 · p. 31
• Decreasing ζ, equivalently increasing α, increases J and can satisfy the stated lower-bound requirements on A_J and J.Source: §B.1 · p. 31
• With the chosen sample size and parameter, the relative finite-sample estimate holds.Source: §B.1 · p. 31

• For conjugation-closed V, L is real-preserving if and only if its L2 µ-Riesz representer is real-valued.Source: §B.2 · p. 31
• If L is real-preserving, the imaginary component b of its representer has norm zero, so the representer is real-valued in L2.Source: §B.2 · p. 31
• Conversely, a real-valued representer makes L real-preserving.Source: §B.2 · p. 32

• For every θ in (0, 1), the mixed measure satisfies both relative admissibility and reference-weight concentration with respect to W.Source: §B.3 · p. 32
• The mixed measure is well-defined, with Qθ bounded above by N/θ and therefore finite.Source: §B.3 · p. 32
• A uniform bound on K_L,ρθ,W(X) establishes reference-weight concentration because it is sub-exponential.Source: §B.3 · p. 32

B.4. Proof of Lemma 15: Real least-squares weights.

• If V is closed under conjugation, L is real-preserving, and G(M) is invertible, the least-squares weight vector belongs to R^M.Source: §B.4 · p. 32
• The proof computes the weights in a real-valued orthonormal basis, then identifies them with the weights from the complex basis used in (3.7).Source: §B.4 · p. 33

B.5. Proof of Lemma 17: Empirical Gram Concentration.

• Lemma 17 establishes Gramian concentration under Q < ∞, using a matrix Chernoff bound [29, Theorem 1.1].Source: §B.5 · p. 33

B.6. Proof of Theorem 27: Carathéodory’s theorem.

• A nonnegative exact rule with more than N nodes can be pruned to a nested rule with at most N active nodes.Perturbing weights along a real null vector preserves exactness; iteration sets active weights to zero until the bound is reached.Source: §B.6 · p. 34

B.7. Integral Representer.

• For the integral representer proof, the orthonormal basis is chosen with φ1 ≡ 1, using 1 ∈ V and the fact that µ is a probability measure.Source: §B.7 · p. 35

B.8. Weighted Lebesgue inequality.

• The weighted Lebesgue inequality follows by applying exactness and the triangle inequality, then taking the infimum over v ∈ V.Source: §B.8 · p. 35