New approach to greedy vector quantization

DOI10.3150/21-BEJ1350MaRDI QIDQ2073221zbMATH OpenFDO

Authors Rancy El Nmeir, Harald Luschgy, Gilles Pagès

Publication date 1 February 2022

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.14145, https://projecteuclid.org/journals/bernoulli/volume-28/issue-1/New-approach-to-greedy-vector-quantization/10.3150/21-BEJ1350.full

zbMATH Keywords

distortion mismatchgreedy quantization sequenceLloyd's algorithmquantization-based numerical integrationquasi-Monte Carlo methodsrate optimality

Mathematics Subject Classification ID

Signal detection and filtering (aspects of stochastic processes) (60G35) Monte Carlo methods (65C05) Probabilistic models, generic numerical methods in probability and statistics (65C20)

Abstract: We extend some rate of convergence results of greedy quantization sequences already investigated in arXiv:1409.0732 [math.PR]. We show, for a more general class of distributions satisfying a certain control, that the quantization error of these sequences have an $n^{-frac1d}$ rate of convergence and that the distortion mismatch property is satisfied. We will give some non-asymptotic Pierce type estimates. The recursive character of greedy vector quantization allows some improvements to the algorithm of computation of these sequences and the implementation of a recursive formula to quantization-based numerical integration. Furthermore, we establish further properties of sub-optimality of greedy quantization sequences.

Review text

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.

Recommendations

• Greedy vector quantization
• Introduction to vector quantization and its applications for numerics
• Fast rates for empirical vector quantization
• Convergence of Vector Quantizers with Applications to Optimal Quantization
• Individual Convergence Rates in Empirical Vector Quantizer Design

Cites work

• A quantization algorithm for solving multidimensional discrete-time optimal stopping problems
• A space quantization method for numerical integration
• A stochastic quantization method for nonlinear problems.
• Asymptotic quantization error of continuous signals and the quantization dimension
• Calculation of discrepancy measures and applications
• Discrepancy and integration of continuous functions
• Distortion mismatch in the quantization of probability measures
• Foundations of quantization for probability distributions
• Functional quantization rate and mean regularity of processes with an application to Lévy processes
• Greedy vector quantization
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 699438 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• Introduction to vector quantization and its applications for numerics
• Long-term planningversusshort-term planning in the asymptotical location problem
• Numerical probability. An introduction with applications to finance
• Quantization of probability distributions under norm-based distortion measures

Cited in

(7)

• Greedy vector quantization
• Performance analysis of greedy algorithms for minimising a maximum mean discrepancy
• A Multigrid Approach to the Scalar Quantization Problem
• scientific article; zbMATH DE number 5506905 (Why is no real title available?)
• Introduction to vector quantization and its applications for numerics
• Quantization dimensions of compactly supported probability measures via Rényi dimensions
• A Lloyd-stabilized Voronoi particle method

This page was built for publication: New approach to greedy vector quantization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073221)