The partition principle revisited: Non-equal volume designs achieve minimal expected approximation error in function sampling

This paper investigated the expected approximation error in function recovery via a novel class of non-uniform-volume partitions. We established two main theoretical results. First, we proved a strong partition principle showing that stratified sampling based on our proposed non-uniform-volume partitions yielded a strictly smaller expected approximation error than classical jittered sampling:

$$\mathbb{E}\Vert f-{\mathcal{A}}_{Z}f\Vert <\mathbb{E}\Vert f-{\mathcal{A}}_{Y}f\Vert ,$$

where $Z$ and $Y$ denoted random samples drawn from the non-uniform-volume and jittered designs, respectively, and $\mathcal{A}$ denoted the piecewise-constant approximation operator. Second, we derived explicit, dimension-explicit upper bounds on the expected approximation error under our non-uniform-volume partition framework—bounds that improved upon the best-known rates for jittered sampling at the constant level. We wish to emphasize that the improvement was at the constant level only: the asymptotic convergence rate $\mathcal{O}(N^{-1/2-1/(2d)})$ remained unchanged from classical jittered sampling. Nevertheless, we believed that constant-level improvements can be practically significant and theoretically illuminating. Collectively, these results offered a theoretical basis for the use of non-uniform-volume partitions in high-dimensional function approximation and sampling theory.