Optimal Bregman quantization: existence and uniqueness of optimal quantizers revisited
Guillaume Boutoille, Gilles Pagès · 2025
Read Optimal Bregman quantization: existence and uniqueness of optimal quantizers revisited by Guillaume Boutoille, Gilles Pagès (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01746.txt.
Introduction
Quantization compresses data by replacing each value with one of a few representatives, chosen to keep the average error small under a chosen distance. Guillaume Boutoille and Gilles Pagès revisit in 2025 when such best representatives exist and when they are unique, for distances of the Bregman family. They prove existence under lighter assumptions than before, with care for the quadratic case.
Uniqueness follows in one dimension for strongly unimodal distributions, provided the generating function's third derivative bends in a controlled way. The result extends a classical theorem of Trushkin. The authors frame the pair of results as firmer ground under a widely used tool. Compression, clustering, and learning all stand on it.
Catalog record
| CREATOR | Guillaume Boutoille, Gilles Pagès |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01746
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Bregman quantization: existence and uniqueness of optimal quantizers revisited Guillaume Boutoille, Gilles Pagès Abstract In this paper we revisit the exsistence theorem for L r L^{r} -optimal quantization, r ≥ 2 r\geq 2 , with respect to a Bregman divergence: we establish the existence of optimal quantizaers under lighter assumptions onthe strictly convex function which generates the divergence, espcially in the quadratic case ( r = 2 r=2 ). We then prove a uniqueness theorem “à la Trushkin” in one dimension for strongly unimodal distributions and divergences gerated by strictly convex functions whiose thire dervative is either stictly log \log -convex or log \log -concave. Keywords: Bregman divergence ; Optimal quantization ; stationary quantizers ; uniqueness ; strongly unimodal distributions. 1 Introduction In computer vision, labeling represents a major cost that we aim to reduce as much as possible. Clustering algorithms are efficient tools to partition similar data into clusters in order to organize data set. Browsing these clusters allows a better visualisation of the data set and an easier labeling. For that purpose, clustering is a fundamental field of ”unsupervised” learning which aggregates procedures that have been widely studied across many disciplines. Most of the clustering methods consist in partitioning similar data into clusters usually “represented” or characterized by a prototype or codeword (either a typical true datum or a synthetic data). These codewords make up a codebook , such a codebook usually minimizes a loss function (quantization error). A widely used and studied clustering algorithm is the Euclidean k -means algorithm ( [ 17 , 11 ] ). In Information Theory, Signal Processing and Probability Theory, this algorithm is also known as the Lloyd (or Lloyd I) algorithm and goes back to the 1950s. At that time, it was a classified field of research in the Bell Labs, supported by the U.S. Navy (see the historical notes in the 1988 special issue of IEEE on Information Theory devoted to quantization). For probabilistic aspects, we refer to [ 9 ] who have proved most milestone theorems of the theory in a rigorous mathematical way and, more recently, [ 16 ] . Since the 1970’s (and even before), there has been a huge literature from Information Theory and automatic classification on the k -means algorithm in connection with optimal quantization theory. Among them we can cite the famous book by [ 8 ] . In this paper we revisit the main existence theorem for the optimal quantizers of a distribution P supported by a (nonempty) open set U\subset\mathbb{R}^{d} (in the sense that P(U)=1 ) when the loss function in the definition of the ( L^{r} -mean) quantization error is no longer a power of a norm on \mathbb{R}^{d} but a power of a Bregman divergence induced by a strictly convex function F:U\to\mathbb{R} . Let us recall that the Bregman divergence \phi_{{}_{F}} associated to a strictly convex is defined on U\times U\to\mathbb{R}_{+} by {\color[rgb]{0,0,0}\forall\,(\xi,x)\!\in U^{2},\quad\phi_{{}_{F}}(\xi,x)=\phi_{{}_{F}}(\xi,x):=F(\xi)-F(x)-\langle\nabla F(x)\,|\,\xi-x\rangle}, (1) where \langle\cdot\,|\,\cdot\rangle denotes the canonical inner product on \mathbb{R}^{d} . Indeed, the connection between these two frameworks is the case of the squared Euclidean norm which is its own Bregman divergence. In [ 1 ] , Banerjee and co-authors pointed out a close relation between Bregman divergences and log -likelihood of exponential families. This led them to extend the scope of k -means clustering algorithms by introducing these Bregman divergences as new similarity measures functions (a.k.a. local loss functions ) in the core of the algorithm instead of a squared Euclidean norm. This work led to a line of research about clustering based on Bregman divergences, see e.g. [ 7 ] , [ 10 ] , [ 15 ] ) among others. An in-depth anamysis of this extension of the k -means algorithm with Bregman divergnece as similarity measure is carried out in [ 2 , Chapter 4] and will soon be issued as a companion paper. Nevertheless, we want first to investigate optimal vector quantization theory in the same probabilistic spirit as that developed in Graf and Luschgy’s book ( [ 9 ] ) or, more recently, in [ 16 ] , i.e. when the distribution P to be quantized is a probability distribution rather than the empirical measure of a dataset (the data being modeled by a sample of i.i.d. random vectors in the statistical literature). So we first establish an existence result for such L^{r} -optimal quantizers under some seemingly slightly weaker assumptions on the function F than those found in the (mathematically rigorous) literature (see e.g. [ 7 ] ). We also investigate some properties of Bregman divergence based optimal quantizers known to be shared by regular optimal quantizers when the loss function is an Euclidean norm (see [ 9 , 16 ] ) like stationarity in the (pseudo-)quadratic case and its L^{r} -variants when r\neq 2 , but also the seemingly less commonly known fact that the distribution P under consideration assigns no mass to the boundaries of the Bregman–Voronoi cells of an optimal quantizer and other close properties. On the way, we provide existence result for the (r,\phi_{{}_{F}}) -mean of P under even less stringent assumptions on F . The (r,\phi_{{}_{F}}) -mean of P corresponds to a quantization of P at level n=1 . It is to be noticed that when r=2 , the (2,\phi_{{}_{F}}) -mean of P coincides with the standard mean of P whatever F is. The second main result, stated and established in Section 8 , is that we extend for Bregman divergence based quantization the celebrated uniqueness Trushkin theorem which states that, in one dimension and when \phi_{{}_{F}}(\xi)=F(\xi)=|\xi|^{2} , if the distribution P is strongly unimodal (i.e. is absolutely continuous with a \log -concave density on the real line), then stationary quantizers are unique. We prove that the uniqueness result remains true for our extended Bregman setting under an additional assumption on the function F , namely that its second derivative is either \log -convex or \log -concave. The paper is organized as follows: Section 2 is devoted to some short background on “regular” Optimal vector quantization (by regular, we mean that the loss function is a power of a norm) and the definitions of the mean quantization errors based on (powers of) Bregman divergence \phi_{{}_{F}} . We also introduce the distortion which is the functional version of the ( r th power) of the Bregman (r,\phi_{{}_{F}}) -mean quantization error. Section 5 , 6 and 7 are devoted to the existence theorem in the pseudo-quadratic case ( r=2 , see below) and, when r>2 , under appropriate integrability conditions on P and light additional conditions on F (on the boundary of U and at infinity). We also establish the differentiability of the distortion function, mostly as a tool to establish the existence of Bregman (r,\phi_{{}_{F}}) -optimal quantizers when r>2 . Section 8 is devoted to uniqueness of optimal quantizers at every level n\geq 1 when P is strongly unimodal and F is twice differentiable with F^{\prime\prime} either \log -convex or \log -concave as well. Our results are illustrated on several usual examples of Bregman divergences. 2 Definitions and background on regular L^{r} -optimal quantization w.r.t. a norm 2.1 Short background on L^{r} -optimal vector quantization Let \|.\| denote a norm on \mathbb{R}^{d} .