Home

Optimal quantization of the standard multivariate normal distribution

Downloadone_dim_1_1000.zip Downloadone_dim_1001_5999.zip Downloadmult_dimensional_grids.zip

The compressed folder one_dim_1_1000.zip contains optimal quantization grids of the standard univariate normal distribution of size $ N=1 $ to $ N=1000 $, and one_dim_1001_5999.zip from the grids of size $ N=1001 $ to $ N=5999 $.

The compressed folder mult_dimensional_grids.zip contains optimized quantization grids of the standard multivariate normal distribution of size between $ N=1 $ and $ N=1450 $ and dimension between $ d = 2 $ and $ d = 10 $. (It does not contain the one-dimensional grids which are available separately.)

The files are in text format. In every case, the filename is N_d_nopti where N is the quantizer size and d is the dimension.

For a given size $ N $, the text files are organized as follows. It presents in the form of a matrix $ G = (G_{i,j}) $ with $ N+1 $ rows and $ d+3 $ columns.

  • On row $ i, i=1,\cdots,N $: element $ i $ of the grid and its companion parameters.
    $$ G_{i,1} = \left(\textrm{weight of the Voronoi cell of element } i \right)= \mathbb{P}[ \mathcal{N}(0,I_d) \in C_i(G) ]. $$
    $$ \{G_{i,j}, j=2, \cdots, d+2 \}= \left(\textrm{coordinates of element } i \right). $$
    $$ G_{i,d+2} =\left( \textrm{conditional local } L^2-\textrm{distortion of the cell of element } i\right) = \frac{\int_{C_i(G)} |z-G_{i,d}|^2 \mathcal{N}(0,I_d)(dz)}{G_{i,1}}. $$
    $$ G_{i,d+3} = \left(\textrm{conditional local } L^1-\textrm{distortion of the cell of element } i\right) = \frac{\int_{C_i(G)} |z-G_{i,d}| \mathcal{N}(0,I_d)(dz)}{G_{i,1}}. $$
  • On last row $ (i = N+1) $:
    $$ G_{N+1,j} = 0 \quad \textrm{ for }j=1, \cdots, d+1. $$
    $$ G_{N+1,d+2} = \left(\textrm{quadratic distortion of the quantization grid}\right). $$
    $$ G_{N+1,d+2} = \left(L^1-\textrm{distortion of the quantization grid}\right). $$
  • In particular we can verify that
    $$ \sum\limits_{i=1}^N G_{i,1} = 1, $$
    $$ \sum\limits_{i=1}^N G_{i,1} G_{i,d+2}= G_{N+1,d+2}, $$
    $$ \sum\limits_{i=1}^N G_{i,1} G_{i,d+3} = G_{N+1,d+3}. $$
Methodology:

  • The multi-dimensional grids were obtained by an incremental "splitting" method based on an optimization by a mixed Lloyd-CLVQ algorithm. The splitting method consists in appending to an optimized grid of $ N $ elements $ n $ random points to get the starting point for the optimization procedure for a quantizer of size $ N+n $.

    Note that the CLVQ procedure is only used for small values of $ N $.

  • The one-dimensional grids where obtained by deterministic methods. This is to directly minimize the quadratic distortion seen as a function of $ N $ values. Several methods are available as a tridiagonal Newton-Raphson method or a semi-closed Lloyd's algorithm. See article [1] for more details on these algorithms.
In the one dimensional setting, 32 significant figures are available.

References

  1. Gilles Pagès, and Jacques Printems, "Optimal quadratic quantization for numerics: the Gaussian case", Monte Carlo Methods and Applications, vol. 9, pp. 135–166, 2003.