Extensible Grids: Uniform Sampling on a Space Filling Curve

DOI10.1111/RSSB.12132MaRDI QIDQ5378376zbMATH OpenOpenAlexFDO

Authors Zhijian He, Art B. Owen

Publication date 12 June 2019

Published in Journal of the Royal Statistical Society Series B: Statistical Methodology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.4549

zbMATH Keywords

Hilbert space filling curvelattice sequencerandomized quasi-Monte-Carlo samplingsequential quasi-Monte-Carlo methodvan der Corput sequence

Mathematics Subject Classification ID

Fractals (28A80) Computational methods in Markov chains (60J22) Asymptotic properties of parametric estimators (62F12)

Abstract: We study the properties of points in $[0,1{]}^d$ generated by applying Hilbert's space-filling curve to uniformly distributed points in $[0,1]$. For deterministic sampling we obtain a discrepancy of $O(n^{-1/d})$ for $dge2$. For random stratified sampling, and scrambled van der Corput points, we get a mean squared error of $O(n^{-1-2/d})$ for integration of Lipshitz continuous integrands, when $dge3$. These rates are the same as one gets by sampling on $d$ dimensional grids and they show a deterioration with increasing $d$. The rate for Lipshitz functions is however best possible at that level of smoothness and is better than plain IID sampling. Unlike grids, space-filling curve sampling provides points at any desired sample size, and the van der Corput version is extensible in $n$. Additionally we show that certain discontinuous functions with infinite variation in the sense of Hardy and Krause can be integrated with a mean squared error of $O(n^{-1-1/d})$. It was previously known only that the rate was $o(n^{-1})$. Other space-filling curves, such as those due to Sierpinski and Peano, also attain these rates, while upper bounds for the Lebesgue curve are somewhat worse, as if the dimension were $lo{g}_2(3)$ times as high.

Recommendations

• Deterministic sampling from uniform distributions with Sierpiński space-filling curves
• Sampling spaces of thick polygons
• Sampling of Planar Curves: Theory and Fast Algorithms
• Asymptotic normality of extensible grid sampling
• Exact sampling with highly uniform point sets
• scientific article; zbMATH DE number 2079612
• Density-Controlled Sampling of Parametric Surfaces Using Adaptive Space-Filling Curves
• Sampling inequalities for sparse grids
• Space-filling curve techniques for parallel, multiscale-based grid adaptation: concepts and applications
• On the generation of curvilinear grids

Cited in

(19)

• Sequential Bayesian inference for static parameters in dynamic state space models
• Sorting methods and convergence rates for Array-RQMC: some empirical comparisons
• Deterministic sampling from uniform distributions with Sierpiński space-filling curves
• Negative association, ordering and convergence of resampling methods
• Asymptotic normality of extensible grid sampling
• Improving simulated annealing through derandomization
• On the convergence rate of randomized quasi-Monte Carlo for discontinuous functions
• Low-discrepancy curves and efficient coverage of space
• Population Quasi-Monte Carlo
• QMC Sampling from Empirical Datasets
• Convergence analysis of quasi-Monte Carlo sampling for quantile and expected shortfall
• k-d darts, sampling by k-dimensional flat searches
• Expected integration approximation under general equal measure partition
• A review on design inspired subsampling for big data
• Super-polynomial accuracy of multidimensional randomized nets using the median-of-means
• Space-filling designs on Riemannian manifolds
• Extensible grid sampling for quantile estimation
• Upper bound estimation of star discrepancy based on Hilbert space filling curve stratified sampling and its applications
• Probabilistic weighted star discrepancy bound based on the general equal measure partition

This page was built for publication: Extensible Grids: Uniform Sampling on a Space Filling Curve

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5378376)