Introduction
Let μ \mu μ be a probability measure on a compact subset X \mathcal{X} X of R d \mathbb{R}^d R d (with particular emphasis on the case where X \mathcal{X} X is the hypercube [ − 1 , 1 ] d [-1,1]^d [ − 1 , 1 ] d ), and let X n = { x 1 , … , x n } ∈ R n × d \mathbf{X}_n = \{x_1,\ldots,x_n\} \in\mathbb{R}^{n \times d} X n = { x 1 , … , x n } ∈ R n × d be a design of size n n n , i.e., an n n n -point set in X \mathcal{X} X . By high dimension, we mean the situation where n n n is typically smaller than 2 d 2^d 2 d , the number of vertices of the hypercube. For any s > 0 s > 0 s > 0 , the L s L_s L s -mean quantization error of μ \mu μ for X n \mathbf{X}_n X n is
E μ , s ( X n ) = ( E μ { min i = 1 , … , n ∥ U − x i ∥ 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}, E μ , s ( X n ) = ( E μ { i = 1 , … , n min ∥ U − x i ∥ s } ) 1/ s ,
where U ∼ d μ U \overset{d}{\sim} \mu U ∼ d μ . When μ \mu μ has the density φ \varphi φ with respect to the Lebesgue measure, Zador’s celebrated theorem [21 ] states that the empirical distribution of an n n n -point optimal quantizer X n ∗ \mathbf{X}_n^* X n ∗ minimizing E μ , s ( X n ) E_{\mu,s}(\mathbf{X}_n) E μ , s ( X n ) converges weakly, as n → ∞ n \to\infty n → ∞ , to the probability measure with density proportional to φ d / ( d + s ) \varphi^{d/(d+s)} φ d / ( d + s ) . It also characterizes the asymptotic value of n 1 / d E μ , s ( X n ∗ ) n^{1/d}E_{\mu,s}(\mathbf{X}_n^*) n 1/ d E μ , s ( X n ∗ ) . Note the connection with transport theory: for s ≥ 1 s \ge1 s ≥ 1 , E μ , s ( X n ∗ ) E_{\mu,s}(\mathbf{X}_n^*) E μ , s ( X n ∗ ) is the minimum Kantorovich (or Wasserstein) distance of order s s s between μ \mu μ and a measure with at most n n n support points; see [5 Lemma 3.4] . Designs with small quantization error are particularly relevant for numerical integration; see [14 ] .
The construction of an n n n -point optimal quantizer X n ∗ \mathbf{X}_n^* 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 d d d . When μ \mu μ is uniform on X \mathcal{X} X , the points of an optimal quantizer are asymptotically uniformly distributed for all s > 0 s > 0 s > 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 n 1 / d n^{1/d} n 1/ d is sufficiently large, which in large dimension requires astronomically large values of n n n . In fact, for large d d d and reasonable n n n , random designs uniformly distributed on specific subsets of X \mathcal{X} 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 [ − 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} X is the d d d -dimensional hypercube C d \mathcal{C}_d C d . In § 3.1 , we construct spherically symmetric approximations of measures on C d \mathcal{C}_d C d ; this yields an approximation of E μ , s s ( X n ) E_{\mu,s}^{s}(\mathbf{X}_n) E μ , s s ( X n ) for random designs X n \mathbf{X}_n 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 C d \mathcal{C}_d 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 C d \mathcal{C}_d 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 B d ( x , r ) \mathcal{B}_d(\mathbf{x},r) B d ( x , r ) the d d d -dimensional (closed) Euclidean ball with centre x \mathbf{x} x and radius r r r ; we write B d ( r ) = B d ( 0 d , r ) \mathcal{B}_d(r)=\mathcal{B}_d(\mathbf{0}_d,r) B d ( r ) = B d ( 0 d , r ) , and S d − 1 ( r ) \mathcal{S}_{d-1}(r) S d − 1 ( r ) denotes its ( d − 1 ) (d-1) ( d − 1 ) -dimensional boundary sphere; ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ is the ℓ 2 \ell_2 ℓ 2 -norm; u T \mathbf{u}^{\mathsf{T}} u T is the transpose of the column vector u \mathbf{u} u ; I d \mathbf{I}_d I d is the d d d -dimensional identity matrix.
Distance c.d.f., quantization error and distortion
Definitions and basic properties
For any n n n -point design X n \mathbf{X}_n X n we denote by d ( ⋅ , X n ) d(\cdot,\mathbf{X}_n) d ( ⋅ , X n ) the distance function defined by x ∈ R d ↦ d ( x , X n ) = min x i ∈ X n ∥ x − x i ∥ \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\| x ∈ R d ↦ d ( x , X n ) = min x i ∈ X n ∥ x − x i ∥ .
Definition 2.1. For X n X_n X n a fixed n n n -point set in R d \mathbb{R}^d R d and μ \mu μ a probability measure on R d \mathbb{R}^d R d , the distance c.d.f. F ( ⋅ ; X n , μ ) F(\cdot; X_n,\mu) F ( ⋅ ; X n , μ ) is the c.d.f. of the random variable d ( U , X n ) d(U,X_n) d ( U , X n ) where U ∼ d μ U \mathrel{\mathop{\sim}\limits^{d}} \mu U ∼ d μ :
F ( t ; X n , μ ) = μ { U ∈ ⋃ i = 1 n B d ( x i , t ) } = μ { d ( U , X n ) ≤ 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\}. F ( t ; X n , μ ) = μ { U ∈ i = 1 ⋃ n B d ( x i , t ) } = μ { d ( U , X n ) ≤ t } . For P n P_n P n a probability measure on R n × d \mathbb{R}^{n\times d} R n × d , the mean distance c.d.f. F ( ⋅ ; P n , μ ) F(\cdot;P_n,\mu) F ( ⋅ ; P n , μ ) is defined by F ( t ; P n , μ ) = E P n { F ( t ; R n , μ ) } F(t;P_n,\mu)=\mathbb{E}_{P_n}\{F(t;R_n,\mu)\} F ( t ; P n , μ ) = E P n { F ( t ; R n , μ )} , where R n R_n R n is a random n n n -point design generated with P n P_n P n .
If μ \mu μ is the delta measure δ u \delta_u δ u concentrated at u ∈ R d u\in\mathbb{R}^d u ∈ R d , the mean distance c.d.f. is simply F ( t ; P n , δ u ) = P n { d ( u , R n ) ≤ t } F(t;P_n,\delta_u)=P_n\{d(u,R_n)\leq t\} F ( t ; P n , δ u ) = P n { d ( u , R n ) ≤ t } . When μ \mu μ is equivalent to the Lebesgue measure on X \mathcal{X} X , the essential supremum of the random variable d ( U , X n ) d(U,X_n) d ( U , X n ) is equal to the covering radius CR ( X n ) = max x ∈ X d ( x , X n ) \operatorname{CR}(X_n)=\max_{x\in\mathcal{X}}d(x,X_n) CR ( X n ) = max x ∈ X d ( x , X n ) and F ( ⋅ ; X n , μ ) F(\cdot;X_n,\mu) F ( ⋅ ; X n , μ ) has a density f ( ⋅ ; X n , μ ) f(\cdot;X_n,\mu) f ( ⋅ ; X n , μ ) on [ 0 , CR ( X n ) ] [0,\operatorname{CR}(X_n)] [ 0 , CR ( X n )] . When μ \mu μ is the uniform measure on X \mathcal{X} X , the distance c.d.f. contains all information about the filling of X \mathcal{X} X by X n X_n X n . The L s L_s L s -mean quantization error of μ \mu μ for X n X_n X n [5 ] , or equivalently the ( μ , s ) (\mu,s) ( μ , s ) -distortion related to X n X_n X n [14 ] , provides a scalar summary of this information.
Definition 2.2. The L s L_s L s -mean quantization error of a probability measure μ \mu μ on R d \mathbb{R}^d R d with finite s s s -th moment E { ∥ X ∥ s } \mathbb{E}\{\lVert X\rVert^s\} E {∥ X ∥ s } for a given n n n -point design X n X_n X n is the L s ( μ ) L_s(\mu) L s ( μ ) -mean (and, when s ≥ 1 s\geq1 s ≥ 1 , the L s ( μ ) L_s(\mu) L s ( μ ) -norm) of the distance function d ( ⋅ , X n ) d(\cdot,X_n) d ( ⋅ , X n ) :
E μ , s ( X n ) = ∥ d ( ⋅ , X n ) ∥ L s = [ ∫ R d d s ( x , X n ) μ ( d x ) ] 1 / s , s > 0. E_{\mu,s}(X_n)=\lVert d(\cdot,X_n)\rVert_{L_s}=\left[\int_{\mathbb{R}^d}d^s(x,X_n)\,\mu(\mathrm{d}x)\right]^{1/s},\qquad s>0. E μ , s ( X n ) = ∥ d ( ⋅ , X n ) ∥ L s = [ ∫ R d d s ( x , X n ) μ ( d x ) ] 1/ s , s > 0. When X n ∼ d P n X_n\mathrel{\mathop{\sim}\limits^{d}}P_n X n ∼ d P n is random, we define the expected ( μ , s ) (\mu,s) ( μ , s ) -distortion as D μ , s ( P n ) = E P n { D μ , s ( X n ) } D_{\mu,s}(P_n)=\mathbb{E}_{P_n}\{D_{\mu,s}(X_n)\} D μ , s ( P n ) = E P n { D μ , s ( X n )} , where D μ , s ( X n ) D_{\mu,s}(X_n) D μ , s ( X n ) is the ( μ , s ) (\mu,s) ( μ , s ) -distortion related to X n X_n X n , defined by D μ , s ( X n ) = E μ , s s ( X n ) D_{\mu,s}(X_n)=E_{\mu,s}^s(X_n) D μ , s ( X n ) = E μ , s s ( X n ) .
For any s > 0 s>0 s > 0 , the ( μ , s ) (\mu,s) ( μ , s ) -distortion satisfies (see, e.g., [4 p. 150] ):
D μ , s ( X n ) = E μ { d s ( U , X n ) } = s ∫ 0 ∞ t s − 1 [ 1 − F ( t ; X n , μ ) ] d t , = ∫ 0 ∞ [ 1 − F ( t 1 / s ; X n , μ ) ] d t . (1) \begin{aligned}
D_{\mu,s}(X_n)&=\mathbb{E}_{\mu}\{d^s(U,X_n)\}=s\int_{0}^{\infty}t^{s-1}[1-F(t;X_n,\mu)]\,\mathrm{d}t,\\
&=\int_{0}^{\infty}[1-F(t^{1/s};X_n,\mu)]\,\mathrm{d}t. \tag*{(1)}
\end{aligned} D μ , s ( X n ) = E μ { d s ( U , X n )} = s ∫ 0 ∞ t s − 1 [ 1 − F ( t ; X n , μ )] d t , = ∫ 0 ∞ [ 1 − F ( t 1/ s ; X n , μ )] d t . (1) showing that D μ , s ( X n ) D_{\mu,s}(X_n) D μ , s ( X n ) corresponds to the area between the curve t ↦ F ( t 1 / s ; X n , μ ) t\mapsto F(t^{1/s};X_n,\mu) t ↦ F ( t 1/ s ; X n , μ ) for t ∈ R + t\in\mathbb{R}^{+} t ∈ R + and the horizontal asymptote y = 1 y=1 y = 1 . As a direct consequence of properties of L s L_s L s norms, for any n n n -point design and probability measure μ \mu μ , E μ , s ( X n ) ≤ E μ , s ′ ( X n ) E_{\mu,s}(X_n)\leq E_{\mu,s'}(X_n) E μ , s ( X n ) ≤ E μ , s ′ ( X n ) for 0 < s < s ′ 0<s<s' 0 < s < s ′ (equality is possible when d ( U , X n ) d(U,X_n) d ( U , X n ) is μ \mu μ -almost surely constant). When μ \mu μ is equivalent to the Lebesgue measure on X \mathcal{X} X , lim s → ∞ E μ , s ( X n ) = CR ( X n ) \lim_{s\to\infty}E_{\mu,s}(X_n)=\operatorname{CR}(X_n) lim s → ∞ E μ , s ( X n ) = CR ( X n ) . Moreover, Lemma 10.1 in [5 ] indicates that, for any n n n -point optimal quantizer X n ∗ X_n^* X n ∗ , E μ , s ( X n ∗ ) → min X n ∈ R n × d CR ( X n ) E_{\mu,s}(X_n^*)\to\min_{X_n\in\mathbb{R}^{n\times d}}\operatorname{CR}(X_n) E μ , s ( X n ∗ ) → min X n ∈ R n × d CR ( X n ) as s → ∞ s\to\infty s → ∞ for any fixed n n n , showing that, for large s s s , optimal n n n -quantizers are almost minimax-optimal.
In contrast, the n n n balls B d ( x i , CR ( X n ) ) \mathcal{B}_d(x_i,\operatorname{CR}(X_n)) B d ( x i , CR ( X n )) cover the entire X \mathcal{X} X : when γ \gamma γ is close to 1, partial covering ignores parts of X \mathcal{X} X that may be difficult to cover (such as corners when X \mathcal{X} X is a hypercube) and focuses on the main bulk of X \mathcal{X} X .
However, quantiles are more challenging to handle than the L s L_s L s -mean quantization error. Moreover, when considering the distance c.d.f. for the uniform measure on a hypercube, we introduce an approximation involving a non-uniform spherically symmetric distribution (see § 3.1 ), and covering quantiles are then less meaningful.
Quantization error of random quantizers
Consider the expected ( μ , s ) (\mu,s) ( μ , s ) -distortion D μ , s ( P n ) D_{\mu,s}(\mathbb{P}_n) D μ , s ( P n ) defined in Definition 2.2 , which we want to minimize with respect to P n \mathbb{P}_n P n . From (1), we can write
D μ , s ( P n ) = s ∫ t ≥ 0 t s − 1 [ 1 − F ( t ; P n , μ ) ] d t , (2) D_{\mu,s}(\mathbb{P}_n)=s\int_{t\geq0}t^{s-1}\left[1-F(t;\mathbb{P}_n,\mu)\right]\mathrm{d}t, \tag*{(2)} D μ , s ( P n ) = s ∫ t ≥ 0 t s − 1 [ 1 − F ( t ; P n , μ ) ] d t , (2)
where F ( ⋅ ; P n , μ ) = E P n { F ( ⋅ ; X n , μ ) } F(\cdot;\mathbb{P}_n,\mu)=\mathbb{E}_{\mathbb{P}_n}\{F(\cdot;X_n,\mu)\} F ( ⋅ ; P n , μ ) = E P n { F ( ⋅ ; X n , μ )} with X n ∼ d P n X_n\mathrel{\overset{d}{\sim}}\mathbb{P}_n X n ∼ d P n is the mean distance c.d.f. of Definition 2.1 ; that is, the c.d.f. of the random variable d ( U , X n ) d(U,X_n) d ( U , X n ) where both U U U and X n X_n X n are random. Note that E P n { E μ , s ( X n ) } ≤ [ D μ , s ( P n ) ] 1 / s \mathbb{E}_{\mathbb{P}_n}\{E_{\mu,s}(X_n)\}\leq[D_{\mu,s}(\mathbb{P}_n)]^{1/s} E P n { E μ , s ( X n )} ≤ [ D μ , s ( P n ) ] 1/ s for s ≥ 1 s\geq1 s ≥ 1 by Jensen’s inequality, which provides an upper bound on the expected quantization error1 ^{1} 1 .
By swapping the order of expectations in F ( ⋅ ; P n , μ ) = E P n { F ( ⋅ ; X n , μ ) } F(\cdot;\mathbb{P}_n,\mu)=\mathbb{E}_{\mathbb{P}_n}\{F(\cdot;X_n,\mu)\} F ( ⋅ ; P n , μ ) = E P n { F ( ⋅ ; X n , μ )} , we get
F ( t ; P n , μ ) = E μ { F ( t ; P n , δ U ) } , (3) F(t;\mathbb{P}_n,\mu)=\mathbb{E}_{\mu}\{F(t;\mathbb{P}_n,\delta_U)\}, \tag*{(3)} F ( t ; P n , μ ) = E μ { F ( t ; P n , δ U )} , (3)
where F ( t ; P n , δ u ) = P n { d ( u , R n ) ≤ t } F(t;\mathbb{P}_n,\delta_u)=\mathbb{P}_n\{d(u,R_n)\leq t\} F ( t ; P n , δ u ) = P n { d ( u , R n ) ≤ t } . From now on, we only consider random quantizers with i.i.d. points having some distribution P \mathbb{P} P , so that P n ( d x 1 , … , d x n ) = ∏ i = 1 n P ( d x i ) \mathbb{P}_n(\mathrm{d}x_1,\ldots,\mathrm{d}x_n)=\prod_{i=1}^{n}\mathbb{P}(\mathrm{d}x_i) P n ( d x 1 , … , d x n ) = ∏ i = 1 n P ( d x i ) . We then denote P n = P [ n ] \mathbb{P}_n=\mathbb{P}^{[n]} P n = P [ n ] .
For any fixed u ∈ R d u\in\mathbb{R}^d u ∈ R d , any t ≥ 0 t\geq0 t ≥ 0 and any X n X_n X n with n n n i.i.d. points x i ∼ d P x_i\mathrel{\overset{d}{\sim}}\mathbb{P} x i ∼ d P , an elementary calculation (see [16 ] ) shows that
F ( t ; P [ n ] , δ u ) = 1 − ( 1 − P { ∥ X − u ∥ ≤ t } ) n , (4) F(t;\mathbb{P}^{[n]},\delta_u)=1-\left(1-\mathbb{P}\{\lVert X-u\rVert\leq t\}\right)^n, \tag*{(4)} F ( t ; P [ n ] , δ u ) = 1 − ( 1 − P {∥ X − u ∥ ≤ t } ) n , (4)
where X ∼ d P X\mathrel{\overset{d}{\sim}}\mathbb{P} X ∼ d P . Calculating the mean distance c.d.f. F ( t ; P [ n ] , μ ) F(t;\mathbb{P}^{[n]},\mu) F ( t ; P [ n ] , μ ) through (3) and then calculating the expected ( μ , s ) (\mu,s) ( μ , s ) -distortion D μ , s ( P [ n ] ) D_{\mu,s}(\mathbb{P}^{[n]}) D μ , s ( P [ n ] ) through (2) yields
D μ , s ( P [ n ] ) = s ∫ t ≥ 0 t s − 1 E μ { ( 1 − P { ∥ X − U ∥ ≤ t } ) n } d t . (5) D_{\mu,s}(\mathbb{P}^{[n]})=s\int_{t\geq0}t^{s-1}\mathbb{E}_{\mu}\left\{\left(1-\mathbb{P}\{\lVert X-U\rVert\leq t\}\right)^n\right\}\mathrm{d}t. \tag*{(5)} D μ , s ( P [ n ] ) = s ∫ t ≥ 0 t s − 1 E μ { ( 1 − P {∥ X − U ∥ ≤ t } ) n } d t . (5)
As shown in [16 ] , when P \mathbb{P} P is spherically symmetric, D μ , s ( P [ n ] ) D_{\mu,s}(\mathbb{P}^{[n]}) D μ , s ( P [ n ] ) admits an explicit representation involving three integrals. This result is summarized in the next section. The case where μ \mu μ is uniform on a hypercube requires some approximations and is addressed in § 3 .
P \mathbb{P} P is spherically symmetric
Assume that P \mathbb{P} P is spherically symmetric. By definition, the random vector X = ( X 1 , … , X d ) ∼ d P X=(X_1,\ldots,X_d)\mathrel{\overset{d}{\sim}}\mathbb{P} X = ( X 1 , … , X d ) ∼ d P can be represented as X = d R ⋅ Z ( d ) X\mathrel{\overset{d}{=}}R\cdot Z^{(d)} X = d R ⋅ Z ( d ) , where R = ∥ X ∥ R=\lVert X\rVert R = ∥ X ∥ , Z ( d ) = ( Z 1 , … , Z d ) Z^{(d)}=(Z_1,\ldots,Z_d) Z ( d ) = ( Z 1 , … , Z d ) is uniformly distributed on the unit sphere S d − 1 ( 1 ) S_{d-1}(1) S d − 1 ( 1 ) , and R R R and Z ( d ) Z^{(d)} Z ( d ) are independent. Let Φ ( ⋅ ) \Phi(\cdot) Φ ( ⋅ ) denote the c.d.f. of R = ∥ X ∥ R = \lVert X\rVert R = ∥ X ∥ and β a , b \beta_{a,b} β a , b denote a random variable with the beta density
φ a , b ( t ) = t a − 1 ( 1 − t ) b − 1 / B ( a , b ) for 0 ≤ t ≤ 1 , \varphi_{a,b}(t) = t^{a-1}(1-t)^{b-1}/B(a,b) \quad\text{for } 0 \le t \le1, φ a , b ( t ) = t a − 1 ( 1 − t ) b − 1 / B ( a , b ) for 0 ≤ t ≤ 1 ,
where a , b > 0 a,b > 0 a , b > 0 and B ( a , b ) = Γ ( a ) Γ ( b ) / Γ ( a + b ) B(a,b) = \Gamma(a)\Gamma(b)/\Gamma(a+b) B ( a , b ) = Γ ( a ) Γ ( b ) /Γ ( a + b ) is the beta function. The c.d.f. of β a , b \beta_{a,b} β a , b is Prob { β a , b ≤ t } = I t ( a , b ) \operatorname{Prob}\{\beta_{a,b} \le t\} = I_t(a,b) Prob { β a , b ≤ t } = I t ( a , b ) , where I t ( a , b ) I_t(a,b) I t ( a , b ) is the regularized incomplete beta function, for which we use the convention
I t ( ⋅ , ⋅ ) = { 0 for t ≤ 0 , 1 for t ≥ 1. (6) I_t(\cdot,\cdot) =
\begin{cases}
0 & \text{for } t \le0,\\
1 & \text{for } t \ge1.
\end{cases} \tag*{(6)} I t ( ⋅ , ⋅ ) = { 0 1 for t ≤ 0 , for t ≥ 1. (6)
As P \mathbb{P} P is spherically symmetric, the distribution of ∥ X − u ∥ \lVert X-u\rVert ∥ X − u ∥ for X ∼ d P X \mathrel{\overset{d}{\sim}} \mathbb{P} X ∼ d P only depends on ∥ u ∥ \lVert u\rVert ∥ u ∥ and d d d (see [16 Prop. 2.1] ): when d ≥ 2 d \ge2 d ≥ 2 , for any fixed u ∈ R d u \in\mathbb{R}^d u ∈ R d we have
∥ X − u ∥ 2 = d ( ∥ u ∥ − R ) 2 + 4 ∥ u ∥ R β d ~ , d ~ , (7) \lVert X-u\rVert^2 \mathrel{\overset{d}{=}} (\lVert u\rVert-R)^2+4\lVert u\rVert R\beta_{\widetilde d,\widetilde d}, \tag*{(7)} ∥ X − u ∥ 2 = d (∥ u ∥ − R ) 2 + 4 ∥ u ∥ R β d , d , (7)
where d ~ = ( d − 1 ) / 2 \widetilde d=(d-1)/2 d = ( d − 1 ) /2 and the random variables R = ∥ X ∥ R=\lVert X\rVert R = ∥ X ∥ and β d ~ , d ~ \beta_{\widetilde d,\widetilde d} β d , d are independent. After some calculation, this gives
D μ , s ( P [ n ] ) = s ∫ t ≥ 0 t s − 1 ∫ r ≥ 0 H ( r , t ; Φ , n ) d Ψ ( r ) d t , (8) D_{\mu,s}(\mathbb{P}^{[n]})=s\int_{t\ge0}t^{s-1}\int_{r\ge0}H(r,t;\Phi,n)\,\mathrm{d}\Psi(r)\,\mathrm{d}t, \tag*{(8)} D μ , s ( P [ n ] ) = s ∫ t ≥ 0 t s − 1 ∫ r ≥ 0 H ( r , t ; Φ , n ) d Ψ ( r ) d t , (8)
where
H ( r , t ; Φ , n ) = ( 1 − ∫ ρ ≥ 0 I ν ( d ~ , d ~ ) d Φ ( ρ ) ) n (9) H(r,t;\Phi,n)=\left(1-\int_{\rho\ge0}I_\nu(\widetilde d,\widetilde d)\,\mathrm{d}\Phi(\rho)\right)^n \tag*{(9)} H ( r , t ; Φ , n ) = ( 1 − ∫ ρ ≥ 0 I ν ( d , d ) d Φ ( ρ ) ) n (9)
with
ν = ν ( t , ρ , r ) = t 2 − ( ρ − r ) 2 4 ρ r , (10) \nu=\nu(t,\rho,r)=\frac{t^2-(\rho-r)^2}{4\rho r}, \tag*{(10)} ν = ν ( t , ρ , r ) = 4 ρ r t 2 − ( ρ − r ) 2 , (10)
and where Ψ ( ⋅ ) \Psi(\cdot) Ψ ( ⋅ ) is the c.d.f. of ∥ U ∥ \lVert U\rVert ∥ U ∥ for U ∼ d μ U \mathrel{\overset{d}{\sim}} \mu U ∼ d μ . Here μ \mu μ does not need to be spherically symmetric, but Ψ ( ⋅ ) \Psi(\cdot) Ψ ( ⋅ ) can be challenging to derive in general cases. For that reason, in Section 3.1 we use a spherically symmetric approximation of μ \mu μ uniform on [ − 1 , 1 ] d [-1,1]^d [ − 1 , 1 ] d .
Quantization error in d d d -dimensional hypercubes
Without loss of generality, we restrict our attention to the unit cube C d = [ − 1 , 1 ] d \mathcal{C}_d=[-1,1]^d C d = [ − 1 , 1 ] d . The case of an arbitrary cube can be addressed by applying a suitable linear rescaling. For any δ > 0 \delta>0 δ > 0 , we denote by δ C d \delta\mathcal{C}_d δ C d the hypercube [ − δ , δ ] d [-\delta,\delta]^d [ − δ , δ ] d . We only consider the case where the measure μ \mu μ is uniform on C d \mathcal{C}_d C d .
Spherically symmetric approximations of measures in C d \mathcal{C}_d C d
A family of product measures in C d \mathcal{C}_d C d
Product measures are well-suited for working in C d \mathcal{C}_d C d , and we consider the family of symmetric distributions defined by the product measures formed from symmetric Betaδ ( α , α ) _\delta(\alpha,\alpha) δ ( α , α ) distributions on [ − δ , δ ] [-\delta,\delta] [ − δ , δ ] with α > 0 \alpha>0 α > 0 and δ ∈ ( 0 , 1 ] \delta\in(0,1] δ ∈ ( 0 , 1 ] , together with their limiting cases α = 0 \alpha=0 α = 0 and δ = 0 \delta=0 δ = 0 . For α > 0 \alpha>0 α > 0 , δ > 0 \delta>0 δ > 0 , and x = ( x 1 , … , x d ) x=(x_1,\ldots,x_d) x = ( x 1 , … , x d ) , P ( d x ) = P α , δ ( d x ) = ∏ i = 1 d p α , δ ( x i ) d x i \mathbb{P}(\mathrm{d}x)=\mathbb{P}_{\alpha,\delta}(\mathrm{d}x)=\prod_{i=1}^d p_{\alpha,\delta}(x_i)\,\mathrm{d}x_i P ( d x ) = P α , δ ( d x ) = ∏ i = 1 d p α , δ ( x i ) d x i , where
p α , δ ( t ) = ( 2 δ ) 1 − 2 α B ( α , α ) [ δ 2 − t 2 ] α − 1 , − δ ≤ t ≤ δ . p_{\alpha,\delta}(t)=\frac{(2\delta)^{1-2\alpha}}{B(\alpha,\alpha)}[\delta^2-t^2]^{\alpha-1},\quad-\delta\le t\le\delta. p α , δ ( t ) = B ( α , α ) ( 2 δ ) 1 − 2 α [ δ 2 − t 2 ] α − 1 , − δ ≤ t ≤ δ .
If X n ∼ d P α , δ [ n ] \mathbf{X}_{n} \mathrel{\mathop{\sim}\limits^{d}} \mathrm{P}_{\alpha,\delta}^{[n]} X n ∼ d P α , δ [ n ] , then each point x i ∈ X n \mathbf{x}_{i} \in\mathcal{X}_{n} x i ∈ X n has d d d i.i.d. coordinates with density p α , δ ( ⋅ ) p_{\alpha,\delta}(\cdot) p α , δ ( ⋅ ) . The case α = 0 \alpha= 0 α = 0 corresponds to a sampling scheme where each coordinate of x i ∈ X n \mathbf{x}_{i} \in\mathcal{X}_{n} x i ∈ X n takes the value ± δ \pm\delta ± δ with probability 1 / 2 1/2 1/2 . For practical applications, to avoid duplicate points, we shall assume that n ≤ 2 d n \leq2^{d} n ≤ 2 d and use sampling without replacement; other, more efficient sampling schemes will also be considered; see § 6 . The choice α = δ = 1 \alpha= \delta= 1 α = δ = 1 corresponds to independent uniform sampling in C d \mathcal{C}_{d} C d , with P 1 , 1 = μ \mathrm{P}_{1,1} = \mu P 1 , 1 = μ . For fixed d d d and n → ∞ n \to\infty n → ∞ , Zador’s theorem implies that the empirical measure of optimal quantizers converges to the uniform distribution. This concerns optimal quantizers; it does not by itself establish the asymptotic optimality of i.i.d. uniform random designs4 . For α > 1 \alpha> 1 α > 1 , p α , δ ( − δ ) = p α , δ ( δ ) = 0 p_{\alpha,\delta}(-\delta) = p_{\alpha,\delta}(\delta) = 0 p α , δ ( − δ ) = p α , δ ( δ ) = 0 and P α , δ \mathrm{P}_{\alpha,\delta} P α , δ places less mass near the boundary of C d \mathcal{C}_{d} C d , so we restrict attention to α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] .
Our objective is to minimize D μ , s ( P α , δ [ n ] ) D_{\mu,s}(\mathrm{P}_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) with respect to α \alpha α and δ \delta δ , with α , δ ∈ [ 0 , 1 ] \alpha,\delta\in[0,1] α , δ ∈ [ 0 , 1 ] . Although this expected distortion is not available in closed form, it can be approximated using the results of Section 2.3. To do so, we first need to construct a spherically symmetric approximation of P α , δ \mathrm{P}_{\alpha,\delta} P α , δ (and in particular of P 1 , 1 = μ \mathrm{P}_{1,1} = \mu P 1 , 1 = μ ).
Spherically symmetric substitutes
Let λ S O ( d ) \lambda_{SO(d)} λ S O ( d ) denote the Haar probability measure on the special orthogonal group S O ( d ) SO(d) S O ( d ) of rotations in R d \mathbb{R}^{d} R d . For any probability measure P \mathrm{P} P on C d \mathcal{C}_{d} C d , consider the product measure P ⊗ λ S O ( d ) \mathrm{P} \otimes\lambda_{SO(d)} P ⊗ λ S O ( d ) on C d × S O ( d ) \mathcal{C}_{d} \times SO(d) C d × S O ( d ) and the symmetrized measure P ‾ \overline{\mathrm{P}} P given by the pushforward of P ⊗ λ S O ( d ) \mathrm{P} \otimes\lambda_{SO(d)} P ⊗ λ S O ( d ) under the transformation T ( R , x ) = R x T(\mathbf{R},\mathbf{x}) = \mathbf{R}\mathbf{x} T ( R , x ) = Rx , R ∈ S O ( d ) \mathbf{R} \in SO(d) R ∈ S O ( d ) , x ∈ R d \mathbf{x} \in\mathbb{R}^{d} x ∈ R d :
P ‾ = T # ( P ⊗ λ S O ( d ) ) . (11) \overline{\mathrm{P}} = T_{\#}\left(\mathrm{P} \otimes\lambda_{SO(d)}\right). \tag*{(11)} P = T # ( P ⊗ λ S O ( d ) ) . (11)
This spherical symmetrization applied to any P α , δ \mathrm{P}_{\alpha,\delta} P α , δ yields a spherically symmetric measure P ‾ α , δ \overline{\mathrm{P}}_{\alpha,\delta} P α , δ . However, P ‾ α , δ \overline{\mathrm{P}}_{\alpha,\delta} P α , δ is difficult to determine for general α , δ \alpha,\delta α , δ in [ 0 , 1 ] [0,1] [ 0 , 1 ] , and below we consider an approximation Q α , δ \mathrm{Q}_{\alpha,\delta} Q α , δ of P ‾ α , δ \overline{\mathrm{P}}_{\alpha,\delta} P α , δ , based on moment-matching for ∥ X − u ∥ 2 j \lVert X-u\rVert^{2j} ∥ X − u ∥ 2 j , with j = 1 , 2 , 3 j = 1,2,3 j = 1 , 2 , 3 and u u u an arbitrary vector in R d \mathbb{R}^{d} R d . It relies on the following result.
Theorem 3.1. [12 Ths. 1.2 & 1.3] Assume that d ≥ 3 d \geq3 d ≥ 3 and X = ( X 1 , … , X d ) ∈ R d X = (X_{1}, \ldots, X_{d}) \in\mathbb{R}^{d} X = ( X 1 , … , X d ) ∈ R d is a random vector satisfying either of the two models:
(i) the components X i X_{i} X i of X X X are i.i.d. with a symmetric distribution having finite moments E { X 1 ℓ } \mathrm{E}\{X_{1}^{\ell}\} E { X 1 ℓ } for ℓ ≤ 6 \ell\leq6 ℓ ≤ 6 ;
(ii) X X X has a spherically symmetric distribution with E { ∥ X ∥ 6 } < ∞ \mathrm{E}\{\lVert X\rVert^{6}\} < \infty E {∥ X ∥ 6 } < ∞ .
Then, for any u ∈ R d u \in\mathbb{R}^{d} u ∈ R d , we have:
E { ∥ X − u ∥ 2 } = E { ∥ X ∥ 2 } + ∥ u ∥ 2 , E { ∥ X − u ∥ 4 } = E { ∥ X ∥ 4 } + ∥ u ∥ 4 + ( 2 + 4 / d ) ∥ u ∥ 2 E { ∥ X ∥ 2 } , E { ∥ X − u ∥ 6 } = E { ∥ X ∥ 6 } + ∥ u ∥ 6 + ( 3 + 12 / d ) [ ∥ u ∥ 2 E { ∥ X ∥ 4 } + ∥ u ∥ 4 E { ∥ X ∥ 2 } ] . \begin{aligned}
\mathrm{E}\{\lVert X-u\rVert^{2}\} & = \mathrm{E}\{\lVert X\rVert^{2}\} + \lVert u\rVert^{2},\\
\mathrm{E}\{\lVert X-u\rVert^{4}\} & = \mathrm{E}\{\lVert X\rVert^{4}\} + \lVert u\rVert^{4} + (2 + 4/d)\lVert u\rVert^{2}\mathrm{E}\{\lVert X\rVert^{2}\},\\
\mathrm{E}\{\lVert X-u\rVert^{6}\} & = \mathrm{E}\{\lVert X\rVert^{6}\} + \lVert u\rVert^{6} + (3 + 12/d)\left[\lVert u\rVert^{2}\mathrm{E}\{\lVert X\rVert^{4}\} + \lVert u\rVert^{4}\mathrm{E}\{\lVert X\rVert^{2}\}\right].
\end{aligned} E {∥ X − u ∥ 2 } E {∥ X − u ∥ 4 } E {∥ X − u ∥ 6 } = E {∥ X ∥ 2 } + ∥ u ∥ 2 , = E {∥ X ∥ 4 } + ∥ u ∥ 4 + ( 2 + 4/ d ) ∥ u ∥ 2 E {∥ X ∥ 2 } , = E {∥ X ∥ 6 } + ∥ u ∥ 6 + ( 3 + 12/ d ) [ ∥ u ∥ 2 E {∥ X ∥ 4 } + ∥ u ∥ 4 E {∥ X ∥ 2 } ] .
The assumptions d ≥ 3 d \geq3 d ≥ 3 , E { X 1 6 } < ∞ \mathrm{E}\{X_{1}^{6}\} < \infty E { X 1 6 } < ∞ and E { ∥ X ∥ 6 } < ∞ \mathrm{E}\{\lVert X\rVert^{6}\} < \infty E {∥ X ∥ 6 } < ∞ in Theorem 3.1 are required for the expressions of E { ∥ X − u ∥ 6 } \mathrm{E}\{\lVert X-u\rVert^{6}\} E {∥ X − u ∥ 6 } , but the expressions for E { ∥ X − u ∥ 2 } \mathrm{E}\{\lVert X-u\rVert^{2}\} E {∥ X − u ∥ 2 } and E { ∥ X − u ∥ 4 } \mathrm{E}\{\lVert X-u\rVert^{4}\} E {∥ X − u ∥ 4 } are valid for all d ≥ 1 d \geq1 d ≥ 1 and d ≥ 2 d \geq2 d ≥ 2 , respectively, when the requirements on the moments are relaxed accordingly. Expressions for E { ∥ X − u ∥ 8 } \mathrm{E}\{\lVert X-u\rVert^{8}\} E {∥ X − u ∥ 8 } are also available for product and spherically symmetric measures, but they do not coincide; see [12 Th. 1.4] .
When X ∼ d P α , δ X \mathrel{\mathop{\sim}\limits^{d}} \mathrm{P}_{\alpha,\delta} X ∼ d P α , δ , the first three moments of ∥ X ∥ 2 \lVert X\rVert^{2} ∥ X ∥ 2 are known explicitly from the formulas for the moments of beta-distributed random variables; they are given in the following lemma.
Lemma 3.1. Let d ≥ 3 d \ge3 d ≥ 3 and X ∼ d P α , δ X \sim^{d} \mathbb{P}_{\alpha,\delta} X ∼ d P α , δ . Then
E { ∥ X ∥ 2 } = d ν 2 , E { ∥ X ∥ 4 } = d [ ν 4 + ( d − 1 ) ν 2 2 ] , E { ∥ X ∥ 6 } = d [ ν 6 + 3 ( d − 1 ) ν 2 ν 4 + ( d − 1 ) ( d − 2 ) ν 2 3 ] . \begin{aligned}
\mathbb{E}\{\lVert X\rVert^{2}\} &= d\nu_{2},\\
\mathbb{E}\{\lVert X\rVert^{4}\} &= d\left[\nu_{4}+(d-1)\nu_{2}^{2}\right],\\
\mathbb{E}\{\lVert X\rVert^{6}\} &= d\left[\nu_{6}+3(d-1)\nu_{2}\nu_{4}+(d-1)(d-2)\nu_{2}^{3}\right].
\end{aligned} E {∥ X ∥ 2 } E {∥ X ∥ 4 } E {∥ X ∥ 6 } = d ν 2 , = d [ ν 4 + ( d − 1 ) ν 2 2 ] , = d [ ν 6 + 3 ( d − 1 ) ν 2 ν 4 + ( d − 1 ) ( d − 2 ) ν 2 3 ] . where ν 2 = δ 2 / ( 1 + 2 α ) \nu_{2}=\delta^{2}/(1+2\alpha) ν 2 = δ 2 / ( 1 + 2 α ) , ν 4 = 3 δ 4 / [ ( 1 + 2 α ) ( 2 α + 3 ) ] \nu_{4}=3\delta^{4}/[(1+2\alpha)(2\alpha+3)] ν 4 = 3 δ 4 / [( 1 + 2 α ) ( 2 α + 3 )] , and ν 6 = 15 δ 6 / [ ( 1 + 2 α ) ( 2 α + 3 ) ( 2 α + 5 ) ] \nu_{6}=15\delta^{6}/[(1+2\alpha)(2\alpha+3)(2\alpha+5)] ν 6 = 15 δ 6 / [( 1 + 2 α ) ( 2 α + 3 ) ( 2 α + 5 )] .
Our family of spherically symmetric approximations is constructed as follows. Let ∥ X ∥ 2 \lVert X\rVert^{2} ∥ X ∥ 2 have the beta density φ ( ⋅ ; a , b ∣ M ) \varphi(\cdot;a,b\mid M) φ ( ⋅ ; a , b ∣ M ) on the interval ( 0 , M ) (0,M) ( 0 , M ) ,
φ ( t ; a , b ∣ M ) = t a − 1 ( M − t ) b − 1 M a + b − 1 B ( a , b ) , t ∈ ( 0 , M ) , a , b > 0 , (12) \varphi(t;a,b\mid M)=\frac{t^{a-1}(M-t)^{b-1}}{M^{a+b-1}B(a,b)},\qquad t\in(0,M),\ a,b>0, \tag*{(12)} φ ( t ; a , b ∣ M ) = M a + b − 1 B ( a , b ) t a − 1 ( M − t ) b − 1 , t ∈ ( 0 , M ) , a , b > 0 , (12)
where B ( ⋅ , ⋅ ) B(\cdot,\cdot) B ( ⋅ , ⋅ ) is the beta function. The first three moments of ∥ X ∥ 2 \lVert X\rVert^{2} ∥ X ∥ 2 are known in closed form. Matching them with those of P α , δ \mathbb{P}_{\alpha,\delta} P α , δ yields explicit expressions for a a a , b b b and M M M in terms of α \alpha α and δ \delta δ :
a ∗ = d 4 ( d + 2 ) α 2 + 4 ( 4 d − 1 ) α + 3 ( 5 d − 4 ) 8 α 2 ( d + 2 ) + 8 α ( 4 d − 1 ) + 6 d , (13) a_{*}=d\frac{4(d+2)\alpha^{2}+4(4d-1)\alpha+3(5d-4)}{8\alpha^{2}(d+2)+8\alpha(4d-1)+6d}, \tag*{(13)} a ∗ = d 8 α 2 ( d + 2 ) + 8 α ( 4 d − 1 ) + 6 d 4 ( d + 2 ) α 2 + 4 ( 4 d − 1 ) α + 3 ( 5 d − 4 ) , (13)
M ∗ = δ 2 4 ( d + 2 ) α 2 + 4 ( 4 d − 1 ) α + 3 d 3 ( 2 α + 1 ) 2 , (14) M_{*}=\delta^{2}\frac{4(d+2)\alpha^{2}+4(4d-1)\alpha+3d}{3(2\alpha+1)^{2}}, \tag*{(14)} M ∗ = δ 2 3 ( 2 α + 1 ) 2 4 ( d + 2 ) α 2 + 4 ( 4 d − 1 ) α + 3 d , (14)
b ∗ = a ∗ ( M ∗ ( 2 α + 1 ) δ 2 d − 1 ) . (15) b_{*}=a_{*}\left(\frac{M_{*}(2\alpha+1)}{\delta^{2}d}-1\right). \tag*{(15)} b ∗ = a ∗ ( δ 2 d M ∗ ( 2 α + 1 ) − 1 ) . (15)
We denote by Q α , δ \mathbb{Q}_{\alpha,\delta} Q α , δ the corresponding spherically symmetric approximation of P α , δ \mathbb{P}_{\alpha,\delta} P α , δ . The density of ∥ X ∥ \lVert X\rVert ∥ X ∥ for Q α , δ \mathbb{Q}_{\alpha,\delta} Q α , δ is φ α , δ ( t ) = 2 t φ ( t 2 ; a ∗ , b ∗ ∣ M ∗ ) \varphi_{\alpha,\delta}(t)=2t\varphi(t^{2};a_{*},b_{*}\mid M_{*}) φ α , δ ( t ) = 2 tφ ( t 2 ; a ∗ , b ∗ ∣ M ∗ ) , t ∈ [ 0 , M ∗ ] t\in[0,\sqrt{M_{*}}] t ∈ [ 0 , M ∗ ] , with φ ( ⋅ ; a , b ∣ M ) \varphi(\cdot;a,b\mid M) φ ( ⋅ ; a , b ∣ M ) given by (12). Note that a ∗ a_{*} a ∗ and b ∗ b_{*} b ∗ do not depend on δ \delta δ , which only affects the support of φ α , δ ( ⋅ ) \varphi_{\alpha,\delta}(\cdot) φ α , δ ( ⋅ ) .
The left panel of Figure 1 shows the evolutions of a ∗ a_{*} a ∗ , b ∗ b_{*} b ∗ and M ∗ M_{*} M ∗ with d d d for two choices of α \alpha α and δ \delta δ ; the right panel plots φ α , δ ( t ) \varphi_{\alpha,\delta}(t) φ α , δ ( t ) for the same choices of α \alpha α and δ \delta δ when d = 20 d=20 d = 20 . When α = 0 \alpha=0 α = 0 , a ∗ = ( 5 d − 4 ) / 2 a_{*}=(5d-4)/2 a ∗ = ( 5 d − 4 ) /2 , M ∗ = d δ 2 M_{*}=d\delta^{2} M ∗ = d δ 2 and b ∗ = 0 b_{*}=0 b ∗ = 0 , so that the distribution of ∥ X ∥ \lVert X\rVert ∥ X ∥ for Q 0 , δ \mathbb{Q}_{0,\delta} Q 0 , δ has the Dirac delta measure concentrated at M ∗ = δ d \sqrt{M_{*}}=\delta\sqrt{d} M ∗ = δ d . Note that a ∗ a_{*} a ∗ is decreasing in α \alpha α for all fixed d ≥ 2 d\ge2 d ≥ 2 , with lim α → ∞ a ∗ = d / 2 \lim_{\alpha\to\infty}a_{*}=d/2 lim α → ∞ a ∗ = d /2 , so that a ∗ > d / 2 a_{*}>d/2 a ∗ > d /2 for all α ≥ 0 \alpha\ge0 α ≥ 0 . Also, for any d ≥ 2 d\ge2 d ≥ 2 , b ∗ = 0 b_{*}=0 b ∗ = 0 for α = 0 \alpha=0 α = 0 and b ∗ > 1 b_{*}>1 b ∗ > 1 for α = 1 \alpha=1 α = 1 , and there exists α ∗ ∈ ( 0 , 1 ) \alpha^{*}\in(0,1) α ∗ ∈ ( 0 , 1 ) such that b ∗ = 1 b_{*}=1 b ∗ = 1 for α = α ∗ \alpha=\alpha^{*} α = α ∗ . For a ∗ > 1 / 2 a_{*}>1/2 a ∗ > 1/2 and b ∗ > 1 b_{*}>1 b ∗ > 1 , φ α , δ ( t ) \varphi_{\alpha,\delta}(t) φ α , δ ( t ) is maximum at t ^ = M ∗ ( 2 a ∗ − 1 ) / [ 2 ( a ∗ + b ∗ ) − 3 ] \hat{t}=\sqrt{M_{*}(2a_{*}-1)/[2(a_{*}+b_{*})-3]} t ^ = M ∗ ( 2 a ∗ − 1 ) / [ 2 ( a ∗ + b ∗ ) − 3 ] (which is increasing in a ∗ a_{*} a ∗ and decreasing in b ∗ b_{*} b ∗ ).
Figure 1. Left: a ∗ a_* a ∗ (- - -), b ∗ b_* b ∗ (· · ·) and M ∗ M_* M ∗ (—) as functions of d d d for α = 1 \alpha= 1 α = 1 , δ = 1 \delta= 1 δ = 1 (▼) and α = 0.1 \alpha= 0.1 α = 0.1 , δ = 0.6 \delta= 0.6 δ = 0.6 (●). Right: ϕ α , δ ( ⋅ ) \phi_{\alpha,\delta}(\cdot) ϕ α , δ ( ⋅ ) for d = 20 d = 20 d = 20 and α = 1 \alpha= 1 α = 1 , δ = 1 \delta= 1 δ = 1 (i.e., P α , δ = P 1 , 1 = μ \mathbb{P}_{\alpha,\delta} = \mathbb{P}_{1,1} = \mu P α , δ = P 1 , 1 = μ , ▼—▼) and α = 0.1 \alpha= 0.1 α = 0.1 , δ = 0.6 \delta= 0.6 δ = 0.6 (●—●); the right limit M ∗ \sqrt{M_*} M ∗ of the support is indicated.
This moment matching approach applied to a mixture P ( w , α , δ ) = ∑ i = 1 q w i P α i , δ i \mathbb{P}(\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\delta})=\sum_{i=1}^{q}w_{i}\mathbb{P}_{\alpha_{i},\delta_{i}} P ( w , α , δ ) = ∑ i = 1 q w i P α i , δ i (where α = ( α 1 , … , α q ) \boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{q}) α = ( α 1 , … , α q ) , δ = ( δ 1 , … , δ q ) \boldsymbol{\delta}=(\delta_{1},\ldots,\delta_{q}) δ = ( δ 1 , … , δ q ) and w = ( w 1 , … , w q ) \mathbf{w}=(w_{1},\ldots,w_{q}) w = ( w 1 , … , w q ) , with w i ≥ 0 w_{i}\ge0 w i ≥ 0 and ∑ i = 1 q w i = 1 \sum_{i=1}^{q}w_{i}=1 ∑ i = 1 q w i = 1 ) yields the mixture Q ( w , α , δ ) = ∑ i = 1 q w i Q α i , δ i \mathbb{Q}(\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\delta})=\sum_{i=1}^{q}w_{i}\mathbb{Q}_{\alpha_{i},\delta_{i}} Q ( w , α , δ ) = ∑ i = 1 q w i Q α i , δ i . For general α , δ \boldsymbol{\alpha},\boldsymbol{\delta} α , δ in [ 0 , 1 ] [0,1] [ 0 , 1 ] , Q α , δ \mathbb{Q}_{\alpha,\delta} Q α , δ does not coincide with the symmetrized measure P ‾ α , δ \overline{\mathbb{P}}_{\alpha,\delta} P α , δ defined by (11) . However, for any δ > 0 \delta>0 δ > 0 , we have Q 0 , δ = P ‾ 0 , δ \mathbb{Q}_{0,\delta}=\overline{\mathbb{P}}_{0,\delta} Q 0 , δ = P 0 , δ , and this property extends to mixtures: Q ( w , 0 q , δ ) = P ‾ ( w , 0 q , δ ) \mathbb{Q}(\mathbf{w},\mathbf{0}_{q},\boldsymbol{\delta})=\overline{\mathbb{P}}(\mathbf{w},\mathbf{0}_{q},\boldsymbol{\delta}) Q ( w , 0 q , δ ) = P ( w , 0 q , δ ) .
Spherically symmetric approximation of P 1 , 1 = μ \mathbb{P}_{1,1}=\mu P 1 , 1 = μ
A case of particular importance is when α = δ = 1 \alpha=\delta=1 α = δ = 1 , for which P 1 , 1 = μ \mathbb{P}_{1,1}=\mu P 1 , 1 = μ , uniform on C d \mathcal{C}_{d} C d . We then have
E { ∥ X ∥ 2 } = d 3 ; E { ∥ X ∥ 4 } = d 2 9 + 4 d 45 ; E { ∥ X ∥ 6 } = d 3 27 + 4 d 2 45 + 16 d 945 , \mathbb{E}\{\lVert X\rVert^{2}\}=\frac{d}{3};\qquad\mathbb{E}\{\lVert X\rVert^{4}\}=\frac{d^{2}}{9}+\frac{4d}{45};\qquad\mathbb{E}\{\lVert X\rVert^{6}\}=\frac{d^{3}}{27}+\frac{4d^{2}}{45}+\frac{16d}{945}, E {∥ X ∥ 2 } = 3 d ; E {∥ X ∥ 4 } = 9 d 2 + 45 4 d ; E {∥ X ∥ 6 } = 27 d 3 + 45 4 d 2 + 945 16 d ,
and we approximate P 1 , 1 \mathbb{P}_{1,1} P 1 , 1 by a spherically symmetric Q 1 , 1 \mathbb{Q}_{1,1} Q 1 , 1 such that ∥ X ∥ 2 \lVert X\rVert^{2} ∥ X ∥ 2 has a density of the form (12). Denoting by φ 1 , 1 ( ⋅ ) \varphi_{1,1}(\cdot) φ 1 , 1 ( ⋅ ) the density of ∥ X ∥ \lVert X\rVert ∥ X ∥ , we get
φ 1 , 1 ( t ) = 2 t φ ( t 2 ; a d , b d ∣ M d ) , t ∈ [ 0 , M d ] , (16) \varphi_{1,1}(t)=2t\varphi(t^{2};a_{d},b_{d}\mid M_{d}),\qquad t\in[0,\sqrt{M_{d}}], \tag*{(16)} φ 1 , 1 ( t ) = 2 tφ ( t 2 ; a d , b d ∣ M d ) , t ∈ [ 0 , M d ] , (16)
where
a d = d ( 35 d − 8 ) 2 ( 23 d + 4 ) , b d = ( 7 d + 2 ) ( 35 d − 8 ) 9 ( 23 d + 4 ) , M d = 23 d + 4 27 . (17) a_d = \frac{d(35d-8)}{2(23d+4)}, \qquad b_d = \frac{(7d+2)(35d-8)}{9(23d+4)}, \qquad M_d = \frac{23d+4}{27}. \tag*{(17)} a d = 2 ( 23 d + 4 ) d ( 35 d − 8 ) , b d = 9 ( 23 d + 4 ) ( 7 d + 2 ) ( 35 d − 8 ) , M d = 27 23 d + 4 . (17)
These three parameters increase with d d d and satisfy a d > 1 / 2 a_d > 1/2 a d > 1/2 , b d > 1 b_d > 1 b d > 1 and M d > 1 M_d > 1 M d > 1 , so that ϕ 1 , 1 ( ⋅ ) \phi_{1,1}(\cdot) ϕ 1 , 1 ( ⋅ ) is maximum at t ^ = d / 3 + 4 / 105 \hat{t} = \sqrt{d/3} + 4/105 t ^ = d /3 + 4/105 .
Explicit expressions for the densities of ∥ X ∥ 2 \lVert X\rVert^2 ∥ X ∥ 2 when X ∼ d P 1 , 1 = μ X \mathrel{\overset{d}{\sim}} \mathbb{P}_{1,1} = \mu X ∼ d P 1 , 1 = μ in C d \mathbb{C}^d C d are derived in [19 ] for d = 2 , 3 , 4 d = 2, 3, 4 d = 2 , 3 , 4 , but for d ≥ 5 d \ge5 d ≥ 5 such explicit expressions remain unknown. Nevertheless, the asymptotic behavior can be easily derived. By the Central Limit Theorem (CLT), we have
1 d ( ∥ X ∥ 2 − d 3 ) → d N ( 0 , 4 45 ) , d → ∞ , (18) \frac{1}{\sqrt{d}}\left(\lVert X\rVert^2 - \frac{d}{3}\right) \mathrel{\overset{d}{\to}} \mathcal{N}\left(0,\frac{4}{45}\right), \qquad d \to\infty, \tag*{(18)} d 1 ( ∥ X ∥ 2 − 3 d ) → d N ( 0 , 45 4 ) , d → ∞ , (18)
and from Hoeffding’s inequality Prob { ∣ ∥ X ∥ 2 − d 3 ∣ > t } ≤ 2 exp ( − 2 t 2 d ) \operatorname{Prob}\left\{\left|\lVert X\rVert^2-\frac{d}{3}\right|>t\right\}\le2\exp\left(-\frac{2t^2}{d}\right) Prob { ∥ X ∥ 2 − 3 d > t } ≤ 2 exp ( − d 2 t 2 ) , showing that, for large d d d , the norm of a random point X ∼ d μ X \mathrel{\overset{d}{\sim}} \mu X ∼ d μ tends to be close to d / 3 \sqrt{d/3} d /3 . The asymptotic distribution (16) is already accurate for moderate d d d , the approximation φ ( ⋅ ; a d , b d ∣ M d ) \varphi(\cdot;a_d,b_d\mid M_d) φ ( ⋅ ; a d , b d ∣ M d ) , which matches exactly the first three moments of ∥ X ∥ 2 \lVert X\rVert^2 ∥ X ∥ 2 , is even more precise and the accuracy improves when d d d increases. Figure 2 gives an illustration.
Figure 2. Left: density of the standard normal distribution N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) (●); empirical (smoothed) density of 45 / ( 2 d ) ( ∥ X ∥ 2 − d / 3 ) \sqrt{45}/(2\sqrt{d})(\lVert X\rVert^2-d/3) 45 / ( 2 d ) (∥ X ∥ 2 − d /3 ) for d = 10 d=10 d = 10 , based on 10000 samples X i X_i X i i.i.d. with μ \mu μ (★—★); renormalized density 2 d / 45 φ ( 2 d / 45 t + d / 3 ; a d , b d ∣ M d ) 2\sqrt{d}/45\,\varphi(2\sqrt{d}/45\,t+d/3;a_d,b_d\mid M_d) 2 d /45 φ ( 2 d /45 t + d /3 ; a d , b d ∣ M d ) for d = 10 d=10 d = 10 (◆—◆) and d = 3 d=3 d = 3 (- - -). Right: distance in variation (●) and Hellinger distance (◆) between the beta distribution with density φ ( ⋅ ; a d , b d ∣ M d ) \varphi(\cdot;a_d,b_d\mid M_d) φ ( ⋅ ; a d , b d ∣ M d ) and the normal distribution N ( d / 3 , 4 d / 45 ) \mathcal{N}(d/3,4d/45) N ( d /3 , 4 d /45 ) as functions of d d d .
Approximation of the expected ( μ , s ) (\mu,s) ( μ , s ) -distortion D μ , s ( P α , δ [ n ] ) D_{\mu,s}(\mathbb{P}_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] )
The approximation is constructed in two steps. First, we replace P α , δ \mathbb{P}_{\alpha,\delta} P α , δ with its spherically symmetric approximation Q α , δ \mathbb{Q}_{\alpha,\delta} Q α , δ and compute the expected distortion D μ , s ( Q α , δ [ n ] ) D_{\mu,s}(\mathbb{Q}_{\alpha,\delta}^{[n]}) D μ , s ( Q α , δ [ n ] ) as in (8) . Second, we substitute Q 1 , 1 \mathbb{Q}_{1,1} Q 1 , 1 for μ \mu μ , i.e., we replace the c.d.f. Ψ ( ⋅ ) \Psi(\cdot) Ψ ( ⋅ ) in (8) with the c.d.f. corresponding to the density φ 1 , 1 ( ⋅ ) \varphi_{1,1}(\cdot) φ 1 , 1 ( ⋅ ) given by (16) . We denote the resulting approximation by
D ^ μ , s ( P α , δ [ n ] ) = D Q 1 , 1 , s ( Q α , δ [ n ] ) , (19) \widehat{D}_{\mu,s}(\mathbb{P}_{\alpha,\delta}^{[n]}) = D_{\mathbb{Q}_{1,1},s}(\mathbb{Q}_{\alpha,\delta}^{[n]}), \tag*{(19)} D μ , s ( P α , δ [ n ] ) = D Q 1 , 1 , s ( Q α , δ [ n ] ) , (19)
which we can then minimize with respect to α \alpha α and δ \delta δ .
In general, the calculation of D ^ μ , s ( P α , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) requires the evaluation of three nested integrals. The inner one corresponds to ∫ ρ ≥ 0 I ν ( d ~ , e ~ ) φ α , δ ( ρ ) d ρ \int_{\rho\ge0} I_{\nu}(\widetilde{d},\widetilde{e})\varphi_{\alpha,\delta}(\rho)\,d\rho ∫ ρ ≥ 0 I ν ( d , e ) φ α , δ ( ρ ) d ρ , see (9) , for which ρ \rho ρ varies in [ 0 , M ∗ ] [0,\sqrt{M_*}] [ 0 , M ∗ ] with M ∗ M_* M ∗ given by (14) . The expectation with respect to r r r in (8) is for r ∈ [ 0 , M d ] r \in[0,\sqrt{M_d}] r ∈ [ 0 , M d ] , see (17) . For the third integral (19) , we can restrict t t t to [ 0 , t ∗ ] [0,t_*] [ 0 , t ∗ ] with t ∗ t_* t ∗ such that ∫ 0 M ∗ I ν ( d ~ , d ~ ) φ α , δ ( ρ ) d ρ = 1 \int_{0}^{\sqrt{M_*}} I_\nu(\tilde d,\tilde d)\,\varphi_{\alpha,\delta}(\rho)\,d\rho=1 ∫ 0 M ∗ I ν ( d ~ , d ~ ) φ α , δ ( ρ ) d ρ = 1 for all r ∈ [ 0 , M d ] r\in[0,\sqrt{M_d}] r ∈ [ 0 , M d ] . From the convention (6) used for I ν ( d , d ~ ) I_\nu(d,\tilde d) I ν ( d , d ~ ) , it is enough to have ν = ν ( t ∗ , ρ , r ) ≥ 1 \nu=\nu(t_*,\rho,r)\geq1 ν = ν ( t ∗ , ρ , r ) ≥ 1 for all ρ \rho ρ and r r r , and the expression (10) for ν ( t , ρ , r ) \nu(t,\rho,r) ν ( t , ρ , r ) shows that t ∗ = M ∗ + M d t_*=\sqrt{M_*}+\sqrt{M_d} t ∗ = M ∗ + M d is suitable.
Let α ^ ∗ ( d , n , s ) \hat{\alpha}^*(d,n,s) α ^ ∗ ( d , n , s ) and δ ^ ∗ ( d , n , s ) \hat{\delta}^*(d,n,s) δ ^ ∗ ( d , n , s ) denote the optimal values of α \alpha α and δ \delta δ that minimize D ^ μ , s ( P α , δ [ n ] ) \widehat{D}_{\mu,s}(P_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) for given values of d d d , n n n and s s s . Their determination corresponds to a two-dimensional optimization problem, which can be solved numerically. At the same time, since Q α , δ Q_{\alpha,\delta} Q α , δ is spherically symmetric, we can exploit results from [16 ] on optimal random quantizers for spherically symmetric distributions. This is the topic of the next section.
Optimal spherically symmetric approximation
Consider the minimization of D Q 1 , 1 , s ( Q [ n ] ) D_{Q_{1,1},s}(Q^{[n]}) D Q 1 , 1 , s ( Q [ n ] ) with respect to a probability measure Q Q Q on R d \mathbb{R}^d R d . The expression (5) shows that D Q 1 , 1 , s ( Q [ n ] ) D_{Q_{1,1},s}(Q^{[n]}) D Q 1 , 1 , s ( Q [ n ] ) is convex in Q Q Q . As Q 1 , 1 Q_{1,1} Q 1 , 1 is spherically symmetric and D Q 1 , 1 , s ( Q [ n ] ) D_{Q_{1,1},s}(Q^{[n]}) D Q 1 , 1 , s ( Q [ n ] ) is invariant under rotation of Q Q Q , by a standard symmetrization argument there exists an optimal Q ∗ Q^* Q ∗ that is spherically symmetric. In [16 ] , a necessary and sufficient condition for the optimality of a spherically symmetric measure Q ∗ Q^* Q ∗ is derived, and it is shown that the support of Q ∗ Q^* Q ∗ is included in that of Q 1 , 1 Q_{1,1} Q 1 , 1 , here B d ( M d ) \mathcal{B}_d(\sqrt{M_d}) B d ( M d ) with M d M_d M d defined in (15). For any finite n n n , the optimal measure Q ∗ Q^* Q ∗ is a mixture of uniform measures on concentric spheres with radii R i R_i R i . For fixed d d d and s s s , the number of spheres increases (very) slowly with n n n ; when n → ∞ n\to\infty n → ∞ , Q ∗ Q^* Q ∗ increasingly resembles Q 1 , 1 Q_{1,1} Q 1 , 1 , in agreement with Zador’s theorem. For n n n small enough, Q ∗ = Q R ∗ Q^*=Q_{R^*} Q ∗ = Q R ∗ uniform on a single sphere S d − 1 ( R ∗ ) S_{d-1}(R^*) S d − 1 ( R ∗ ) , with R ∗ = R ∗ ( d , n , s ) R^*=R^*(d,n,s) R ∗ = R ∗ ( d , n , s ) . The necessary and sufficient condition for the optimality of Q R ∗ Q_{R^*} Q R ∗ takes a simple form, which we formulate in the theorem below.
Theorem 3.2. [16 Corollary 3.1] For any d ≥ 3 d\geq3 d ≥ 3 , n ≥ 1 n\geq1 n ≥ 1 and s > 0 s>0 s > 0 , the measure Q R ∗ Q_{R^*} Q R ∗ , supported in S d − 1 ( R ∗ ) S_{d-1}(R^*) S d − 1 ( R ∗ ) , minimizes D Q 1 , 1 , s ( Q [ n ] ) D_{Q_{1,1},s}(Q^{[n]}) D Q 1 , 1 , s ( Q [ n ] ) among all distributions on R d \mathbb{R}^d R d if and only if
S ( ρ ; R ∗ , n , s ) ≤ S ( R ∗ ; R ∗ , n , s ) for all ρ ∈ [ 0 , M d ] , S(\rho;R^*,n,s)\leq S(R^*;R^*,n,s)\quad\text{for all }\rho\in[0,\sqrt{M_d}], S ( ρ ; R ∗ , n , s ) ≤ S ( R ∗ ; R ∗ , n , s ) for all ρ ∈ [ 0 , M d ] ,
with S ( ⋅ ; R , n , s ) S(\cdot;R,n,s) S ( ⋅ ; R , n , s ) the sensitivity function defined by
S ( ρ ; R , n , s ) = n s ∫ t ≥ 0 t s − 1 ∫ r ≥ 0 [ 1 − I v ( t , R , r ) ( d ~ , d ~ ) ] n − 1 I v ( t , ρ , r ) ( d ~ , d ~ ) ϕ 1 , 1 ( r ) d r d t , S(\rho;R,n,s)=ns\int_{t\geq0}t^{s-1}\int_{r\geq0}\left[1-I_{v(t,R,r)}(\widetilde{d},\widetilde{d})\right]^{n-1}I_{v(t,\rho,r)}(\widetilde{d},\widetilde{d})\phi_{1,1}(r)\,\mathrm{d}r\,\mathrm{d}t, S ( ρ ; R , n , s ) = n s ∫ t ≥ 0 t s − 1 ∫ r ≥ 0 [ 1 − I v ( t , R , r ) ( d , d ) ] n − 1 I v ( t , ρ , r ) ( d , d ) ϕ 1 , 1 ( r ) d r d t ,
where v ( t , ρ , r ) v(t,\rho,r) v ( t , ρ , r ) is defined by (10) , ϕ 1 , 1 ( ⋅ ) \phi_{1,1}(\cdot) ϕ 1 , 1 ( ⋅ ) is defined by (16) , I v ( d ~ , d ~ ) I_v(\widetilde{d},\widetilde{d}) I v ( d , d ) is the regularized incomplete beta function with d ~ = ( d − 1 ) / 2 \widetilde{d}=(d-1)/2 d = ( d − 1 ) /2 and M d M_d M d is given by (17) .
The left panel of Figure 3 plots S ( ρ ; R ∗ , n , 2 ) S(\rho;R^*,n,2) S ( ρ ; R ∗ , n , 2 ) as a function of ρ ∈ [ 0 , M d ] \rho\in[0,\sqrt{M_d}] ρ ∈ [ 0 , M d ] for d = 10 d=10 d = 10 and n = 1000 n=1000 n = 1000 , where R ∗ ≃ 1.5101 R^*\simeq1.5101 R ∗ ≃ 1.5101 .
Figure 3. Left: sensitivity function S ( ρ ; R ∗ , n , s ) S(\rho;R^*,n,s) S ( ρ ; R ∗ , n , s ) for d = 10 d=10 d = 10 , s = 2 s=2 s = 2 and n = 1000 n=1000 n = 1000 ; the value of S ( R ∗ ; R ∗ , n , s ) S(R^*;R^*,n,s) S ( R ∗ ; R ∗ , n , s ) is indicated by the horizontal dashed line. Right: n 1 ( d , s ) n_1(d,s) n 1 ( d , s ) as a function of d d d for s = 2 s=2 s = 2 (♦), s = 4 s=4 s = 4 (★) and s = 10 s=10 s = 10 (•).
From Zador’s theorem, Q R ∗ \mathbb{Q}_{R^*} Q R ∗ ceases to be optimal for n n n larger than some n 1 ( d , s ) n_1(d,s) n 1 ( d , s ) . The right panel presents n 1 ( d , s ) n_1(d,s) n 1 ( d , s ) , obtained by binary search based on Theorem 3.2, for d = 3 , 4 , … , 20 d=3,4,\ldots,20 d = 3 , 4 , … , 20 and s = 2 , 4 s=2,4 s = 2 , 4 and 10 10 10 (on a logarithmic scale). It shows that for n n n smaller than a value n 1 ( d , s ) n_1(d,s) n 1 ( d , s ) growing exponentially fast with d d d , a measure uniform on a single sphere with radius R ∗ = R ∗ ( d , n , s ) R^*=R^*(d,n,s) R ∗ = R ∗ ( d , n , s ) minimizes D Q 1 , 1 , s ( Q [ n ] ) D_{\mathbb{Q}_{1,1,s}}(\mathbb{Q}^{[n]}) D Q 1 , 1 , s ( Q [ n ] ) . This has the consequence that, for n ≤ n 1 ( d , s ) n\leq n_1(d,s) n ≤ n 1 ( d , s ) , the measure P ∗ = P 0 , R ∗ / d \mathbb{P}^*=\mathbb{P}_{0,R^*/\sqrt{d}} P ∗ = P 0 , R ∗ / d minimizes D Q 1 , 1 , s ( P [ n ] ) D_{\mathbb{Q}_{1,1,s}}(\mathbb{P}^{[n]}) D Q 1 , 1 , s ( P [ n ] ) with respect to P \mathbb{P} P on R d \mathbb{R}^d R d , with P ‾ \overline{\mathbb{P}} P the symmetrized version of P \mathbb{P} P defined by (11) , and the optimal P α , δ \mathbb{P}_{\alpha,\delta} P α , δ minimizing D ^ μ , s ( P α , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}^{[n]}_{\alpha,\delta}) D μ , s ( P α , δ [ n ] ) is P 0 , δ 0 ∗ \mathbb{P}_{0,\delta^*_0} P 0 , δ 0 ∗ with δ 0 ∗ = R ∗ / d \delta^*_0=R^*/\sqrt{d} δ 0 ∗ = R ∗ / d .
For n > n 1 ( d , s ) n>n_1(d,s) n > n 1 ( d , s ) , Q ∗ = ∑ i = 1 q w i ∗ Q R i ∗ \mathbb{Q}^*=\sum_{i=1}^{q}w_i^*\mathbb{Q}_{R_i^*} Q ∗ = ∑ i = 1 q w i ∗ Q R i ∗ is a mixture, and the product measure P ∗ = ∑ i = 1 q w i ∗ P 0 , R i ∗ / d \mathbb{P}^*=\sum_{i=1}^{q}w_i^*\mathbb{P}_{0,R_i^*/\sqrt{d}} P ∗ = ∑ i = 1 q w i ∗ P 0 , R i ∗ / d minimizes D Q 1 , 1 , s ( P [ n ] ) D_{\mathbb{Q}_{1,1,s}}(\mathbb{P}^{[n]}) D Q 1 , 1 , s ( P [ n ] ) . An algorithm for constructing Q ∗ \mathbb{Q}^* Q ∗ is provided in [16 ] . However, for such large values of n n n this approach is unnecessarily complex and Section 4.4 proposes a simpler alternative construction.
For i = 0 , 1 i=0,1 i = 0 , 1 , let δ i ∗ \delta_i^* δ i ∗ denote the value of δ \delta δ minimizing D ^ μ , s ( P i , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}^{[n]}_{i,\delta}) D μ , s ( P i , δ [ n ] ) . The example in the next section shows that, in terms of D ^ μ , s ( ⋅ ) \widehat{D}_{\mu,s}(\cdot) D μ , s ( ⋅ ) , P 1 , δ 1 ∗ \mathbb{P}_{1,\delta_1^*} P 1 , δ 1 ∗ performs only slightly worse than P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ . The former is uniform on δ 1 ∗ C d \delta_1^*\mathcal{C}_d δ 1 ∗ C d , whereas the latter is concentrated on the vertices of δ 0 ∗ C d \delta_0^*\mathcal{C}_d δ 0 ∗ C d . It also shows that, for fixed d d d , the values of δ 0 ∗ \delta_0^* δ 0 ∗ and δ 1 ∗ \delta_1^* δ 1 ∗ vary slowly with n n n and s s s , with δ 1 ∗ \delta_1^* δ 1 ∗ being significantly larger than δ 0 ∗ \delta_0^* δ 0 ∗ .
Example: P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ and P 1 , δ 1 ∗ \mathbb{P}_{1,\delta_1^*} P 1 , δ 1 ∗
We take s = 2 s=2 s = 2 , d = 10 , 20 , … , 50 d=10,20,\ldots,50 d = 10 , 20 , … , 50 and consider designs of sizes n = τ d n=\tau d n = τ d with τ = 10 , 20 , … , 100 \tau=10,20,\ldots,100 τ = 10 , 20 , … , 100 . For all cases considered, we have n < n 1 ( d , s ) n<n_1(d,s) n < n 1 ( d , s ) and the optimal α \alpha α equals zero. The optimal δ ∗ ( d , n , s ) \delta^*(d,n,s) δ ∗ ( d , n , s ) is obtained by minimizing the double integral
D ^ μ , s ( P 0 , δ [ n ] ) = s ∫ t ≥ 0 t s − 1 ∫ r ≥ 0 H 0 ( r , t ; δ , n ) ϕ 1 , 1 ( r ) d r d t , (20) \widehat{D}_{\mu,s}(\mathbb{P}^{[n]}_{0,\delta})=s\int_{t\geq0}t^{s-1}\int_{r\geq0}H_0(r,t;\delta,n)\phi_{1,1}(r)\,\mathrm{d}r\,\mathrm{d}t, \tag*{(20)} D μ , s ( P 0 , δ [ n ] ) = s ∫ t ≥ 0 t s − 1 ∫ r ≥ 0 H 0 ( r , t ; δ , n ) ϕ 1 , 1 ( r ) d r d t , (20)
with respect to δ ∈ ( 0 , 1 ] \delta\in(0,1] δ ∈ ( 0 , 1 ] , where ϕ 1 , 1 \phi_{1,1} ϕ 1 , 1 is given by (14) and H 0 ( r , t ; δ , n ) = [ 1 − I ν ( d ~ , d ~ ) ] n H_0(r,t;\delta,n)=[1-I_{\nu}(\tilde{d},\tilde{d})]^n H 0 ( r , t ; δ , n ) = [ 1 − I ν ( d ~ , d ~ ) ] n with ν = [ t 2 − ( δ d − r ) 2 ] / ( 4 r δ d ) \nu=[t^2-(\delta\sqrt{d}-r)^2]/(4r\delta\sqrt{d}) ν = [ t 2 − ( δ d − r ) 2 ] / ( 4 r δ d ) , see (9, 10). The values of δ 0 ∗ ( d , τ d , 2 ) \delta_0^*(d,\tau d,2) δ 0 ∗ ( d , τ d , 2 ) are shown on the left panel of Figure 4 , while the right panel shows D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) . \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]}). D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) . Note the slow increase of δ 0 ∗ \delta_0^* δ 0 ∗ with τ \tau τ (i.e., with the design size n n n ).
Figure 4. Left: optimal δ 0 ∗ = δ 0 ∗ ( d , τ d , 2 ) \delta_0^*=\delta_0^*(d,\tau d,2) δ 0 ∗ = δ 0 ∗ ( d , τ d , 2 ) minimizing D ^ μ , 2 ( P 0 , δ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta}^{[\tau d]}) D μ , 2 ( P 0 , δ [ τ d ] ) as a function of τ \tau τ for d = 10 d=10 d = 10 (●), d = 20 d=20 d = 20 (♦), d = 30 d=30 d = 30 (▼), d = 40 d=40 d = 40 (★), and d = 50 d=50 d = 50 (■); the dashed lines correspond to the extreme-value approximation (19). Right: D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]}) D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) as a function of τ \tau τ , with the same color code as on the left panel.
For α = 1 \alpha=1 α = 1 , δ 1 ∗ ( d , n , s ) \delta_1^*(d,n,s) δ 1 ∗ ( d , n , s ) minimizes D ^ μ , s ( P 1 , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{1,\delta}^{[n]}) D μ , s ( P 1 , δ [ n ] ) given by (8, 9), where Ψ ( ⋅ ) \Psi(\cdot) Ψ ( ⋅ ) and Φ ( ⋅ ) \Phi(\cdot) Φ ( ⋅ ) are the c.d.f. associated with ϕ 1 , 1 ( ⋅ ) \phi_{1,1}(\cdot) ϕ 1 , 1 ( ⋅ ) and φ ( ⋅ ; a d , b d ∣ δ 2 M d ) \varphi(\cdot\,;a_d,b_d|\delta^2M_d) φ ( ⋅ ; a d , b d ∣ δ 2 M d ) , respectively; see (12) and (15). The left panel of Figure 5 shows the optimal δ 1 ∗ ( d , τ d , 2 ) \delta_1^*(d,\tau d,2) δ 1 ∗ ( d , τ d , 2 ) obtained when we set α = 1 \alpha=1 α = 1 : δ 1 ∗ \delta_1^* δ 1 ∗ is much larger than δ 0 ∗ \delta_0^* δ 0 ∗ on Figure 4 -left and also increases with τ \tau τ , i.e. with n n n (asymptotically, the optimal distribution is uniform, with α = δ = 1 \alpha=\delta=1 α = δ = 1 ). The plots of D ^ μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{1,\delta_1^*}^{[\tau d]}) D μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) are visually indistinguishable from those of D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]}) D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) on Figure 4 -right, and Figure 5 -right presents the efficiencies D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) / D ^ μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]})/\widehat{D}_{\mu,2}(\mathbb{P}_{1,\delta_1^*}^{[\tau d]}) D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) / D μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) obtained for the different d d d and n n n considered: the performance degradation due to the imposition of α = 1 \alpha=1 α = 1 quickly appears negligible as d d d increases.
Figure 5. Left: Optimal δ 1 ∗ = δ 1 ∗ ( d , τ d , 2 ) \delta_1^*=\delta_1^*(d,\tau d,2) δ 1 ∗ = δ 1 ∗ ( d , τ d , 2 ) minimizing D ^ μ , 2 ( P 1 , δ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{1,\delta}^{[\tau d]}) D μ , 2 ( P 1 , δ [ τ d ] ) as a function of τ \tau τ . Right: efficiency D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) / D ^ μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]})/\widehat{D}_{\mu,2}(\mathbb{P}_{1,\delta_1^*}^{[\tau d]}) D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) / D μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) . The color code is as in Figure 4.
We now set n = 50 d n=50d n = 50 d and vary d d d and s s s . The optimal α \alpha α equals zero, and the left panel of Figure 6 plots the optimal δ 0 ∗ ( d , 50 d , s ) \delta_0^*(d,50d,s) δ 0 ∗ ( d , 50 d , s ) versus s s s for different d d d . As s s s increases, the boundary points play a more important role, so that δ 0 ∗ \delta_0^* δ 0 ∗ (slowly) increases with s s s . The right panel shows [ D ^ μ , s ( P 0 , δ 0 ∗ [ 50 d ] ) ] 1 / s [\widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta_0^*}^{[50d]})]^{1/s} [ D μ , s ( P 0 , δ 0 ∗ [ 50 d ] ) ] 1/ s as a function of s s s . When
Figure 6. Left: optimal δ 0 ∗ = δ 0 ∗ ( d , 50 d , s ) \delta_0^*=\delta_0^*(d,50d,s) δ 0 ∗ = δ 0 ∗ ( d , 50 d , s ) minimizing D ^ μ , s ( P 0 [ 50 d ] ) \widehat{D}_{\mu,s}(\mathbb{P}_0^{[50d]}) D μ , s ( P 0 [ 50 d ] ) as a function of s s s for d = 10 d=10 d = 10 (●), d = 20 d=20 d = 20 (♦), d = 30 d=30 d = 30 (▼), d = 40 d=40 d = 40 (★), and d = 50 d=50 d = 50 (■). Right: [ D ^ μ , s ( P 0 [ 50 d ] ) ] 1 / s [\widehat{D}_{\mu,s}(\mathbb{P}_0^{[50d]})]^{1/s} [ D μ , s ( P 0 [ 50 d ] ) ] 1/ s as a function of s s s , with the same color code as on the left panel.
@page 11/25 starts_mid=1 ends_mid=1 with respect to δ ∈ ( 0 , 1 ] \delta\in(0,1] δ ∈ ( 0 , 1 ] , where ϕ 1 , 1 \phi_{1,1} ϕ 1 , 1 is given by (14) and H 0 ( r , t ; δ , n ) = [ 1 − I ν ( d ~ , d ~ ) ] n H_0(r,t;\delta,n)=[1-I_{\nu}(\tilde{d},\tilde{d})]^n H 0 ( r , t ; δ , n ) = [ 1 − I ν ( d ~ , d ~ ) ] n with ν = [ t 2 − ( δ d − r ) 2 ] / ( 4 r δ d ) \nu=[t^2-(\delta\sqrt{d}-r)^2]/(4r\delta\sqrt{d}) ν = [ t 2 − ( δ d − r ) 2 ] / ( 4 r δ d ) , see (9, 10). The values of δ 0 ∗ ( d , τ d , 2 ) \delta_0^*(d,\tau d,2) δ 0 ∗ ( d , τ d , 2 ) are shown on the left panel of Figure 4, while the right panel shows D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) . \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]}). D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) . Note the slow increase of δ 0 ∗ \delta_0^* δ 0 ∗ with τ \tau τ (i.e., with the design size n n n ).
Figure 4 (PDF p. 11). Left: optimal δ 0 ∗ = δ 0 ∗ ( d , τ d , 2 ) \delta_0^*=\delta_0^*(d,\tau d,2) δ 0 ∗ = δ 0 ∗ ( d , τ d , 2 ) minimizing D ^ μ , 2 ( P 0 , δ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta}^{[\tau d]}) D μ , 2 ( P 0 , δ [ τ d ] ) as a function of τ \tau τ for d = 10 d=10 d = 10 (●), d = 20 d=20 d = 20 (♦), d = 30 d=30 d = 30 (▼), d = 40 d=40 d = 40 (★), and d = 50 d=50 d = 50 (■); the dashed lines correspond to the extreme-value approximation (19). Right: D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]}) D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) as a function of τ \tau τ , with the same color code as on the left panel.
For α = 1 \alpha=1 α = 1 , δ 1 ∗ ( d , n , s ) \delta_1^*(d,n,s) δ 1 ∗ ( d , n , s ) minimizes D ^ μ , s ( P 1 , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{1,\delta}^{[n]}) D μ , s ( P 1 , δ [ n ] ) given by (8, 9), where Ψ ( ⋅ ) \Psi(\cdot) Ψ ( ⋅ ) and Φ ( ⋅ ) \Phi(\cdot) Φ ( ⋅ ) are the c.d.f. associated with ϕ 1 , 1 ( ⋅ ) \phi_{1,1}(\cdot) ϕ 1 , 1 ( ⋅ ) and φ ( ⋅ ; a d , b d ∣ δ 2 M d ) \varphi(\cdot\,;a_d,b_d|\delta^2M_d) φ ( ⋅ ; a d , b d ∣ δ 2 M d ) , respectively; see (12) and (15). The left panel of Figure 5 shows the optimal δ 1 ∗ ( d , τ d , 2 ) \delta_1^*(d,\tau d,2) δ 1 ∗ ( d , τ d , 2 ) obtained when we set α = 1 \alpha=1 α = 1 : δ 1 ∗ \delta_1^* δ 1 ∗ is much larger than δ 0 ∗ \delta_0^* δ 0 ∗ on Figure 4 -left and also increases with τ \tau τ , i.e. with n n n (asymptotically, the optimal distribution is uniform, with α = δ = 1 \alpha=\delta=1 α = δ = 1 ). The plots of D ^ μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{1,\delta_1^*}^{[\tau d]}) D μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) are visually indistinguishable from those of D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]}) D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) on Figure 4 -right, and Figure 5 -right presents the efficiencies D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) / D ^ μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]})/\widehat{D}_{\mu,2}(\mathbb{P}_{1,\delta_1^*}^{[\tau d]}) D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) / D μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) obtained for the different d d d and n n n considered: the performance degradation due to the imposition of α = 1 \alpha=1 α = 1 quickly appears negligible as d d d increases.
Figure 5 (PDF p. 11). Left: Optimal δ 1 ∗ = δ 1 ∗ ( d , τ d , 2 ) \delta_1^*=\delta_1^*(d,\tau d,2) δ 1 ∗ = δ 1 ∗ ( d , τ d , 2 ) minimizing D ^ μ , 2 ( P 1 , δ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{1,\delta}^{[\tau d]}) D μ , 2 ( P 1 , δ [ τ d ] ) as a function of τ \tau τ . Right: efficiency D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) / D ^ μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) \widehat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau d]})/\widehat{D}_{\mu,2}(\mathbb{P}_{1,\delta_1^*}^{[\tau d]}) D μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) / D μ , 2 ( P 1 , δ 1 ∗ [ τ d ] ) . The color code is as in Figure 4.
We now set n = 50 d n=50d n = 50 d and vary d d d and s s s . The optimal α \alpha α equals zero, and the left panel of Figure 6 plots the optimal δ 0 ∗ ( d , 50 d , s ) \delta_0^*(d,50d,s) δ 0 ∗ ( d , 50 d , s ) versus s s s for different d d d . As s s s increases, the boundary points play a more important role, so that δ 0 ∗ \delta_0^* δ 0 ∗ (slowly) increases with s s s . The right panel shows [ D ^ μ , s ( P 0 , δ 0 ∗ [ 50 d ] ) ] 1 / s [\widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta_0^*}^{[50d]})]^{1/s} [ D μ , s ( P 0 , δ 0 ∗ [ 50 d ] ) ] 1/ s as a function of s s s . When we impose α = 1 \alpha= 1 α = 1 , the evolution of the optimal values δ 0 ∗ ( d , 50 d , s ) \delta_0^*(d,50d,s) δ 0 ∗ ( d , 50 d , s ) follows that shown in the left panel of Figure 6 , up to a shift toward higher values, similar to the shift between the left panels of Figures 4 and 5. The efficiency ratios [ D ^ μ , s ( P 0 [ 50 d ] ) ] 1 / s / [ D ^ μ , s ( P 1 [ 50 d ] ) ] 1 / s [\widehat{D}_{\mu,s}(\mathbb{P}_0^{[50d]})]^{1/s}/[\widehat{D}_{\mu,s}(\mathbb{P}_1^{[50d]})]^{1/s} [ D μ , s ( P 0 [ 50 d ] ) ] 1/ s / [ D μ , s ( P 1 [ 50 d ] ) ] 1/ s are about 0.99 for d = 10 d=10 d = 10 and above 0.997 for d ≥ 20 d\geq20 d ≥ 20 ; i.e., the increase in quantization error when using α = 1 \alpha=1 α = 1 instead of α = 0 \alpha=0 α = 0 is negligible for large d d d . In contrast, the choice of δ \delta δ (adapted to the chosen α \alpha α ) has a significant effect.
Extreme-value approximation for δ 0 ∗ \delta_0^* δ 0 ∗
An approximation of D μ , s ( Q R [ n ] ) D_{\mu,s}(Q_R^{[n]}) D μ , s ( Q R [ n ] ) is derived in [16 ] for Q R Q_R Q R uniform on S d − 1 ( R ) S_{d-1}(R) S d − 1 ( R ) , μ \mu μ spherically symmetric and d ≥ 3 d\geq3 d ≥ 3 , based on extreme-value theory:
D ~ μ , s ( Q R [ n ] ) = ∫ r ≥ 0 ∫ ζ ≥ 0 [ ( r − R ) 2 + 4 r R κ n , d ζ ] s / 2 d F d ( ζ ) d Ψ ( r ) . \widetilde{D}_{\mu,s}(Q_R^{[n]})=\int_{r\geq0}\int_{\zeta\geq0}\left[(r-R)^2+4rR\kappa_{n,d}\zeta\right]^{s/2}\,\mathrm{d}F_d(\zeta)\,\mathrm{d}\Psi(r). D μ , s ( Q R [ n ] ) = ∫ r ≥ 0 ∫ ζ ≥ 0 [ ( r − R ) 2 + 4 r R κ n , d ζ ] s /2 d F d ( ζ ) d Ψ ( r ) .
Here, Ψ ( ⋅ ) \Psi(\cdot) Ψ ( ⋅ ) is the c.d.f. of ∥ U ∥ \lVert U\rVert ∥ U ∥ when U ∼ d μ U\mathrel{\overset{d}{\sim}}\mu U ∼ d μ , F d ( t ) = 1 − exp [ − t ( d − 1 ) / 2 ] F_d(t)=1-\exp[-t^{(d-1)/2}] F d ( t ) = 1 − exp [ − t ( d − 1 ) /2 ] is a Weibull c.d.f., and κ n , d \kappa_{n,d} κ n , d is the 1 / n 1/n 1/ n quantile of the random variable β d ~ , d ~ \beta_{\widetilde d,\widetilde d} β d , d in (7), defined by I κ n , d ( d ~ , d ~ ) = 1 / n I_{\kappa_{n,d}}(\widetilde d,\widetilde d)=1/n I κ n , d ( d , d ) = 1/ n , with I ν ( ⋅ , ⋅ ) I_\nu(\cdot,\cdot) I ν ( ⋅ , ⋅ ) the regularized incomplete beta function and d ~ = ( d − 1 ) / 2 \widetilde d=(d-1)/2 d = ( d − 1 ) /2 . Explicit expressions are obtained when s s s is an even integer, yielding approximations R ^ ∗ = R ^ ∗ ( d , n , s ) \widehat{R}^*=\widehat{R}^*(d,n,s) R ∗ = R ∗ ( d , n , s ) for the value of R ∗ R^* R ∗ that minimizes D μ , s ( Q R [ n ] ) D_{\mu,s}(Q_R^{[n]}) D μ , s ( Q R [ n ] ) with respect to R R R .
This directly provides an extreme-value approximation of δ 0 ∗ \delta_0^* δ 0 ∗ that minimizes D ^ μ , s ( P 0 , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta}^{[n]}) D μ , s ( P 0 , δ [ n ] ) defined by (17). Indeed, the spherically symmetric approximation of P 0 , δ \mathbb{P}_{0,\delta} P 0 , δ is Q 0 , δ = Q δ d Q_{0,\delta}=Q_{\delta\sqrt d} Q 0 , δ = Q δ d , uniform on the sphere S d − 1 ( δ d ) S_{d-1}(\delta\sqrt d) S d − 1 ( δ d ) . The approximation of δ 0 ∗ \delta_0^* δ 0 ∗ is thus δ ^ 0 ∗ ( d , n , s ) = R ^ ∗ ( d , n , s ) / d \widehat{\delta}_0^*(d,n,s)=\widehat{R}^*(d,n,s)/\sqrt d δ 0 ∗ ( d , n , s ) = R ∗ ( d , n , s ) / d . In particular, for s = 2 s=2 s = 2 we get
δ ^ 0 ∗ ( d , n , 2 ) = E Q 1 , 1 { ∥ U ∥ } d [ 1 − 2 κ n , d Γ ( 1 + 2 d − 1 ) ] (21) \widehat{\delta}_0^*(d,n,2)=\frac{\mathbb{E}_{Q_{1,1}}\{\lVert U\rVert\}}{\sqrt d}\left[1-2\kappa_{n,d}\Gamma\left(1+\frac{2}{d-1}\right)\right] \tag*{(21)} δ 0 ∗ ( d , n , 2 ) = d E Q 1 , 1 {∥ U ∥} [ 1 − 2 κ n , d Γ ( 1 + d − 1 2 ) ] (21)
with U ∼ d Q 1 , 1 U\mathrel{\overset{d}{\sim}}Q_{1,1} U ∼ d Q 1 , 1 . The beta distribution defined by (12) yields
E Q 1 , 1 { ∥ U ∥ } = M d Γ ( a d + 1 / 2 ) Γ ( a d + b d ) Γ ( a d ) Γ ( a d + b d + 1 / 2 ) . \mathbb{E}_{Q_{1,1}}\{\lVert U\rVert\}=\sqrt{M_d}\frac{\Gamma(a_d+1/2)\Gamma(a_d+b_d)}{\Gamma(a_d)\Gamma(a_d+b_d+1/2)}. E Q 1 , 1 {∥ U ∥} = M d Γ ( a d ) Γ ( a d + b d + 1/2 ) Γ ( a d + 1/2 ) Γ ( a d + b d ) .
where a d a_d a d , b d b_d b d and M d M_d M d are given by (15). The values of δ ^ 0 ∗ ( d , n , 2 ) \hat{\delta}_0^*(d,n,2) δ ^ 0 ∗ ( d , n , 2 ) are plotted as dashed lines on the left panel of Figure 4. Notice the good agreement with the values δ 0 ∗ \delta_0^* δ 0 ∗ obtained by numerical minimization of D ^ μ , 2 ( P 0 , δ [ n ] ) \hat{D}_{\mu,2}(\mathbb{P}_{0,\delta}^{[n]}) D ^ μ , 2 ( P 0 , δ [ n ] ) . On the right panel, the values of D ^ μ , 2 ( P 0 , δ ^ 0 ∗ [ τ d ] ) \hat{D}_{\mu,2}(\mathbb{P}_{0,\hat{\delta}_0^*}^{[\tau_d]}) D ^ μ , 2 ( P 0 , δ ^ 0 ∗ [ τ d ] ) are indistinguishable from those of D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) \hat{D}_{\mu,2}(\mathbb{P}_{0,\delta_0^*}^{[\tau_d]}) D ^ μ , 2 ( P 0 , δ 0 ∗ [ τ d ] ) .
Asymptotics for δ 0 ∗ ( d , n ( d ) , s ) \delta_0^*(d,n(d),s) δ 0 ∗ ( d , n ( d ) , s ) and min δ ≥ 0 D ^ μ , s ( P 0 , δ [ n ( d ) ] ) \min_{\delta\geq0}\hat{D}_{\mu,s}(\mathbb{P}_{0,\delta}^{[n(d)]}) min δ ≥ 0 D ^ μ , s ( P 0 , δ [ n ( d )] )
When n = n ( d ) n=n(d) n = n ( d ) grows with d d d , the optimal δ 0 ∗ ( d , n ( d ) , s ) \delta_0^*(d,n(d),s) δ 0 ∗ ( d , n ( d ) , s ) converges to a limit that depends on the growth regime of n n n but not on d d d . Indeed, let Q 1 , 1 ; d \mathbb{Q}_{1,1;d} Q 1 , 1 ; d denote the spherically symmetric approximation of the uniform probability measure on the rescaled hypercube 3 / d C d \sqrt{3/d}\mathcal{C}_d 3/ d C d . When X ∼ d Q 1 , 1 ; d X\overset{d}{\sim}\mathbb{Q}_{1,1;d} X ∼ d Q 1 , 1 ; d , it follows from (16) that ∥ X ∥ → 1 \lVert X\rVert\to1 ∥ X ∥ → 1 in probability as d → ∞ d\to\infty d → ∞ , and Theorem 4.2 of [16 ] implies
δ 0 ∗ ( d , n ( d ) , s ) → { 1 / 3 if n 1 / d → ∞ , 1 − 1 / λ 2 / 3 if n 1 / d → λ ∈ ( 1 , ∞ ) , 0 if ( log n ) / d → 0. (22) \delta_0^*(d,n(d),s)\to
\begin{cases}
1/\sqrt{3} & \text{if } n^{1/d}\to\infty,\\
\sqrt{1-1/\lambda^2}/\sqrt{3} & \text{if } n^{1/d}\to\lambda\in(1,\infty),\\
0 & \text{if } (\log n)/d\to0.
\end{cases} \tag*{(22)} δ 0 ∗ ( d , n ( d ) , s ) → ⎩ ⎨ ⎧ 1/ 3 1 − 1/ λ 2 / 3 0 if n 1/ d → ∞ , if n 1/ d → λ ∈ ( 1 , ∞ ) , if ( log n ) / d → 0. (22)
Moreover, we also have
1 d s / 2 min δ ≥ 0 D ^ μ , s ( P 0 , δ [ n ( d ) ] ) → { 0 if n 1 / d → ∞ , 1 / ( 3 s / 2 λ s ) if n 1 / d → λ ∈ ( 1 , ∞ ) , 1 / 3 s / 2 if ( log n ) / d → 0. (23) \frac{1}{d^{s/2}}\min_{\delta\geq0}\hat{D}_{\mu,s}(\mathbb{P}_{0,\delta}^{[n(d)]})\to
\begin{cases}
0 & \text{if } n^{1/d}\to\infty,\\
1/(3^{s/2}\lambda^s) & \text{if } n^{1/d}\to\lambda\in(1,\infty),\\
1/3^{s/2} & \text{if } (\log n)/d\to0.
\end{cases} \tag*{(23)} d s /2 1 δ ≥ 0 min D ^ μ , s ( P 0 , δ [ n ( d )] ) → ⎩ ⎨ ⎧ 0 1/ ( 3 s /2 λ s ) 1/ 3 s /2 if n 1/ d → ∞ , if n 1/ d → λ ∈ ( 1 , ∞ ) , if ( log n ) / d → 0. (23)
Figure 7 gives an illustration in the case n ( d ) = λ d n(d)=\lambda^d n ( d ) = λ d for s = 2 s=2 s = 2 .
!Two plots showing δ 0 ∗ ( d , n ( d ) , 2 ) \delta_0^*(d,n(d),2) δ 0 ∗ ( d , n ( d ) , 2 ) and ( 1 / d ) min δ ≥ 0 D ^ μ , 2 ( P 0 , δ [ n ( d ) ] ) (1/d)\min_{\delta\ge0}\widehat{D}_{\mu,2}(P^{[n(d)]}_{0,\delta}) ( 1/ d ) min δ ≥ 0 D μ , 2 ( P 0 , δ [ n ( d )] ) as functions of d d d bbox=0.22,0.15,0.74,0.28
Figure 7. δ 0 ∗ ( d , n ( d ) , 2 ) \delta_0^*(d,n(d),2) δ 0 ∗ ( d , n ( d ) , 2 ) (left) and ( 1 / d ) min δ ≥ 0 D ^ μ , 2 ( P 0 , δ [ n ( d ) ] ) (1/d)\min_{\delta\ge0}\widehat{D}_{\mu,2}(P^{[n(d)]}_{0,\delta}) ( 1/ d ) min δ ≥ 0 D μ , 2 ( P 0 , δ [ n ( d )] ) (right) as functions of d d d for n ( d ) = λ d n(d)=\lambda^d n ( d ) = λ d with λ = 1.5 \lambda=1.5 λ = 1.5 (•) and λ = 2 \lambda=2 λ = 2 (♦). The limits (22) and (23) are indicated by horizontal dashed lines.
Comparison between D μ , s ( P α , δ [ n ] ) D_{\mu,s}(\mathbb{P}_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) and D ^ μ , s ( P α , δ [ n ] ) \hat{D}_{\mu,s}(\mathbb{P}_{\alpha,\delta}^{[n]}) D ^ μ , s ( P α , δ [ n ] )
The calculation of D ^ μ , s ( P α , δ [ n ] ) = D Q 1 , 1 , s ( Q α , δ [ n ] ) \hat{D}_{\mu,s}(\mathbb{P}_{\alpha,\delta}^{[n]})=D_{\mathbb{Q}_{1,1},s}(\mathbb{Q}_{\alpha,\delta}^{[n]}) D ^ μ , s ( P α , δ [ n ] ) = D Q 1 , 1 , s ( Q α , δ [ n ] ) is exact, see (8) —up to the numerical evaluation of integrals. In contrast with the case of spherically symmetric distributions, we do not have access to the ground truth D μ , s ( P α , δ [ n ] ) D_{\mu,s}(\mathbb{P}_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) and need to rely on an estimator.
Estimation of D μ , s ( P [ n ] ) D_{\mu,s}(\mathbb{P}^{[n]}) D μ , s ( P [ n ] )
For any probability measure μ \mu μ on a compact set X \mathcal{X} X , the ( μ , s ) (\mu,s) ( μ , s ) -distortion of an arbitrary n n n -point design X n X_n X n can be approximated by the Monte Carlo estimator D μ N , s ( X n ) = ( 1 / N ) ∑ i = 1 N d s ( U i , X n ) D_{\mu_N,s}(X_n)=(1/N)\sum_{i=1}^N d^s(U_i,X_n) D μ N , s ( X n ) = ( 1/ N ) ∑ i = 1 N d s ( U i , X n ) , where the U i U_i U i are i.i.d. with μ \mu μ . This estimator satisfies the classical central limit theorem
N [ D μ N , s ( X n ) − D μ , s ( X n ) ] → d N ( 0 , V ( X n ) ) , N → ∞ , \sqrt{N}\left[D_{\mu_N,s}(X_n)-D_{\mu,s}(X_n)\right]\xrightarrow{d}\mathcal{N}(0,V(X_n)),\qquad N\to\infty, N [ D μ N , s ( X n ) − D μ , s ( X n ) ] d N ( 0 , V ( X n )) , N → ∞ ,
where V ( X n ) = D μ , 2 s ( X n ) − D μ , s 2 ( X n ) V(X_n)=D_{\mu,2s}(X_n)-D_{\mu,s}^2(X_n) V ( X n ) = D μ , 2 s ( X n ) − D μ , s 2 ( X n ) . Moreover, a direct application of Hoeffding’s inequality gives:
for all α ∈ ( 0 , 1 ) , Prob { ∣ D μ N , s ( X n ) − D μ , s ( X n ) ∣ > α C R s ( X n ) } < 2 e − 2 N α 2 , \text{for all }\alpha\in(0,1),\quad\operatorname{Prob}\{|D_{\mu_N,s}(X_n)-D_{\mu,s}(X_n)|>\alpha CR^s(X_n)\}<2e^{-2N\alpha^2}, for all α ∈ ( 0 , 1 ) , Prob { ∣ D μ N , s ( X n ) − D μ , s ( X n ) ∣ > α C R s ( X n )} < 2 e − 2 N α 2 ,
showing the exponentially fast concentration of D μ N , s ( X n ) D_{\mu_N,s}(X_n) D μ N , s ( X n ) to its mean D μ , s ( X n ) D_{\mu,s}(X_n) D μ , s ( X n ) as N N N increases. For large N N N , the expected ( μ , s ) (\mu,s) ( μ , s ) -distortion D μ , s ( P [ n ] ) D_{\mu,s}(P^{[n]}) D μ , s ( P [ n ] ) can then be estimated by the empirical mean of D μ N , s ( X n ) D_{\mu_N,s}(X_n) D μ N , s ( X n ) over a series of random designs X n X_n X n generated with P [ n ] P^{[n]} P [ n ] .
The left panel of Figure 8 shows that when N N N is large enough, the variability caused by the estimation of E μ , s ( X n ) = [ D μ , s ( X n ) ] 1 / s E_{\mu,s}(X_n)=[D_{\mu,s}(X_n)]^{1/s} E μ , s ( X n ) = [ D μ , s ( X n ) ] 1/ s by E μ N , s ( X n ) E_{\mu_N,s}(X_n) E μ N , s ( X n ) is negligible compared to the variability of E μ , s ( X n ) E_{\mu,s}(X_n) E μ , s ( X n ) due to the randomness of X n X_n X n . Here, d = 30 d=30 d = 30 , n = 2 10 n=2^{10} n = 2 10 and N = 2 18 N=2^{18} N = 2 18 . We generate 100 random designs X n ( i ) X_n^{(i)} X n ( i ) , i = 1 , … , 100 i=1,\ldots,100 i = 1 , … , 100 , each with n n n points i.i.d. uniform in C d \mathcal{C}_d C d . The gray envelope is for the values k 1 / d E μ N , s ( X 1 : k ( i ) ) k^{1/d}E_{\mu_N,s}(X_{1:k}^{(i)}) k 1/ d E μ N , s ( X 1 : k ( i ) ) when μ N \mu_N μ N is the empirical measure on the first N N N points of a given scrambled Sobol’ sequence in C d \mathcal{C}_d C d (i.e., the N N N -point prefix of the sequence). The thinner cyan envelope is for k 1 / d E μ N ( i ) , s ( X 1 : k ( 1 ) ) k^{1/d}E_{\mu_N^{(i)},s}(X_{1:k}^{(1)}) k 1/ d E μ N ( i ) , s ( X 1 : k ( 1 ) ) , where the design X n ( 1 ) X_n^{(1)} X n ( 1 ) is fixed but we consider empirical measures μ N ( i ) \mu_N^{(i)} μ N ( i ) supported on the first N N N points of 100 independent scrambled Sobol’ sequences; the magenta envelope is for k 1 / d E μ N ( i ) , s ( X 1 : k ( i ) ) k^{1/d}E_{\mu_N^{(i)},s}(X_{1:k}^{(i)}) k 1/ d E μ N ( i ) , s ( X 1 : k ( i ) ) and empirical measures μ N ( i ) \mu_N^{(i)} μ N ( i ) on 100 independent N N N -point designs i.i.d. uniform in C d \mathcal{C}_d C d . The variability of k 1 / d E μ N ( i ) , s ( X k ) k^{1/d}E_{\mu_N^{(i)},s}(X_k) k 1/ d E μ N ( i ) , s ( X k ) induced by μ N \mu_N μ N is roughly similar whether μ N \mu_N μ N is supported on Sobol’ points or on uniform designs, and is negligible compared to the variability arising from the random choice of X n X_n X n . In the rest of the paper, all numerical evaluations of an L s L_s L s -mean quantization error in X = C d \mathcal{X}=\mathcal{C}_d X = C d use μ N \mu_N μ N supported on the first N N N points of a scrambled Sobol’ sequence in C d \mathcal{C}_d C d .
Figure 8. Left: envelope of k 1 / d E μ N , s ( X n ( i ) ) k^{1/d} E_{\mu_N,s}(X_n^{(i)}) k 1/ d E μ N , s ( X n ( i ) ) for 100 random designs X n ( i ) X_n^{(i)} X n ( i ) (n = 2 10 n=2^{10} n = 2 10 , d = 30 d=30 d = 30 ), uniform in C d \mathcal{C}_d C d (gray), and envelope of k 1 / d E μ N ( i ) , s ( X n ( j ) ) k^{1/d} E_{\mu_N^{(i)},s}(X_n^{(j)}) k 1/ d E μ N ( i ) , s ( X n ( j ) ) for one random design X n ( j ) X_n^{(j)} X n ( j ) and 100 different empirical measures μ N ( i ) \mu_N^{(i)} μ N ( i ) on N N N -point sets, N = 2 18 N=2^{18} N = 2 18 : j = 1 j=1 j = 1 and initial points of 100 scrambled Sobol’ sequences (●); j = 2 j=2 j = 2 and 100 random N N N -point designs i.i.d. uniform in C d \mathcal{C}_d C d (■). Right: n 1 / d [ D ^ μ , s ( P 1 , δ 1 ∗ [ n ] ) ] 1 / s n^{1/d}[\widehat{D}_{\mu,s}(\mathbb{P}_{1,\delta_1^*}^{[n]})]^{1/s} n 1/ d [ D μ , s ( P 1 , δ 1 ∗ [ n ] ) ] 1/ s (♦) and n 1 / d [ E { D μ N , s ( X n ) } ] 1 / s n^{1/d}[\mathbb{E}\{D_{\mu_N,s}(X_n)\}]^{1/s} n 1/ d [ E { D μ N , s ( X n )} ] 1/ s for X n ∼ P 1 , δ 1 ∗ [ n ] X_n \sim\mathbb{P}_{1,\delta_1^*}^{[n]} X n ∼ P 1 , δ 1 ∗ [ n ] (♦) and X n X_n X n given by the n n n -point prefix of Sobol’ sequence in δ 1 ∗ C d \delta_1^*\mathcal{C}_d δ 1 ∗ C d (●), as functions of n n n (the envelopes for 100 independent Monte Carlo realizations and 100 independent scrambled Sobol’ sequences are indicated).
Comparison of D μ , s ( P α , δ [ n ] ) D_{\mu,s}(P_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) with D ^ μ , s ( P α , δ [ n ] ) \widehat{D}_{\mu,s}(P_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) for α = 1 \alpha=1 α = 1 and α = 0 \alpha=0 α = 0
We illustrate the approximation error introduced by considering spherically symmetric distributions through an example with d = 10 d=10 d = 10 , s = 2 s=2 s = 2 and values of n n n between 100 and 1 500. Our numerical results indicate that D ^ μ , s ( P α , δ [ n ] ) \widehat{D}_{\mu,s}(P_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) substantially overestimates D μ , s ( P α , δ [ n ] ) D_{\mu,s}(P_{\alpha,\delta}^{[n]}) D μ , s ( P α , δ [ n ] ) . The behavior is similar for other values of d d d and s s s .
We first consider the case α = 1 \alpha=1 α = 1 , so that P 1 , δ \mathbb{P}_{1,\delta} P 1 , δ is uniform on δ C d \delta\mathcal{C}_d δ C d . We compare D μ N , s ( P 1 , δ ) D_{\mu_N,s}(\mathbb{P}_{1,\delta}) D μ N , s ( P 1 , δ ) , with μ N \mu_N μ N uniform on the first N = 2 15 N=2^{15} N = 2 15 points of a scrambled Sobol’ sequence, with D ^ μ , s ( P 1 , δ [ n ] ) = D Q 1 , 1 , s ( Q 1 , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{1,\delta}^{[n]})=D_{Q_{1,1,s}}(Q_{1,\delta}^{[n]}) D μ , s ( P 1 , δ [ n ] ) = D Q 1 , 1 , s ( Q 1 , δ [ n ] ) computed with (8), where Q 1 , δ Q_{1,\delta} Q 1 , δ is such that ∥ X ∥ 2 \lVert X\rVert^2 ∥ X ∥ 2 has the density φ ( t ; a d , b d ∣ δ 2 M d ) \varphi(t;a_d,b_d\mid\delta^2M_d) φ ( t ; a d , b d ∣ δ 2 M d ) defined by (12) and a d a_d a d , b d b_d b d and M d M_d M d are given by (15). For each n n n considered, n = 100 , 200 , … , 1500 n=100,200,\ldots,1500 n = 100 , 200 , … , 1500 , we calculate the optimal δ 1 ∗ ( n ) \delta_1^*(n) δ 1 ∗ ( n ) minimizing D ^ μ , s ( P 1 , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{1,\delta}^{[n]}) D μ , s ( P 1 , δ [ n ] ) . We then estimate D μ N , s ( P 1 , δ 1 ∗ [ n ] ) = E P 1 , δ 1 ∗ [ n ] { D μ N , s ( X n ) } D_{\mu_N,s}(\mathbb{P}_{1,\delta_1^*}^{[n]})=\mathbb{E}_{\mathbb{P}_{1,\delta_1^*}^{[n]}}\{D_{\mu_N,s}(X_n)\} D μ N , s ( P 1 , δ 1 ∗ [ n ] ) = E P 1 , δ 1 ∗ [ n ] { D μ N , s ( X n )} by Monte Carlo: for each n n n , we generate 100 independent random designs X n ∼ P 1 , δ 1 ∗ [ n ] X_n\sim\mathbb{P}_{1,\delta_1^*}^{[n]} X n ∼ P 1 , δ 1 ∗ [ n ] and compute D μ N , s ( X n ) = E μ N , s ( X n ) D_{\mu_N,s}(X_n)=E_{\mu_N,s}(X_n) D μ N , s ( X n ) = E μ N , s ( X n ) for each of them. We also estimate D μ N , s ( P 1 , δ 1 ∗ [ n ] ) D_{\mu_N,s}(\mathbb{P}_{1,\delta_1^*}^{[n]}) D μ N , s ( P 1 , δ 1 ∗ [ n ] ) by quasi-Monte Carlo, using the first n n n points of 100 independent scrambled Sobol’ sequences in δ 1 ∗ C d \delta_1^*\mathcal{C}_d δ 1 ∗ C d . The right panel of Figure 8 shows the results obtained. One may notice in particular that D ^ μ , s ( P 1 , δ 1 ∗ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{1,\delta_1^*}^{[n]}) D μ , s ( P 1 , δ 1 ∗ [ n ] ) is already in its asymptotic regime for the values of n n n considered (with a decrease rate of n − s / d n^{-s/d} n − s / d ); that D ^ μ , s ( P 1 , δ 1 ∗ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{1,\delta_1^*}^{[n]}) D μ , s ( P 1 , δ 1 ∗ [ n ] ) overestimates D μ , s ( P 1 , δ 1 ∗ [ n ] ) D_{\mu,s}(\mathbb{P}_{1,\delta_1^*}^{[n]}) D μ , s ( P 1 , δ 1 ∗ [ n ] ) ; and that, unsurprisingly, uniform designs in δ 1 ∗ C d \delta_1^*\mathcal{C}_d δ 1 ∗ C d have smaller dispersion when using (scrambled) Sobol’ points than when using i.i.d. random points. It is shown in [16 Th. 4.1] that the variability of D μ , s ( X n ) D_{\mu,s}(X_n) D μ , s ( X n ) tends to zero as n → ∞ n\to\infty n → ∞ when μ \mu μ is spherically symmetric and X n X_n X n is a random design uniform on a sphere S d − 1 ( R ) S_{d-1}(R) S d − 1 ( R ) for some R > 0 R>0 R > 0 . This is not the case here, as μ \mu μ and P 1 , δ \mathbb{P}_{1,\delta} P 1 , δ are uniform on hypercubes. Nevertheless, the variability of D μ , s ( X n ) D_{\mu,s}(X_n) D μ , s ( X n ) remains small6 , as illustrated by the envelopes shown in Figure 8 -right.
We now take α = 0 \alpha=0 α = 0 , so that Q 0 , δ Q_{0,\delta} Q 0 , δ is uniform on S d − 1 ( δ d ) S_{d-1}(\delta\sqrt{d}) S d − 1 ( δ d ) . To investigate the approximation error introduced by using spherically symmetric distributions, we consider the following three distributions P ( δ ) \mathbb{P}(\delta) P ( δ ) with support in S d − 1 ( δ d ) ∩ C d S_{d-1}(\delta\sqrt{d})\cap\mathcal{C}_d S d − 1 ( δ d ) ∩ C d : (i) P U ( δ ) \mathbb{P}_U(\delta) P U ( δ ) , the uniform distribution on the intersection S d − 1 ( δ d ) ∩ C d S_{d-1}(\delta\sqrt{d})\cap\mathcal{C}_d S d − 1 ( δ d ) ∩ C d ; (ii) P R ( δ ) = P 0 , δ \mathbb{P}_R(\delta)=\mathbb{P}_{0,\delta} P R ( δ ) = P 0 , δ , independent sampling with replacement from the vertices of the hypercube δ C d \delta\mathcal{C}_d δ C d ; (iii) P V ( δ ) \mathbb{P}_V(\delta) P V ( δ ) , sampling without replacement from the vertices (as long as n ≤ 2 d n\le2^d n ≤ 2 d ; for n ≥ 2 d n \ge2^{d} n ≥ 2 d , X n \mathbf{X}_{n} X n corresponds to the entire set of vertices).
For each n n n selected, we calculate the optimal δ 0 ∗ = δ 0 ∗ ( n ) \delta_{0}^{*}=\delta_{0}^{*}(n) δ 0 ∗ = δ 0 ∗ ( n ) . The left panel of Figure 9 presents n 1 / d [ D ^ μ , s ( P 0 , δ 0 ∗ [ n ] ) ] 1 / s n^{1/d}[\widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta_{0}^{*}}^{[n]})]^{1/s} n 1/ d [ D μ , s ( P 0 , δ 0 ∗ [ n ] ) ] 1/ s and n 1 / d [ E { D μ N , s ( X n ) } ] 1 / s n^{1/d}[\mathbb{E}\{D_{\mu_{N},s}(\mathbf{X}_{n})\}]^{1/s} n 1/ d [ E { D μ N , s ( X n )} ] 1/ s as functions of n n n , for X n ∼ d P U ( δ 0 ∗ ) [ n ] \mathbf{X}_{n}\mathrel{\overset{d}{\sim}}\mathbb{P}_{U}(\delta_{0}^{*})^{[n]} X n ∼ d P U ( δ 0 ∗ ) [ n ] . As above, μ N \mu_{N} μ N is uniform on the first N = 2 15 N=2^{15} N = 2 15 points of a scrambled Sobol’ sequence and the expectation is estimated through m = 100 m=100 m = 100 Monte Carlo evaluations of D μ N , s ( X n ) D_{\mu_{N},s}(\mathbf{X}_{n}) D μ N , s ( X n ) —the envelope of the 100 realizations of n 1 / d E μ N , s ( X n ) n^{1/d}E_{\mu_{N},s}(\mathbf{X}_{n}) n 1/ d E μ N , s ( X n ) is also shown; again, the variability of D μ , s ( X n ) D_{\mu,s}(\mathbf{X}_{n}) D μ , s ( X n ) is small6 , although μ \mu μ is not spherically symmetric and P ( δ ) \mathbb{P}(\delta) P ( δ ) is not uniform on a sphere (even if its support is contained in S d − 1 ( δ d ) S_{d-1}(\delta\sqrt{d}) S d − 1 ( δ d ) ). For n = 100 n=100 n = 100 , δ 0 ∗ d ≃ 1.289 \delta_{0}^{*}\sqrt{d}\simeq1.289 δ 0 ∗ d ≃ 1.289 is sufficiently small for P U ( δ 0 ∗ ) \mathbb{P}_{U}(\delta_{0}^{*}) P U ( δ 0 ∗ ) to resemble Q 0 , δ 0 ∗ \mathbb{Q}_{0,\delta_{0}^{*}} Q 0 , δ 0 ∗ . Furthermore, as the distributions of ∥ X ∥ 2 \lVert\mathbf{X}\rVert^{2} ∥ X ∥ 2 are similar for X ∼ d μ \mathbf{X}\mathrel{\overset{d}{\sim}}\mu X ∼ d μ and X ∼ d Q 1 , 1 \mathbf{X}\mathrel{\overset{d}{\sim}}\mathbb{Q}_{1,1} X ∼ d Q 1 , 1 (see Figure 2 ), we have [ D ^ μ , s ( P 0 , δ 0 ∗ [ n ] ) ] 1 / s ≈ E { E μ , s ( X n ) } [\widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta_{0}^{*}}^{[n]})]^{1/s}\approx\mathbb{E}\{E_{\mu,s}(\mathbf{X}_{n})\} [ D μ , s ( P 0 , δ 0 ∗ [ n ] ) ] 1/ s ≈ E { E μ , s ( X n )} .
Figure 9. Left: n 1 / d [ D ^ μ , s ( P 0 , δ 0 ∗ [ n ] ) ] 1 / s n^{1/d}[\widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta_{0}^{*}}^{[n]})]^{1/s} n 1/ d [ D μ , s ( P 0 , δ 0 ∗ [ n ] ) ] 1/ s (♦) and n 1 / d [ E { D μ N , s ( X n ) } ] 1 / s n^{1/d}[\mathbb{E}\{D_{\mu_{N},s}(\mathbf{X}_{n})\}]^{1/s} n 1/ d [ E { D μ N , s ( X n )} ] 1/ s for X n ∼ d P U ( δ 0 ∗ ) [ n ] \mathbf{X}_{n}\mathrel{\overset{d}{\sim}}\mathbb{P}_{U}(\delta_{0}^{*})^{[n]} X n ∼ d P U ( δ 0 ∗ ) [ n ] (●) as functions of n n n ; Monte Carlo estimate of the (normalized) spherical measure V ( n ) V(n) V ( n ) of the intersection S d − 1 ( δ 0 ∗ d ) ∩ C d S_{d-1}(\delta_{0}^{*}\sqrt{d})\cap\mathcal{C}_{d} S d − 1 ( δ 0 ∗ d ) ∩ C d (★, the scale is indicated by the red labels on the right vertical axis). Right: n 1 / d [ E μ N , s ( X n ) ] 1 / s n^{1/d}[\mathbb{E}_{\mu_{N},s}(\mathbf{X}_{n})]^{1/s} n 1/ d [ E μ N , s ( X n ) ] 1/ s for X n ∼ d P U ( δ 0 ∗ ) [ n ] \mathbf{X}_{n}\mathrel{\overset{d}{\sim}}\mathbb{P}_{U}(\delta_{0}^{*})^{[n]} X n ∼ d P U ( δ 0 ∗ ) [ n ] (●), P R ( δ 0 ∗ ) [ n ] \mathbb{P}_{R}(\delta_{0}^{*})^{[n]} P R ( δ 0 ∗ ) [ n ] (▼) and P V ( δ 0 ∗ ) [ n ] \mathbb{P}_{V}(\delta_{0}^{*})^{[n]} P V ( δ 0 ∗ ) [ n ] (▲) as functions of n n n . The envelopes for 100 independent realizations of X n \mathbf{X}_{n} X n are indicated.
As n n n increases, δ 0 ∗ ( n ) \delta_{0}^{*}(n) δ 0 ∗ ( n ) increases (see Figure 4-left) and the (normalized) spherical measure V ( n ) V(n) V ( n ) of the intersection S d − 1 ( δ 0 ∗ d ) ∩ C d S_{d-1}(\delta_{0}^{*}\sqrt{d})\cap\mathcal{C}_{d} S d − 1 ( δ 0 ∗ d ) ∩ C d decreases (see the curve with red stars on Figure 9 -left), so that P U ( δ 0 ∗ ) \mathbb{P}_{U}(\delta_{0}^{*}) P U ( δ 0 ∗ ) resembles less and less Q 0 , δ 0 ∗ \mathbb{Q}_{0,\delta_{0}^{*}} Q 0 , δ 0 ∗ : E μ , s ( X n ) E_{\mu,s}(\mathbf{X}_{n}) E μ , s ( X n ) quickly differs significantly from [ D ^ μ , s ( P 0 , δ 0 ∗ [ n ] ) ] 1 / s [\widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta_{0}^{*}}^{[n]})]^{1/s} [ D μ , s ( P 0 , δ 0 ∗ [ n ] ) ] 1/ s as n n n grows. The approximation D ^ μ , s ( P 0 , δ 0 ∗ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta_{0}^{*}}^{[n]}) D μ , s ( P 0 , δ 0 ∗ [ n ] ) is actually pessimistic: P U ( δ 0 ∗ ) \mathbb{P}_{U}(\delta_{0}^{*}) P U ( δ 0 ∗ ) accounts for the geometry of the cube, resulting in a smaller expected ( μ , s ) (\mu,s) ( μ , s ) -distortion than that predicted by spherically symmetric approximations.
The pessimism of D ^ μ , s ( P 0 , δ 0 ∗ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta_{0}^{*}}^{[n]}) D μ , s ( P 0 , δ 0 ∗ [ n ] ) is even stronger on the right panel of Figure 9 where we consider random designs distributed with P R ( δ 0 ∗ ) \mathbb{P}_{R}(\delta_{0}^{*}) P R ( δ 0 ∗ ) and P V ( δ 0 ∗ ) \mathbb{P}_{V}(\delta_{0}^{*}) P V ( δ 0 ∗ ) . When X n ∼ d P V ( δ 0 ∗ ) [ n ] \mathbf{X}_{n}\mathrel{\overset{d}{\sim}}\mathbb{P}_{V}(\delta_{0}^{*})^{[n]} X n ∼ d P V ( δ 0 ∗ ) [ n ] (sampling without replacement), the design is fixed for n ≥ 2 d n\ge2^{d} n ≥ 2 d and n 1 / d E μ N , s ( X n ) n^{1/d}E_{\mu_{N},s}(\mathbf{X}_{n}) n 1/ d E μ N , s ( X n ) then grows like n 1 / d n^{1/d} n 1/ d . When X n ∼ d P R ( δ 0 ∗ ) [ n ] \mathbf{X}_{n}\mathrel{\overset{d}{\sim}}\mathbb{P}_{R}(\delta_{0}^{*})^{[n]} X n ∼ d P R ( δ 0 ∗ ) [ n ] , the proportion of repeated vertices increases with n n n , an effect similar to slowing the growth of the design size. Ultimately, the behavior is similar to P V ( δ 0 ∗ ) [ n ] \mathbb{P}_{V}(\delta_{0}^{*})^{[n]} P V ( δ 0 ∗ ) [ n ] , as all vertices have been included in X n \mathbf{X}_{n} X n . Notice the marked superiority of P R ( δ 0 ∗ ) \mathbb{P}_{R}(\delta_{0}^{*}) P R ( δ 0 ∗ ) , and especially P V ( δ 0 ∗ ) \mathbb{P}_{V}(\delta_{0}^{*}) P V ( δ 0 ∗ ) , for moderate n n n compared with P U ( δ 0 ∗ ) \mathbb{P}_{U}(\delta_{0}^{*}) P U ( δ 0 ∗ ) (and with P 1 , δ 1 ∗ \mathbb{P}_{1,\delta_{1}^{*}} P 1 , δ 1 ∗ on the right panel of Figure 8 ).
This shows that, despite its strong pessimism, the approximation D ^ μ , s ( P 0 , δ [ n ] ) \widehat{D}_{\mu,s}(\mathbb{P}_{0,\delta}^{[n]}) D μ , s ( P 0 , δ [ n ] ) can be used to determine a distribution P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_{0}^{*}} P 0 , δ 0 ∗ whose support provides a basis for designs with small quantization error, an idea further exploited in the next section.
Incremental designs in d d d -dimensional hypercubes
In this section, we compare the quantization-error performance of incremental designs based on P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ and P 1 , δ 1 ∗ \mathbb{P}_{1,\delta_1^*} P 1 , δ 1 ∗ with that obtained with other incremental constructions. The comparison is through numerical examples, with d = 10 d=10 d = 10 and d = 30 d=30 d = 30 .
Determining P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ and P 1 , δ 1 ∗ \mathbb{P}_{1,\delta_1^*} P 1 , δ 1 ∗ requires specifying n n n , which will denote here the maximum targeted design size. In many computer experiment frameworks, it is desirable to be able to interrupt data acquisition at X 1 : k \mathbf{X}_{1:k} X 1 : k for any size k ≤ n k\le n k ≤ n once sufficient information has been gathered. Situations where the order of magnitude of k k k is about 10 d 10d 10 d are of special interest (see [7 ] ), but we also consider designs of much larger size.
When n ≤ 2 d n\le2^d n ≤ 2 d (see § 6.1 , § 6.2 and § 6.3 ), designs based on P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ can be constructed by sampling, randomly or deterministically, from the vertices of δ 0 ∗ C d \delta_0^*\mathcal{C}_d δ 0 ∗ C d .
When d d d is small enough that designs of size n > 2 d n>2^d n > 2 d can be considered (§ 6.4 ), we suggest constructions based on P 1 , δ 1 ∗ \mathbb{P}_{1,\delta_1^*} P 1 , δ 1 ∗ . Since designs contained in the support of P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ suffer from poor dispersion when projected onto lower-dimensional canonical subspaces, perturbing this support is necessary whenever such projections are of interest. § 6.5 explores an approach based on independent perturbations of the vertices of δ 0 ∗ C d \delta_0^*\mathcal{C}_d δ 0 ∗ C d , trading off quantization in the full hypercube against that in lower-dimensional projections. A numerical comparison is also presented with design points independently distributed according to P U ( δ 0 ∗ ) \mathbb{P}_{U}(\delta_0^*) P U ( δ 0 ∗ ) , the uniform distribution on S d − 1 ( δ 0 ∗ ) ∩ C d S_{d-1}(\delta_0^*)\cap\mathcal{C}_d S d − 1 ( δ 0 ∗ ) ∩ C d .
For d = 10 d=10 d = 10 , besides random and Sobol’ points in C d \mathcal{C}_d C d , we also consider two alternative constructions for performance comparison: greedy packing with boundary avoidance [18 , 15 ] , and greedy quantization [10 ] . However, both methods are too computationally expensive for d = 30 d=30 d = 30 . They are briefly described below.
Let Y M \mathcal{Y}_M Y M denote a finite set of M M M candidate points. Greedy packing with boundary avoidance selects the first design point x 1 \mathbf{x}_1 x 1 at the center of C d \mathcal{C}_d C d . Then, at each iteration k k k , the algorithm chooses x k + 1 \mathbf{x}_{k+1} x k + 1 in Arg max x ∈ Y M Δ β ( x ; X 1 : k , C d ) \operatorname{Arg\,max}_{\mathbf{x}\in\mathcal{Y}_M}\Delta_\beta(\mathbf{x};\mathbf{X}_{1:k},\mathcal{C}_d) Arg max x ∈ Y M Δ β ( x ; X 1 : k , C d ) , where Δ β ( x ; X 1 : k , C d ) = min { d ( x , X 1 : k ) , ∂ C d } \Delta_\beta(\mathbf{x};\mathbf{X}_{1:k},\mathcal{C}_d)=\min\{d(\mathbf{x},\mathbf{X}_{1:k}),\partial\mathcal{C}_d\} Δ β ( x ; X 1 : k , C d ) = min { d ( x , X 1 : k ) , ∂ C d } with ∂ C d \partial\mathcal{C}_d ∂ C d the boundary of C d \mathcal{C}_d C d ; i.e., ∂ C d = { x ∈ C d : ∣ x i ∣ = 1 for some i } \partial\mathcal{C}_d=\{\mathbf{x}\in\mathcal{C}_d:|x_i|=1\text{ for some }i\} ∂ C d = { x ∈ C d : ∣ x i ∣ = 1 for some i } .
The greedy minimization algorithm for E μ , s ( X n ) E_{\mu,s}(\mathbf{X}_n) E μ , s ( X n ) also starts with x 1 \mathbf{x}_1 x 1 at the center of C d \mathcal{C}_d C d . Then, at each iteration, it selects x k + 1 \mathbf{x}_{k+1} x k + 1 in Arg min x ∈ C d E μ , s ( X 1 : k ∪ { x } ) \operatorname{Arg\,min}_{\mathbf{x}\in\mathcal{C}_d}E_{\mu,s}(\mathbf{X}_{1:k}\cup\{\mathbf{x}\}) Arg min x ∈ C d E μ , s ( X 1 : k ∪ { x }) ; i.e.,
x k + 1 ∈ Arg min x ∈ C d ∫ C d min { d s ( y , X 1 : k ) , ∥ y − x ∥ s } μ ( d y ) . (24) \mathbf{x}_{k+1}\in\operatorname*{Arg\,min}_{\mathbf{x}\in\mathcal{C}_d}\int_{\mathcal{C}_d}\min\left\{d^s(\mathbf{y},\mathbf{X}_{1:k}),\lVert\mathbf{y}-\mathbf{x}\rVert^s\right\}\,\mu(\mathrm{d}\mathbf{y}). \tag*{(24)} x k + 1 ∈ x ∈ C d Arg min ∫ C d min { d s ( y , X 1 : k ) , ∥ y − x ∥ s } μ ( d y ) . (24)
By [8 Prop. 4.1] , this greedy algorithm is rate-optimal for any s > 0 s>0 s > 0 (i.e., it ensures lim sup k → ∞ k 1 / d E μ , s ( X 1 : k ) < ∞ \limsup_{k\to\infty}k^{1/d}E_{\mu,s}(\mathbf{X}_{1:k})<\infty lim sup k → ∞ k 1/ d E μ , s ( X 1 : k ) < ∞ ). In practice, x k + 1 \mathbf{x}_{k+1} x k + 1 is selected among a finite set Y M ′ \mathcal{Y}_{M'} Y M ′ of candidates and the integral over y ∼ μ \mathbf{y}\sim\mu y ∼ μ in (22) is approximated by a finite sum over a set Y M ′ ′ \mathcal{Y}_{M''} Y M ′′ of M ′ ′ M'' M ′′ points uniformly distributed in C d \mathcal{C}_d C d . The implementation of the algorithm requires computing all pairwise distances between points in Y M ′ \mathcal{Y}_{M'} Y M ′ and Y M ′ ′ \mathcal{Y}_{M''} Y M ′′ , which strongly limits their feasible sizes. Since the set function X n ↦ E μ , s p ( X n ) \mathbf{X}_n\mapsto E_{\mu,s}^p(\mathbf{X}_n) X n ↦ E μ , s p ( X n ) is supermodular, an accelerated lazy-greedy version of the algorithm can be implemented [9 ] , yielding significant computational speedup; see [10 ] .
Sampling vertices without replacement
We set d = 10 d=10 d = 10 and n = 2 8 = 256 n=2^8=256 n = 2 8 = 256 . For greedy packing with boundary avoidance (GP), the candidate set X M \mathbf{X}_M X M consists of the first 2 19 2^{19} 2 19 points of Sobol’ sequence in C d \mathcal{C}_d C d . We set β = 2 2 d \beta=2\sqrt{2d} β = 2 2 d , the value recommended in [18 ] and confirmed experimentally. For the greedy minimization of the quantization error (GQ) E μ , s ( X n ) E_{\mu,s}(\mathbf{X}_n) E μ , s ( X n ) , we take X M ′ = X M ′ ′ \mathbf{X}_{M'}=\mathbf{X}_{M''} X M ′ = X M ′′ to be the set of the first 2 13 2^{13} 2 13 points of Sobol’ sequence in C d \mathcal{C}_d C d , augmented with the 2 d 2^d 2 d vertices. Figure 10 shows k 1 / d E μ , s ( X 1 : k ) k^{1/d}E_{\mu,s}(\mathbf{X}_{1:k}) k 1/ d E μ , s ( X 1 : k ) for k = 50 , … , n k=50,\ldots,n k = 50 , … , n . Here and throughout Section 4, μ N \mu_N μ N denotes the uniform measure on the 2 18 2^{18} 2 18 -point prefix of a scrambled Sobol’ sequence in C d \mathcal{C}_d C d .
Figure 10. k 1 / d E μ N , s ( X 1 : k ) k^{1/d} E_{\mu_N,s}(\mathbf{X}_{1:k}) k 1/ d E μ N , s ( X 1 : k ) versus k k k for s = 10 s = 10 s = 10 (left) and s = 2 s = 2 s = 2 (right), for the designs in Table 1 . Here X n \mathbf{X}_n X n based on P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ is a random permutation of the vertices of δ 0 ∗ C d \delta_0^* \mathcal{C}_d δ 0 ∗ C d : light gray for δ 0 ∗ ( d , n , 10 ) \delta_0^*(d,n,10) δ 0 ∗ ( d , n , 10 ) , dark gray for δ 0 ∗ ( d , n , 2 ) \delta_0^*(d,n,2) δ 0 ∗ ( d , n , 2 ) , with the darkest area showing the intersection of the envelopes (100 independent repetitions).
Table 1. Color code for plots in Figure 10: random points are i.i.d. uniform in C d \mathcal{C}_d C d , GP corresponds to X n \mathbf{X}_n X n generated by greedy packing with boundary avoidance, GQ to X n \mathbf{X}_n X n obtained by greedy minimization of the L s L_s L s -mean quantization error for s = 2 s = 2 s = 2 and s = 10 s = 10 s = 10 .
Unsurprisingly, scrambled Sobol’ points outperform pure random designs, though both are outperformed by other constructions, in particular, for sufficiently large k k k , by greedy packing with boundary avoidance. This approach is grounded in geometrical considerations that make it well-suited for minimizing the covering radius, hence its strong performance in terms of E μ N , s ( X 1 : k ) E_{\mu_N,s}(\mathbf{X}_{1:k}) E μ N , s ( X 1 : k ) for large s s s (left panel, s = 10 s = 10 s = 10 ). While it is rather common that greedy methods do not yield the overall best results, more surprising is the fact that greedy minimization of E μ , 2 ( X n ) E_{\mu,2}(\mathbf{X}_n) E μ , 2 ( X n ) produces smaller E μ , 10 ( X 1 : k ) E_{\mu,10}(\mathbf{X}_{1:k}) E μ , 10 ( X 1 : k ) values (left panel) than greedy minimization of E μ , 10 ( X n ) E_{\mu,10}(\mathbf{X}_n) E μ , 10 ( X n ) . This may be explained by several factors: the candidate set X M ′ \mathbf{X}_{M'} X M ′ is much smaller than for greedy packing (M ′ = 2 13 M' = 2^{13} M ′ = 2 13 versus M = 2 19 M = 2^{19} M = 2 19 ), and the algorithm is quite sensitive to the choice of Y M ′ ′ \mathbf{Y}_{M''} Y M ′′ (here equal to Y M ′ \mathbf{Y}_{M'} Y M ′ ) for large s s s [10 ] . In contrast, designs given by permuting the vertices of δ 0 ∗ C d \delta_0^* \mathcal{C}_d δ 0 ∗ C d respect the expected ordering: those using δ 0 ∗ ( d , n , 10 ) \delta_0^*(d,n,10) δ 0 ∗ ( d , n , 10 ) tend to outperform those using δ 0 ∗ ( d , n , 2 ) \delta_0^*(d,n,2) δ 0 ∗ ( d , n , 2 ) in terms of E μ , 10 ( X 1 : k ) E_{\mu,10}(\mathbf{X}_{1:k}) E μ , 10 ( X 1 : k ) (left panel) and vice-versa (right panel). Their performance is, however, nearly identical, which is consistent with δ 0 ∗ ( d , n , s ) \delta_0^*(d,n,s) δ 0 ∗ ( d , n , s ) varying little with s s s (left panel of Figure 6 ): δ 0 ∗ ( d , n , 2 ) ≃ 0.4415 \delta_0^*(d,n,2) \simeq0.4415 δ 0 ∗ ( d , n , 2 ) ≃ 0.4415 and δ 0 ∗ ( d , n , 10 ) ≃ 0.4690 \delta_0^*(d,n,10) \simeq0.4690 δ 0 ∗ ( d , n , 10 ) ≃ 0.4690 . For s = 2 s = 2 s = 2 (right panel), these random designs outperform the other methods considered.
Sampling from a fractional-factorial subset of vertices
We continue the example from the previous section. As we consider designs of size k ≤ 2 8 k \leq2^8 k ≤ 2 8 , there is no need to consider permutations of all vertices of δ 0 ∗ C d \delta_0^* \mathcal{C}_d δ 0 ∗ C d . For Z n = { z 1 , … , z n } \mathbf{Z}_n = \{z_1,\ldots,z_n\} Z n = { z 1 , … , z n } an n n n -point design with z i ∈ { − 1 , 1 } d z_i \in\{-1,1\}^d z i ∈ { − 1 , 1 } d for all i i i , the Hamming distance d H ( z i , z j ) d_H(\mathbf{z}_i,\mathbf{z}_j) d H ( z i , z j ) counts the number of components that differ between z i \mathbf{z}_i z i and z j \mathbf{z}_j z j , and thus d H ( z i , z j ) = 1 4 ∥ z i − z j ∥ 2 d_H(\mathbf{z}_i,\mathbf{z}_j) = \frac{1}{4}\lVert\mathbf{z}_i-\mathbf{z}_j\rVert^2 d H ( z i , z j ) = 4 1 ∥ z i − z j ∥ 2 ; the minimum Hamming distance ρ H ( Z n ) \rho_H(\mathcal{Z}_n) ρ H ( Z n ) of Z n \mathcal{Z}_n Z n is ρ H ( Z n ) = PR 2 ( Z n ) \rho_H(\mathcal{Z}_n) = \operatorname{PR}^2(\mathcal{Z}_n) ρ H ( Z n ) = PR 2 ( Z n ) with PR ( Z n ) = 1 2 min i ≠ j ∥ z i − z j ∥ \operatorname{PR}(\mathcal{Z}_n) = \frac{1}{2}\min_{i\ne j}\lVert\mathbf{z}_i-\mathbf{z}_j\rVert PR ( Z n ) = 2 1 min i = j ∥ z i − z j ∥ the packing radius of Z n \mathcal{Z}_n Z n .
For a given n ≤ 2 d n \le2^d n ≤ 2 d , let m = ⌊ d − log 2 n ⌋ m = \lfloor d-\log_2 n\rfloor m = ⌊ d − log 2 n ⌋ , and let Z 2 d − m \mathcal{Z}_{2^{d-m}} Z 2 d − m be a 2 d − m 2^{d-m} 2 d − m fractional factorial design in { − 1 , 1 } \{-1,1\} { − 1 , 1 } such that its minimum Hamming distance ρ H ( Z 2 d − m ) \rho_H(\mathcal{Z}_{2^{d-m}}) ρ H ( Z 2 d − m ) is as large as possible. For instance, two-level fractional factorial designs Z 2 d − m \mathcal{Z}_{2^{d-m}} Z 2 d − m with large minimum Hamming distance can be obtained using the simulated-annealing algorithm of [2 ] .7 We can then generate random designs by randomly sampling without replacement from δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\mathcal{Z}_{2^{d-m}} δ 0 ∗ ( d , n , s ) Z 2 d − m , which forms a fractional factorial subset of the vertices of δ 0 ∗ ( d , n , s ) C d \delta_0^*(d,n,s)\mathcal{C}_d δ 0 ∗ ( d , n , s ) C d . In the example considered, m = 2 m=2 m = 2 and the 2 d − 2 2^{d-2} 2 d − 2 fractional factorial design that we use has minimum Hamming distance 2 and resolution VI (with the notation of the pioneering paper [1 ] , its generators are G 1 = 145678 \mathbf{G}_1=145678 G 1 = 145678 and G 2 = 23578 \mathbf{G}_2=23578 G 2 = 23578 ; see also [20 Chap. 5] ).
Figure 11 is analogous to Figure 10 , but for designs X n \mathbf{X}_n X n based on P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ obtained by random permutations of δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\mathcal{Z}_{2^{d-m}} δ 0 ∗ ( d , n , s ) Z 2 d − m . These random designs clearly outperform those in Figure 10 . Note that at k = 2 8 k=2^8 k = 2 8 there is no variability, since all points of δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\mathcal{Z}_{2^{d-m}} δ 0 ∗ ( d , n , s ) Z 2 d − m have already been selected.
Figure 11. Like Figure 10, but now X n \mathbf{X}_n X n based on P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ is a random permutation of δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\mathcal{Z}_{2^{d-m}} δ 0 ∗ ( d , n , s ) Z 2 d − m .
Greedy packing applied to a subset of vertices
Finally, designs based on P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ can be refined by sampling greedily from its support. We use greedy packing: x 1 \mathbf{x}_1 x 1 is drawn uniformly at random from δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\mathcal{Z}_{2^{d-m}} δ 0 ∗ ( d , n , s ) Z 2 d − m , and at each subsequent step k k k , x k + 1 \mathbf{x}_{k+1} x k + 1 is the point in δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\mathcal{Z}_{2^{d-m}} δ 0 ∗ ( d , n , s ) Z 2 d − m furthest from X 1 : k \mathbf{X}_{1:k} X 1 : k , with ties broken randomly.
d = 10 d=10 d = 10 , n = 2 8 = 256 n=2^8=256 n = 2 8 = 256
We continue with the example discussed in the previous two sections. Figure 12 is analogous to Figure 11 , but with X 1 : k \mathbf{X}_{1:k} X 1 : k generated by greedy packing from the candidate set δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\mathcal{Z}_{2^{d-m}} δ 0 ∗ ( d , n , s ) Z 2 d − m : the designs X n \mathbf{X}_n X n are the same, but the intermediate designs X 1 : k \mathbf{X}_{1:k} X 1 : k , k < n k<n k < n , tend to perform better.
Figure 12. Like Figure 11, but now X 1 : k X_{1:k} X 1 : k based on P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ is generated by the greedy packing algorithm applied to δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\,\mathbb{Z}_2^{d-m} δ 0 ∗ ( d , n , s ) Z 2 d − m .
d = 30 d=30 d = 30 , n = 2 10 = 1024 n=2^{10}=1024 n = 2 10 = 1024
Owing to the high dimension d d d , greedy packing with boundary avoidance and greedy minimization of the quantization error are no longer computationally feasible. The left panel of Figure 13 presents k 1 / d E μ N , 2 ( X 1 : k ) k^{1/d} E_{\mu_N,2}(X_{1:k}) k 1/ d E μ N , 2 ( X 1 : k ) versus k k k for random designs i.i.d. uniform in C d \mathcal{C}_d C d , n n n -point prefixes of Sobol’ and independent Sobol’ sequences, in C d \mathcal{C}_d C d and in δ 1 ∗ C d \delta_1^*\mathcal{C}_d δ 1 ∗ C d (with δ 1 ∗ = δ 1 ∗ ( d , n , 2 ) ≃ 0.5540 \delta_1^*=\delta_1^*(d,n,2)\simeq0.5540 δ 1 ∗ = δ 1 ∗ ( d , n , 2 ) ≃ 0.5540 ). We also generate designs in the intersection S d − 1 ( δ 0 ∗ d ) ∩ C d S_{d-1}(\delta_0^*\sqrt{d})\cap\mathcal{C}_d S d − 1 ( δ 0 ∗ d ) ∩ C d (with δ 0 ∗ = δ 0 ∗ ( d , n , 2 ) ≃ 0.3191 \delta_0^*=\delta_0^*(d,n,2)\simeq0.3191 δ 0 ∗ = δ 0 ∗ ( d , n , 2 ) ≃ 0.3191 )—the spherical measure of this intersection is large enough to permit simple rejection sampling. Specifically, points on S d − 1 ( 1 ) S_{d-1}(1) S d − 1 ( 1 ) are obtained by applying the inverse standard normal c.d.f. to the first n ′ n' n ′ points of Sobol’ and scrambled Sobol’ sequences in [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d , with n ′ > n n'>n n ′ > n ; each point is then rescaled to have norm δ 0 ∗ d \delta_0^*\sqrt{d} δ 0 ∗ d , and we retain the first n n n points falling in C d \mathcal{C}_d C d . Finally, we construct a 2 d − m 2^{d-m} 2 d − m fractional factorial design Z 2 d − m \mathbb{Z}_2^{d-m} Z 2 d − m , with m = ⌊ d − log 2 n ⌋ = 20 m=\lfloor d-\log_2 n\rfloor=20 m = ⌊ d − log 2 n ⌋ = 20 , having a large minimum Hamming distance (ρ H ( Z 2 d − m ) = 10 \rho_H(\mathbb{Z}_2^{d-m})=10 ρ H ( Z 2 d − m ) = 10 ), and construct designs X 1 : k X_{1:k} X 1 : k by greedy packing using the candidate set δ 0 ∗ ( d , n , s ) Z 2 d − m \delta_0^*(d,n,s)\,\mathbb{Z}_2^{d-m} δ 0 ∗ ( d , n , s ) Z 2 d − m . The variability due to the random choice of x 1 x_1 x 1 and to random tie-breaking is negligible and not visible in the figure.
Figure 13. Left (d = 30 d = 30 d = 30 , n = 1024 n = 1024 n = 1024 ; δ 0 ∗ = δ 0 ∗ ( d , n , 2 ) \delta_0^* = \delta_0^*(d,n,2) δ 0 ∗ = δ 0 ∗ ( d , n , 2 ) , δ 1 ∗ = δ 1 ∗ ( d , n , 2 ) \delta_1^* = \delta_1^*(d,n,2) δ 1 ∗ = δ 1 ∗ ( d , n , 2 ) ): k 1 / d E μ N , 2 ( X 1 : k ) k^{1/d} E_{\mu_N,2}(X_{1:k}) k 1/ d E μ N , 2 ( X 1 : k ) versus k k k , for 100 random designs i.i.d. uniform in C d \mathcal{C}_d C d (magenta envelope); k k k -point prefixes of Sobol’ sequence (●—●) and 100 independent scrambled Sobol’ sequences, in C d \mathcal{C}_d C d (light blue envelope) and in δ 1 ∗ C d \delta_1^* \mathcal{C}_d δ 1 ∗ C d (dark blue envelope); n n n -point designs uniform in S d − 1 ( δ 0 ∗ d ) ∩ C d \mathbb{S}_{d-1}(\delta_0^* \sqrt{d}) \cap\mathcal{C}_d S d − 1 ( δ 0 ∗ d ) ∩ C d (red envelope); X 1 : k X_{1:k} X 1 : k generated by greedy packing from the candidate set δ 0 ∗ Z 2 d − m \delta_0^* \mathbb{Z}_2^{d-m} δ 0 ∗ Z 2 d − m (■—■). Right (d = 10 d = 10 d = 10 , n = 10 000 n = 10\,000 n = 10 000 ): k 1 / d E μ N , 2 ( X 1 : k ) k^{1/d} E_{\mu_N,2}(X_{1:k}) k 1/ d E μ N , 2 ( X 1 : k ) versus k k k for the first three designs in Table 1 and for k k k -point prefixes of Sobol’ sequence (■—■) and 100 independent scrambled Sobol’ sequences (dark blue envelope) in δ 1 ∗ ( d , n , 2 ) C d \delta_1^*(d,n,2)\mathcal{C}_d δ 1 ∗ ( d , n , 2 ) C d . The red envelope corresponds to random permutations of the product quantizer { ± 1 2 , … , ± 1 2 } \{\pm\frac{1}{2},\ldots,\pm\frac{1}{2}\} { ± 2 1 , … , ± 2 1 } augmented with prefixes of independent scrambled Sobol’ sequences in δ 1 ∗ ( d , n , 2 ) C d \delta_1^*(d,n,2)\mathcal{C}_d δ 1 ∗ ( d , n , 2 ) C d .
Note the striking difference in quantization performance for small k k k between the k k k -point prefix of Sobol’ sequence and those of scrambled Sobol’ sequences (other scrambling methods, e.g., Cranley–Patterson rotation [3 ] , yield similar results): although their filling properties become similar asymptotically, the initial points of the Sobol’ sequence exhibit a specific structure that results in lower quantization error for design sizes k ≪ 2 d k\ll2^d k ≪ 2 d . The designs based on P 1 , δ 1 ∗ \mathbb{P}_{1,\delta_1^*} P 1 , δ 1 ∗ (dark blue) and P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ (red and black) perform significantly better than random and Sobol’ designs in C d \mathcal{C}_d C d . Greedy packing applied to the fractional factorial design Z 2 d − m \mathbb{Z}_2^{d-m} Z 2 d − m yields the best overall performance, and designs uniform in δ 1 ∗ C d \delta_1^*\mathcal{C}_d δ 1 ∗ C d are preferable to those in S d − 1 ( δ 0 ∗ d ) ∩ C d S_{d-1}(\delta_0^*\sqrt{d})\cap\mathcal{C}_d S d − 1 ( δ 0 ∗ d ) ∩ C d . The plots of k 1 / d E μ N , 10 ( X 1 : k ) k^{1/d} E_{\mu_N,10}(X_{1:k}) k 1/ d E μ N , 10 ( X 1 : k ) versus k k k are similar, up to a shift towards larger values. Using δ 0 ∗ ( d , n , 10 ) \delta_0^*(d,n,10) δ 0 ∗ ( d , n , 10 ) and δ 1 ∗ ( d , n , 10 ) \delta_1^*(d,n,10) δ 1 ∗ ( d , n , 10 ) instead of δ 0 ∗ ( d , n , 2 ) \delta_0^*(d,n,2) δ 0 ∗ ( d , n , 2 ) and δ 1 ∗ ( d , n , 2 ) \delta_1^*(d,n,2) δ 1 ∗ ( d , n , 2 ) has little effect, since δ 0 ∗ \delta_0^* δ 0 ∗ and δ 1 ∗ \delta_1^* δ 1 ∗ vary only slightly with s s s (see the left panel of Figure 6 for δ 0 ∗ \delta_0^* δ 0 ∗ and the comments after the figure for the evolution of δ 1 ∗ \delta_1^* δ 1 ∗ ): we have δ 0 ∗ ( d , n , 10 ) ≃ 0.3269 \delta_0^*(d,n,10)\simeq0.3269 δ 0 ∗ ( d , n , 10 ) ≃ 0.3269 and δ 1 ∗ ( d , n , 10 ) ≃ 0.5676 \delta_1^*(d,n,10)\simeq0.5676 δ 1 ∗ ( d , n , 10 ) ≃ 0.5676 .
Designs with size above 2 d 2^d 2 d
When the design size can reach n > 2 d n>2^d n > 2 d we cannot restrict our attention to the vertices of δ 0 ∗ C d \delta_0^*\mathcal{C}_d δ 0 ∗ C d . A first option is to take X k X_k X k as the k k k -point prefix of a random design, or a (scrambled) Sobol’ sequence, in δ 1 ∗ C d \delta_1^*\mathcal{C}_d δ 1 ∗ C d . The right panel of Figure 13 provides an illustration for d = 10 d=10 d = 10 and n = 10 000 n=10\,000 n = 10 000 : designs uniform in δ 1 ∗ C d \delta_1^*\mathcal{C}_d δ 1 ∗ C d perform significantly better than designs uniform in C d \mathcal{C}_d C d . Here, δ 1 ∗ = δ 1 ∗ ( d , n , 2 ) ≃ 0.9046 \delta_1^* = \delta_1^*(d,n,2) \simeq0.9046 δ 1 ∗ = δ 1 ∗ ( d , n , 2 ) ≃ 0.9046 . Although greedy packing with boundary avoidance performs well, prefixes of the Sobol’ (or a scrambled Sobol’) sequence on δ 1 ∗ C d \delta_1^* \mathcal{C}_d δ 1 ∗ C d constitute a valuable alternative, owing to the simplicity of their construction. These prefixes can also be used to augment the full factorial design X 2 d ∗ \mathbf{X}_{2^d}^* X 2 d ∗ of Remark 3.1, yielding even better performance.
Accounting for low-dimensional projections
By projection, we mean projection onto a canonical subspace of dimension p < d p < d p < d . For any n n n -point design X n \mathbf{X}_n X n , let { X n } J \{\mathbf{X}_n\}_J { X n } J denote the projection of X n \mathbf{X}_n X n onto the coordinates in J ⊂ { 1 , … , d } J \subset\{1,\ldots,d\} J ⊂ { 1 , … , d } , with ∣ J ∣ = p |J| = p ∣ J ∣ = p .
The designs from Sections 4.1–4.4 are concentrated in a cube δ C d \delta\mathcal{C}_d δ C d with δ < 1 \delta< 1 δ < 1 , and even δ < 1 / 2 \delta< 1/2 δ < 1/2 when d d d is large and n ≪ 2 d n \ll2^d n ≪ 2 d , see the left panel of Figure 4. Consequently, their projections onto low-dimensional subspaces are poor: { X n } J ∈ δ C p \{\mathbf{X}_n\}_J \in\delta\mathcal{C}_p { X n } J ∈ δ C p for every p ∈ { 1 , … , d } p \in\{1,\ldots,d\} p ∈ { 1 , … , d } . In particular, when X n \mathbf{X}_n X n is based on P 0 , δ 0 ∗ \mathbb{P}_{0,\delta_0^*} P 0 , δ 0 ∗ (Sections 4.1 to 4.3), its projections on a p p p -dimensional subspace contain at most n p = min { n , 2 p } n_p = \min\{n,2^p\} n p = min { n , 2 p } distinct points.
The method below builds on the greedy-packing approach of Section 4.3, which uses a 2 d − m 2^{d-m} 2 d − m fractional factorial design Z 2 d − m \mathbf{Z}_{2^{d-m}} Z 2 d − m as the candidate set, with m = ⌊ d − log 2 n ⌋ m = \lfloor d - \log_2 n \rfloor m = ⌊ d − log 2 n ⌋ and n n n the maximum targeted design size. We first generate points x k ′ \mathbf{x}'_k x k ′ , k = 1 , … , n k = 1,\ldots,n k = 1 , … , n in { − 1 , 1 } d \{-1,1\}^d { − 1 , 1 } d via greedy-packing: x 1 ′ \mathbf{x}'_1 x 1 ′ is a random element of Z 2 d − m \mathbf{Z}_{2^{d-m}} Z 2 d − m and x k + 1 ′ \mathbf{x}'_{k+1} x k + 1 ′ is the point in Z 2 d − m \mathbf{Z}_{2^{d-m}} Z 2 d − m furthest from X 1 : k ′ = { x 1 ′ , … , x k ′ } \mathbf{X}'_{1:k} = \{\mathbf{x}'_1,\ldots,\mathbf{x}'_k\} X 1 : k ′ = { x 1 ′ , … , x k ′ } , with ties broken randomly. The actual design points are then obtained by componentwise scaling: x k = x k ′ ∘ y k \mathbf{x}_k = \mathbf{x}'_k \circ\mathbf{y}_k x k = x k ′ ∘ y k for some y k ∈ [ 0 , 1 ] d \mathbf{y}_k \in[0,1]^d y k ∈ [ 0 , 1 ] d , where ∘ \circ ∘ denotes the Hadamard product (i.e. ( x ∘ y ) i = x i y i (\mathbf{x}\circ\mathbf{y})_i = x_i y_i ( x ∘ y ) i = x i y i , i = 1 , … , d i = 1,\ldots,d i = 1 , … , d ).
Let φ y ( ⋅ ) \varphi_y(\cdot) φ y ( ⋅ ) be a p.d.f. supported on [ 0 , 1 ] [0,1] [ 0 , 1 ] and let F y ( ⋅ ) F_y(\cdot) F y ( ⋅ ) denote its c.d.f. A first option is to use i.i.d. random vectors Y k ∼ i . i . d . φ y \mathbf{Y}_k \overset{\mathrm{i.i.d.}}{\sim} \varphi_y Y k ∼ i.i.d. φ y . Alternatively, one may set y k = F y − 1 ( s k ) \mathbf{y}_k = F_y^{-1}(\mathbf{s}_k) y k = F y − 1 ( s k ) , k = 1 , 2 , … k = 1,2,\ldots k = 1 , 2 , … , where s k \mathbf{s}_k s k is the k k k -point prefix of Sobol’ sequence in [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d and F y − 1 F_y^{-1} F y − 1 (the inverse c.d.f.) is applied componentwise. To keep E μ , s ( X 1 : k ) E_{\mu,s}(\mathbf{X}_{1:k}) E μ , s ( X 1 : k ) small (i.e., to obtain space-filling designs), φ y \varphi_y φ y should be peaked at δ 0 ∗ \delta_0^* δ 0 ∗ . We propose
φ y ( t ) = φ ( t ; a , b ∣ 1 ) (25) \varphi_y(t)=\varphi(t;a,b|1) \tag*{(25)} φ y ( t ) = φ ( t ; a , b ∣1 ) (25)
given by (12) with
a = 1 + δ 0 ∗ ( b − 1 ) 1 − δ 0 ∗ , (26) a=1+\frac{\delta_0^*(b-1)}{1-\delta_0^*}, \tag*{(26)} a = 1 + 1 − δ 0 ∗ δ 0 ∗ ( b − 1 ) , (26)
so that d φ y / d t = 0 \mathrm{d}\varphi_y/\mathrm{d}t=0 d φ y / d t = 0 at t = δ 0 ∗ t=\delta_0^* t = δ 0 ∗ . Hence, φ y \varphi_y φ y attains its maximum at δ 0 ∗ \delta_0^* δ 0 ∗ for b > 1 b>1 b > 1 . We take b ∈ [ 1 , ∞ ) b\in[1,\infty) b ∈ [ 1 , ∞ ) : when b = 1 b=1 b = 1 , y k \mathbf{y}_k y k is uniform in [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d , while y k → δ 0 ∗ ( 1 , … , 1 ) \mathbf{y}_k\to\delta_0^*(1,\ldots,1) y k → δ 0 ∗ ( 1 , … , 1 ) as b → ∞ b\to\infty b → ∞ .
In the following example, we compare quantization performance, in the full space and in projections, across different values of b b b in (23–24), highlighting the inherent trade-off between the two.
Consider again the case d = 30 d=30 d = 30 , n = 2 10 = 1 024 n=2^{10}=1\,024 n = 2 10 = 1 024 . The fractional factorial design Z 2 d − m \mathbf{Z}_{2^{d-m}} Z 2 d − m of § 6.3 , with minimum Hamming distance ρ H ( Z 2 d − m ) = 10 \rho_H(\mathbf{Z}_{2^{d-m}})=10 ρ H ( Z 2 d − m ) = 10 , has resolution IV, with 16 defining relations of length 4 (see, e.g., [1 ] and [20 Chap. 5] for definitions). Since m = 10 m=10 m = 10 , every p p p -dimensional projection of Z 2 d − m \mathbf{Z}_{2^{d-m}} Z 2 d − m involving only the first 10 variables yields a 2 p 2^p 2 p full factorial design; moreover, any projection with p ≤ 3 p\leq3 p ≤ 3 is also a 2 p 2^p 2 p full factorial design. For p = 4 p=4 p = 4 , out of 27 405 = ( 30 4 ) 27\,405=\binom{30}{4} 27 405 = ( 4 30 ) possible 4-dimensional projections, all but 16 (( 30 4 ) − 16 = 27 389 \binom{30}{4}-16=27\,389 ( 4 30 ) − 16 = 27 389 ) are 2 p 2^p 2 p full factorial designs. This illustrates the benefit of choosing a design with high resolution R R R and few defining relations of length R R R . However, a trade-off with the minimum Hamming distance is necessary: we could find designs with less than 16 defining relations of length 4, but their minimum Hamming distance drops to only 9.
Figure 14 shows the projections { X n } J \{\mathbf{X}_n\}_{\mathcal{J}} { X n } J of different designs X n \mathbf{X}_n X n onto the subspace defined by J = { 29 , 30 } \mathcal{J}=\{29,30\} J = { 29 , 30 } (the reason for this choice is that, for the Sobol’ sequence (top row, left), the projection onto the last two coordinates is less even than the projections onto pairs of variables with smaller indices). The center panel shows quasi-random points with distribution P 1 , δ 0 ∗ P_{1,\delta_0^*} P 1 , δ 0 ∗ , and the right panel those with P 0 , δ 0 ∗ P_{0,\delta_0^*} P 0 , δ 0 ∗ . On the bottom row, the designs are generated as x k = x k ′ ∘ F y − 1 ( s k ) \mathbf{x}_k=\mathbf{x}'_k\circ F_y^{-1}(s_k) x k = x k ′ ∘ F y − 1 ( s k ) , where x k ′ \mathbf{x}'_k x k ′ is obtained by greedy packing applied to Z 2 d − m \mathbf{Z}_{2^{d-m}} Z 2 d − m , s k s_k s k is the k k k -th Sobol’ point in [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d , and F y F_y F y is the c.d.f. of the beta density (23) with a a a from (24), for three values of b b b . When b = 1 b=1 b = 1 (left), y k = s k \mathbf{y}_k=\mathbf{s}_k y k = s k , and the projection { X n } { 29 , 30 } \{\mathbf{X}_n\}_{\{29,30\}} { X n } { 29 , 30 } is more evenly spread over C 2 \mathcal{C}_2 C 2 than for the standard Sobol’ sequence (top left). As b b b increases (center and right), { X n } { 29 , 30 } \{\mathbf{X}_n\}_{\{29,30\}} { X n } { 29 , 30 } becomes increasingly concentrated around the four points ( ± δ 0 ∗ , ± δ 0 ∗ ) (\pm\delta_0^*,\pm\delta_0^*) ( ± δ 0 ∗ , ± δ 0 ∗ ) .
Figure 14. Design projections { X n } { 29 , 30 } \{\mathbf{X}_n\}_{\{29,30\}} { X n } { 29 , 30 } . First row: prefixes of Sobol’ sequence in C d \mathcal{C}_d C d (left) and in δ 1 ∗ C d \delta_1^* \mathcal{C}_d δ 1 ∗ C d (center), δ 0 ∗ Z 2 d − m \delta_0^* \mathbb{Z}_2^{d-m} δ 0 ∗ Z 2 d − m (right). Second row: x k = x k ′ ∘ F y − 1 ( s k ) \mathbf{x}_k = \mathbf{x}'_k \circ F_y^{-1}(s_k) x k = x k ′ ∘ F y − 1 ( s k ) , k = 1 , … , n k=1,\ldots,n k = 1 , … , n , with s k s_k s k the k k k -th element of Sobol’ sequence in [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d and φ y \varphi_y φ y given by (23–24) with b = 1 b=1 b = 1 (left), b = 3 b=3 b = 3 (center) and b = 10 b=10 b = 10 (right).
Figure 15 plots k 1 / p E μ N ∣ p , 2 ( { X k } J ) k^{1/p}E_{\mu_N|p,2}(\{\mathbf{X}_k\}_{\mathcal{J}}) k 1/ p E μ N ∣ p , 2 ({ X k } J ) versus k k k for different designs, with p = ∣ J ∣ = 4 p=|\mathcal{J}|=4 p = ∣ J ∣ = 4 and μ N ∣ p \mu_{N|p} μ N ∣ p uniform on the first p p p components of the points supporting μ N \mu_N μ N . On the left panel, J = { 27 , 28 , 29 , 30 } \mathcal{J}=\{27,28,29,30\} J = { 27 , 28 , 29 , 30 } , corresponding to a 4-dimensional subspace for which the projection { Z 2 d − m } J \{\mathbf{Z}_{2^{d-m}}\}_{\mathcal{J}} { Z 2 d − m } J is a 16-point full factorial design repeated 64 times. On the right panel, J = { 2 , 4 , 14 , 22 } \mathcal{J}=\{2,4,14,22\} J = { 2 , 4 , 14 , 22 } , corresponding to one of the 16 poor 4-dimensional projections out of ( 30 4 ) = 27 405 \binom{30}{4}=27\,405 ( 4 30 ) = 27 405 : { Z 2 d − m } J \{\mathbf{Z}_{2^{d-m}}\}_{\mathcal{J}} { Z 2 d − m } J is a half fraction (see [1 ] ) repeated 128 times. Therefore, for any b b b , the designs { X k } J \{\mathbf{X}_k\}_{\mathcal{J}} { X k } J only occupy half of the 4-dimensional cube; hence the larger L s L_s L s -mean quantization error observed on the right panel compared to the left one.
Figure 15. k 1 / 4 E μ N , 4 , 2 ( { X k } J ) k^{1/4}E_{\mu_N,4,2}(\{\mathbf{X}_k\}_{\mathcal{J}}) k 1/4 E μ N , 4 , 2 ({ X k } J ) versus k k k for J = { 27 , 28 , 29 , 30 } \mathcal{J}=\{27,28,29,30\} J = { 27 , 28 , 29 , 30 } (left) and J = { 2 , 4 , 14 , 22 } \mathcal{J}=\{2,4,14,22\} J = { 2 , 4 , 14 , 22 } (right): k k k -point prefixes of Sobol’ sequence (●—●), X 1 : k \mathbf{X}_{1:k} X 1 : k generated by greedy packing from the candidate set δ 0 ∗ ( d , n , 2 ) Z 2 d − m \delta_0^*(d,n,2)\mathbb{Z}_2^{d-m} δ 0 ∗ ( d , n , 2 ) Z 2 d − m (■—■), quasi random (Sobol’) design uniform in S d − 1 ( δ d ∗ d ) ∩ C d \mathbb{S}_{d-1}(\delta_d^*\sqrt{d})\cap\mathcal{C}_d S d − 1 ( δ d ∗ d ) ∩ C d (★—★), and X 1 : k = { x 1 , … , x k } \mathbf{X}_{1:k}=\{\mathbf{x}_1,\ldots,\mathbf{x}_k\} X 1 : k = { x 1 , … , x k } where x k = x k ′ ∘ F y − 1 ( s k ) \mathbf{x}_k=\mathbf{x}'_k\circ F_y^{-1}(s_k) x k = x k ′ ∘ F y − 1 ( s k ) , s k s_k s k is the k k k -th element of Sobol’ sequence in [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d , φ y \varphi_y φ y is given by (23) with a a a as in (24), and b = 1 b=1 b = 1 (◆—◆), b = 2 , … , 9 b=2,\ldots,9 b = 2 , … , 9 (★- - -★), b = 10 b=10 b = 10 (▼—▼).
Figure 16 shows the full-space quantization performance (for s = 10 s=10 s = 10 and s = 2 s=2 s = 2 ) of the same designs as in Figure 15 . The quasi-random design uniform on S d − 1 ( δ 0 ∗ d ) ∩ C d \mathcal{S}_{d-1}(\delta_0^*\sqrt{d})\cap\mathcal{C}_d S d − 1 ( δ 0 ∗ d ) ∩ C d (see § 6.3 for d = 30 d=30 d = 30 and n = 2 10 n=2^{10} n = 2 10 ) achieves a trade-off between quantization in C d \mathcal{C}_d C d and in its four-dimensional projections, but offers no tuning parameter to control it. In contrast, designs X 1 : k \mathbf{X}_{1:k} X 1 : k generated by x k = x k ′ ∘ F y − 1 ( s k ) \mathbf{x}_k=\mathbf{x}'_k\circ F_y^{-1}(s_k) x k = x k ′ ∘ F y − 1 ( s k ) allow such control through the parameter b b b in (24): for b = 1 b=1 b = 1 , performance is similar to that of Sobol’ prefixes in C d \mathcal{C}_d C d (good in projections, weak in the full space), whereas for large b b b it approaches that of greedy-packing designs based on δ 0 ∗ Z 2 d − m \delta_0^*\mathbb{Z}_2^{d-m} δ 0 ∗ Z 2 d − m (excellent in the full space, weak in projections).
Figure 16. k 1 / d E μ N , 10 ( X k ) k^{1/d} E_{\mu_N,10}(X_k) k 1/ d E μ N , 10 ( X k ) (left) and k 1 / d E μ N , 2 ( X k ) k^{1/d} E_{\mu_N,2}(X_k) k 1/ d E μ N , 2 ( X k ) (right) versus k k k for the same designs as in Figure 15 .
Conclusions
We have proposed a methodology for generating incremental designs in high-dimensional hypercubes C d = [ − 1 , 1 ] d \mathcal{C}_d=[-1,1]^d C d = [ − 1 , 1 ] d , based on minimizing the L s L_s L s -mean quantization error of the uniform distribution. By considering spherically symmetric approximations of product measures on the hypercube, we construct an approximation of the mean distortion of a random design with i.i.d. points, which can be minimized with respect to their distribution. For design sizes n n n growing slower than exponentially in the dimension d d d , the optimal distribution is supported on the vertices of a smaller hypercube δ 0 ∗ E d \delta_0^*\mathcal{E}_d δ 0 ∗ E d . Sampling these vertices, or a suitable subset of them when n < 2 d n < 2^d n < 2 d (e.g., via a fractional factorial design), possibly through a deterministic algorithm such as greedy packing, yields incremental designs with strong quantization performance. Since sampling hypercube vertices necessarily produces designs with poor low-dimensional projections, a perturbation can be applied, with a parameter that sets the trade-off between quantization performance in the full hypercube and in lower-dimensional projections (§ 6.5 ). The optimal δ 0 ∗ \delta_0^* δ 0 ∗ , which depends on d d d , n n n , and s s s , can be determined numerically by minimizing a function expressed as a double integral (see (20) ); for large enough n n n , an extreme-value approximation δ 0 ∗ \delta_0^* δ 0 ∗ can be used, with an explicit form when s = 2 s = 2 s = 2 (see (21) ). When d d d is small enough that designs of size n > 2 d n > 2^d n > 2 d can be considered, we suggest augmenting the 2 d 2^d 2 d vertices of 1 2 E d \frac{1}{2}\mathcal{E}_d 2 1 E d with points uniformly distributed in a larger cube δ 1 ∗ E d \delta_1^*\mathcal{E}_d δ 1 ∗ E d (§ 6.4 ).
Finally, recall that our incremental constructions of designs X 1 : k \mathbf{X}_{1:k} X 1 : k require specifying a target maximum design size n n n . One could also adapt the construction to k k k , i.e., use δ 0 ∗ ( d , k , s ) \delta_0^*(d,k,s) δ 0 ∗ ( d , k , s ) and δ 1 ∗ ( d , k , s ) \delta_1^*(d,k,s) δ 1 ∗ ( d , k , s ) . Further investigation is needed to assess whether this would improve performance and, if so, whether the gain would justify the increased complexity of the algorithm.