Efficient quantization and weak covering of high dimensional cubes

Abstract

Let ${\mathbb{Z}}_n=\{Z_1,\dots ,Z_n\}$ be a design; that is, a collection of $n$ points $Z_j\in [-1,1{]}^d$. We study the quality of quantization of $[-1,1{]}^d$ by the points of ${\mathbb{Z}}_n$ and the problem of quality of coverage of $[-1,1{]}^d$ by ${\mathcal{B}}_d({\mathbb{Z}}_n,r)$, the union of balls centred at $Z_j\in {\mathbb{Z}}_n$. We concentrate on the cases where the dimension $d$ is not small ($d\ge 5$) and $n$ is not too large, $n\le 2^d$. We define the design ${\mathbb{D}}_{n,\delta }$ as a $2^{d-1}$ design defined on vertices of the cube $[-\delta ,\delta {]}^d$, $0\le \delta \le 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\cap {\mathcal{B}}_d({\mathbb{Z}}_n,r))$. We provide results of a large-scale numerical investigation confirming the accuracy of the developed approximations and the efficiency of the designs ${\mathbb{D}}_{n,\delta }$.