Constructive Tchakaloff results and well-conditioned quadrature through randomized least squares
Abstract
We consider using randomized least squares to construct quadrature rules exact on a subspace of functions. Using new conditions that we call relative admissibility and reference weight concentration, we establish both that the quadrature weights from such a procedure concentrate close to their asymptotic values with prescribed and arbitrarily large probability, and this in turn provides useful finite-sample probabilistic bounds on the stability of the resulting quadrature rules for very general classes of possibly complex-valued functions. Our analysis both significantly generalizes the existing analysis of randomized least squares quadrature construction, and provides new bounds on stability for these rules. These results specialize to existence results for positive quadrature rules, when such rules can be theoretically expected. Because our procedures are formally algorithmic, our analysis is a substantive advance toward computationally constructive generalized Tchakaloff theorems.
Related
- Random nodes with positive weights: Richter-Tchakaloff rules and optimal positive quadrature
- Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
- Evaluating IMMPACT Criteria for the Clinical Meaningfulness of Between-Group Differences: Interpreting Randomized Trial Results within a Context of Existing Chronic Pain Analgesics.
- Inequalities and equalities of means in Constructive Mathematics
- Constructive equivalence between Brouwer's fixed-point theorem and weak König's lemma
BibTeX
@misc{belik2026constructive,
title = {{Constructive Tchakaloff results and well-conditioned quadrature through randomized least squares}},
author = {Filip Bělík and Akil Narayan and John Turnage},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09506},
eprint = {2609.09506},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09506},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Constructive Tchakaloff results and well-conditioned quadrature through randomized least squares
AU - Filip Bělík
AU - Akil Narayan
AU - John Turnage
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09506
UR - https://arxiv.org/abs/2609.09506
AB - We consider using randomized least squares to construct quadrature rules exact on a subspace of functions. Using new conditions that we call relative admissibility and reference weight concentration, we establish both that the quadrature weights from such a procedure concentrate close to their asymptotic values with prescribed and arbitrarily large probability, and this in turn provides useful finite-sample probabilistic bounds on the stability of the resulting quadrature rules for very general classes of possibly complex-valued functions. Our analysis both significantly generalizes the existing analysis of randomized least squares quadrature construction, and provides new bounds on stability for these rules. These results specialize to existence results for positive quadrature rules, when such rules can be theoretically expected. Because our procedures are formally algorithmic, our analysis is a substantive advance toward computationally constructive generalized Tchakaloff theorems.
ER -