Optimal sampling in general domains

When approximating a multivariate function defined on an irregular domain, a good choice of sampling points is critical. In this paper, my PhD student Juan and I develop new, practical sampling strategies for which the sample complexity is near-optimal: specifically, it is linear (up to a log factor) in the degree of the approximation. This improves previous approaches which were at best quadratic in the degree. Here’s the paper:

Optimal sampling strategies for multivariate function approximation on general domains