Efficient quantization and weak covering of high dimensional cubes
share
Let ℤ_n = {Z_1, ..., Z_n} be a design; that is, a collection of n points Z_j ∈ [-1,1]^d. We study the quality of quantization of [-1,1]^d by the points of ℤ_n and the problem of quality of covering of [-1,1]^d by B_d(ℤ_n,r), the union of balls centred at Z_j ∈ℤ_n. We concentrate on the cases where the dimension d is not small (d≥ 5) and n is not too large, n ≤ 2^d. We define the design 𝔻_n,δ as the maximum-resolution 2^d-1 design defined on vertices of the cube [-δ,δ]^d, 0≤δ≤ 1. For this design, we derive a closed-form expression for the quantization error and very accurate approximations for the coverage area vol([-1,1]^d ∩ B_d(ℤ_n,r)). We conjecture that the design 𝔻_n,δ with optimal δ is the most efficient quantizer of [-1,1]^d under the assumption n ≤ 2^d and it is also makes a very efficient (1-γ)-covering. We provide results of a large-scale numerical investigation confirming the accuracy of the developed approximations and the efficiency of the designs 𝔻_n,δ.
READ FULL TEXT