betaFeedback

WorksMathematics

Sparse designs via quantization of the uniform measure on high-dimensional hypercubes

Abstract

While the notions of sphere packing and sphere covering underlie the most widely used criteria for space-filling design in computer experiments, namely, the maximin and minimax approaches, they suffer from major drawbacks in high dimensions. First, when the dimension dd is very large, deploying a space-filling design requires an extremely large number of design points, making the very notion of a space-filling design questionable. Second, these two design characteristics are highly sensitive to boundaries, particularly when the design domain is a hypercube (the case considered in this paper), and especially to its vertices. This sensitivity is particularly acute when the design size is less than 2d2^d. Instead of considering the maximin or minimax criterion, we consider here the quantization error of the uniform measure on the hypercube. This error has three key advantages: it accounts for the entire distribution of distances from a random point UU to the design, is less sensitive to boundary effects than the maximin and minimax criteria, and, thanks to Zador's celebrated theorem, enables a smooth and natural transition to uniform designs as the design size tends to infinity. Building on recent results on the construction of optimal random quantizers for spherically symmetric distributions (arXiv:2610.11772) we propose a method to generate random designs of a given target size nn with small LsL_s-mean quantization error. The support of the resulting distribution is then used to construct designs, possibly incrementally, with sizes up to nn. We demonstrate that, for moderate nn, designs supported on a fractional factorial subset of the vertices of a small hypercube perform exceptionally well—and significantly better than designs uniformly distributed over the entire hypercube. We also explain how to account for projections onto lower-dimensional subspaces.

Introduction

Let μ\mu be a probability measure on a compact subset X\mathcal{X} of Rd\mathbb{R}^d (with particular emphasis on the case where X\mathcal{X} is the hypercube [−1,1]d[-1,1]^d), and let Xn={x1,…,xn}∈Rn×d\mathbf{X}_n = \{x_1,\ldots,x_n\} \in\mathbb{R}^{n \times d} be a design of size nn, i.e., an nn-point set in X\mathcal{X}. By high dimension, we mean the situation where nn is typically smaller than 2d2^d, the number of vertices of the hypercube. For any s>0s > 0, the LsL_s-mean quantization error of μ\mu for Xn\mathbf{X}_n is

Eμ,s(Xn)=(Eμ{min⁡i=1,…,n∥U−xi∥s})1/s,E_{\mu,s}(\mathbf{X}_n) = \left(\mathbb{E}_{\mu}\{\min_{i=1,\ldots,n}\|U-\mathbf{x}_i\|^s\}\right)^{1/s},

where U∼dμU \overset{d}{\sim} \mu. When μ\mu has the density φ\varphi with respect to the Lebesgue measure, Zador’s celebrated theorem [21] states that the empirical distribution of an nn-point optimal quantizer Xn∗\mathbf{X}_n^* minimizing Eμ,s(Xn)E_{\mu,s}(\mathbf{X}_n) converges weakly, as n→∞n \to\infty, to the probability measure with density proportional to φd/(d+s)\varphi^{d/(d+s)}. It also characterizes the asymptotic value of n1/dEμ,s(Xn∗)n^{1/d}E_{\mu,s}(\mathbf{X}_n^*). Note the connection with transport theory: for s≥1s \ge1, Eμ,s(Xn∗)E_{\mu,s}(\mathbf{X}_n^*) is the minimum Kantorovich (or Wasserstein) distance of order ss between μ\mu and a measure with at most nn support points; see [5 Lemma 3.4]. Designs with small quantization error are particularly relevant for numerical integration; see [14].

The construction of an nn-point optimal quantizer Xn∗\mathbf{X}_n^* is a difficult task. While in low dimensions greedy algorithms can be used for the incremental construction of designs with small quantization error [8, 10], they become computationally infeasible for large dd. When μ\mu is uniform on X\mathcal{X}, the points of an optimal quantizer are asymptotically uniformly distributed for all s>0s > 0, and the asymptotic considerations above do not help with the construction of designs with small quantization error. However, these asymptotics are effective only when n1/dn^{1/d} is sufficiently large, which in large dimension requires astronomically large values of nn. In fact, for large dd and reasonable nn, random designs uniformly distributed on specific subsets of X\mathcal{X} can achieve exceptional performance. This is proved in [16] for the case when μ\mu is spherically symmetric; in this paper we consider the case where μ\mu is uniform on [−1,1]d[-1,1]^d. Related work studies covering and quantization in high-dimensional cubes, including non-lattice constructions and nested designs [22, 11]; high-dimensional exploration and convergence of global random search algorithms are considered in [13].

The paper is organized as follows. § 2 introduces the main notions and recalls some results for spherically symmetric distributions. § 3, which contains the main results of the paper, addresses the case where X\mathcal{X} is the dd-dimensional hypercube Cd\mathcal{C}_d. In § 3.1, we construct spherically symmetric approximations of measures on Cd\mathcal{C}_d; this yields an approximation of Eμ,ss(Xn)E_{\mu,s}^{s}(\mathbf{X}_n) for random designs Xn\mathbf{X}_n (Section 3.2). Distributions minimizing this approximate criterion are studied in § 3.5, with numerical illustrations in Section 3.4; § 5 compares the approximate criterion with its numerically computed value, showing that it over-estimates the true value in the examples considered. § 6 demonstrates the value of our approach through numerical examples. The support of the optimal distribution corresponds to the vertices of a small hypercube in Cd\mathcal{C}_d; these can be sampled randomly (§ 6.1 and § 6.2) or via a deterministic greedy algorithm (§ 6.3). Designs of size exceeding the number of vertices are treated in § 6.4, and § 6.5 illustrates the necessary trade-off between quantization in the full hypercube Cd\mathcal{C}_d and in its lower-dimensional projections. § 7 briefly concludes. The examples presented in the paper use the MATLAB scripts available at https://github.com/lpronzato-prog/random-quantizers-high-d-cube.

We denote by Bd(x,r)\mathcal{B}_d(\mathbf{x},r) the dd-dimensional (closed) Euclidean ball with centre x\mathbf{x} and radius rr; we write Bd(r)=Bd(0d,r)\mathcal{B}_d(r)=\mathcal{B}_d(\mathbf{0}_d,r), and Sd−1(r)\mathcal{S}_{d-1}(r) denotes its (d−1)(d-1)-dimensional boundary sphere; ∥⋅∥\|\cdot\| is the ℓ2\ell_2-norm; uT\mathbf{u}^{\mathsf{T}} is the transpose of the column vector u\mathbf{u}; Id\mathbf{I}_d is the dd-dimensional identity matrix.

Distance c.d.f., quantization error and distortion

Definitions and basic properties

For any nn-point design Xn\mathbf{X}_n we denote by d(⋅,Xn)d(\cdot,\mathbf{X}_n) the distance function defined by x∈Rd↦d(x,Xn)=min⁡xi∈Xn∥x−xi∥\mathbf{x} \in\mathbb{R}^d \mapsto d(\mathbf{x},\mathbf{X}_n)=\min_{\mathbf{x}_i\in\mathbf{X}_n}\|\mathbf{x}-\mathbf{x}_i\|.

Definition 2.1. For XnX_n a fixed nn-point set in Rd\mathbb{R}^d and μ\mu a probability measure on Rd\mathbb{R}^d, the distance c.d.f. F(⋅;Xn,μ)F(\cdot; X_n,\mu) is the c.d.f. of the random variable d(U,Xn)d(U,X_n) where U∼dμU \mathrel{\mathop{\sim}\limits^{d}} \mu:

F(t;Xn,μ)=μ{U∈⋃i=1nBd(xi,t)}=μ{d(U,Xn)≤t}.F(t; X_n,\mu)=\mu\left\{U\in\bigcup_{i=1}^{n}\mathcal{B}_d(x_i,t)\right\}=\mu\{d(U,X_n)\leq t\}.

For PnP_n a probability measure on Rn×d\mathbb{R}^{n\times d}, the mean distance c.d.f. F(⋅;Pn,μ)F(\cdot;P_n,\mu) is defined by F(t;Pn,μ)=EPn{F(t;Rn,μ)}F(t;P_n,\mu)=\mathbb{E}_{P_n}\{F(t;R_n,\mu)\}, where RnR_n is a random nn-point design generated with PnP_n.

If μ\mu is the delta measure δu\delta_u concentrated at u∈Rdu\in\mathbb{R}^d, the mean distance c.d.f. is simply F(t;Pn,δu)=Pn{d(u,Rn)≤t}F(t;P_n,\delta_u)=P_n\{d(u,R_n)\leq t\}. When μ\mu is equivalent to the Lebesgue measure on X\mathcal{X}, the essential supremum of the random variable d(U,Xn)d(U,X_n) is equal to the covering radius CR⁡(Xn)=max⁡x∈Xd(x,Xn)\operatorname{CR}(X_n)=\max_{x\in\mathcal{X}}d(x,X_n) and F(⋅;Xn,μ)F(\cdot;X_n,\mu) has a density f(⋅;Xn,μ)f(\cdot;X_n,\mu) on [0,CR⁡(Xn)][0,\operatorname{CR}(X_n)]. When μ\mu is the uniform measure on X\mathcal{X}, the distance c.d.f. contains all information about the filling of X\mathcal{X} by XnX_n. The LsL_s-mean quantization error of μ\mu for XnX_n [5], or equivalently the (μ,s)(\mu,s)-distortion related to XnX_n [14], provides a scalar summary of this information.

References

  1. [1]G.E.P. Box and J.S. Hunter. The 2^{k-p} fractional factorial designs. Part I. Technometrics, 3(3):311–351, 1961.
  2. [2]R. Cabral-Farias, L. Pronzato, and M.-J. Rendas. Incremental construction of nested designs based on two-level fractional factorial designs. In V.B. Melas J. Pilz and A. Bathke, editors, Statistical Modeling and Simulation for Experimental Design and Machine Learning Applications, pages 77–110. Springer, 2023.DOI
  3. [3]R. Cranley and T.N.L. Patterson. Randomization of number theoretic methods for multiple integration. SIAM Journal on Numerical Analysis, 13(6):904–914, 1976.DOI
  4. [4]W. Feller. An Introduction to Probability Theory and Its Applications, vol. 2. Wiley, New York, 1971. Second edition.
  5. [5]S. Graf and H. Luschgy. Foundations of Quantization for Probability Distributions. Springer, Berlin, 2000.DOI
  6. [6]H.S. Hong and F.J. Hickernell. Algorithm 823: Implementing scrambled digital sequences. ACM Transactions on Mathematical Software (TOMS), 29(2):95–109, 2003.DOI
  7. [7]J.L. Loeppky, J. Sacks, and W.J. Welch. Choosing the sample size of a computer experiment: a practical guide. Journal of the American Statistical Association, 51(4):366–376, 2009.DOI
  8. [8]H. Luschgy and G. Pagès. Greedy vector quantization. Journal of Approximation Theory, 198:111–131, 2015.
  9. [9]M. Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Proc. 8th IFIP Conference, Würzburg (Part 2), pages 234–243. Springer, New-York, 1977.
  10. [10]A. Nogales Gómez, L. Pronzato, and M.-J. Rendas. Incremental space-filling design based on coverings and spacings: improving upon low discrepancy sequences. Journal of Statistical Theory and Practice, 15(4):77, 2021.arxiv.org/abs/2106.05833
  11. [11]J. Noonan and A. Zhigljavsky. Non-lattice covering and quantization of high dimensional sets. In P.M. Pardalos, V. Rasskazova, and M.N. Vrahatis, editors, Black Box Optimization, Machine Learning, and No-Free Lunch Theorems, pages 273–318. Springer, Cham, 2021.DOI
  12. [12]J. Noonan and A. Zhigljavsky. High-Dimensional Optimization: Set Exploration in the Non-Asymptotic Regime. Springer, 2024.DOI
  13. [13]J. Noonan and A. Zhigljavsky. Improving exploration strategies in large dimensions and rate of convergence of global random search algorithms. Journal of Global Optimization, 88(1):1–26, 2024.arxiv.org/abs/2208.11542
  14. [14]G. Pagès. A space quantization method for numerical integration. Journal of Computational and Applied Mathematics, 89(1):1–38, 1997.DOI
  15. [15]L. Pronzato and A. Zhigljavsky. Quasi-uniform designs with asymptotically optimal and near-optimal uniformity constant. Journal of Approximation Theory, 294(105931), 2023.arxiv.org/abs/2112.10401
  16. [16]L. Pronzato and A.A. Zhigljavsky. Optimal random quantisers for spherically symmetric distributions, 2026. hal-05786349, arXiv:2610.11772.arxiv.org/abs/2610.11772
  17. [17]M.K. Roychowdhury. Optimal quantizers for some absolutely continuous probability measures. Real Analysis Exchange, 43(1):105–136, 2017.
  18. [18]B. Shang and D.W. Apley. Full-sequential space-filling design algorithms for computer experiments. Journal of Quality Technology, 53(2):173–196, 2021.DOI
  19. [19]I. Weissman. Sum of squares of uniform random variables. Statistics & Probability Letters, 129:147–154, 2017.DOI
  20. [20]C.F.J. Wu and M.S. Hamada. Experiments: Planning Analysis, and Optimization. Wiley, New York, 2009. [2nd ed.].
  21. [21]P.L. Zador. Asymptotic quantization error of continuous signals and the quantization dimension. IEEE Trans. Inform. Theory, 28:139–149, 1982.DOI
  22. [22]A. Zhigljavsky and J. Noonan. Covering of high-dimensional cubes and quantization. SN Operations Research Forum, 1(3):18, 2020.arxiv.org/abs/2002.06118

Paper details

vlnc:W_rzbkgz6t
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents