New approach to greedy vector quantization (Q2073221)

Optimal vector quantization is a technique derived from signal processing, initially devised to optimally discretize a continuous stationary signal for its transmission. Its goal is to find the best approximation of a continuous probability distribution by a discrete one. If \(X\) is a \(d\)-dimensional variable and \(\Gamma=\{x_1,\cdots, x_n\}\) is a \(d\)-dimensional grid of size \(n\), then the idea is to approximate \(X\) by \(q(X)\), where \(q\) is a Borel function defined on \(\mathbb R^d\) and having values in \(\Gamma\). In this paper, the study from [\textit{H. Luschgy} and \textit{G. Pagès}, J. Approx. Theory 198, 111--131 (2015; Zbl 1398.60074)] is continued obtaining a new approach to greedy vector quantization. Some rate of convergence results of greedy quantization sequences are extended to a much larger class of functions. It is shown how the recursive character of greedy quantization provides several improvements to the algorithm obtained in the previous quoted paper. This recursive formula is introduced first in the one-dimensional case, and then extended to the multi-dimensional case for product greedy quantization sequences, computed from one-dimensional sequences, used to reduce the cost of implementations while always preserving the recursive character. The paper is organized in six sections, the first one being an introduction into the topic. The second section is devoted to some extensions of the known results and a Pierce type non-asymptotic estimates relying on micro-macro inequalities applied to a certain class of auxiliary probability distributions \(\nu\). In the third section, the distortion mismatch problem is solved and extended. Improvements applied to the algorithm of designing the greedy sequences, as well as the new approach for greedy quantization-based numerical integration are presented in the fourth section. Numerical applications and examples are given in the fifth section of the paper. In the last section, based on numerical experiments, some properties of the one-dimensional quadratic greedy quantization sequences are presented. The sub-optimality of greedy quantization sequences, convergence of standard and weighted empirical measures, the stationarity and quasi-stationarity and the discrepancy of greedy sequences are studied and analyzed, to see to what extent greedy sequences can be close to optimality.