Hypercontractivity meets random convex hulls: analysis of randomized multivariate cubatures

Journal article

Given a probability measure μ on a set X and a vector-valued function φ, a common problem is to construct a discrete probability measure on X such that the push-forward of these two probability measures under φ is the same. This construction is at the heart of numerical integration methods that run under various names such as quadrature, cubature, or recombination. A natural approach is to sample points from μ until their convex hull of their image under φ includes the mean of φ. Here we analyze the computational complexity of this approach when φ exhibits a graded structure by using so-called hypercontractivity. The resulting theorem not only covers the classical cubature case of multivariate polynomials, but also integration on pathspace, as well as kernel quadrature for product measures.

Authors: Hayakawa, S; Oberhauser, H; Lyons, T

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Royal Society
• Journal: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
• Volume: 479
• Issue: 2273
• Article number: 20220725
• Publication date: 2023-05-17
• Acceptance date: 2023-04-20
• DOI: 10.1098/rspa.2022.0725
• EISSN: 1471-2946
• ISSN: 1364-5021
• Language: English
• Keywords: hypercontractivity; cubature; random convex hull; FFR; kernel quadrature