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}\|f - \mathcal{A}_Z f\| < \mathbb{E}\|f - \mathcal{A}_Y f\|, $

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.