Locally Optimal Functional Quantization
Harald Luschgy, Gilles Pagès · 2025
Read Locally Optimal Functional Quantization by Harald Luschgy, 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-2504-08681.txt.
Introduction
Harald Luschgy and Gilles Pagès wrote this 2025 arXiv note in probability theory. It concerns quantization, which replaces a random curve with the nearest of a few fixed curves. A quantizer can be best overall or merely best in its neighborhood. The authors show the two notions meet for distributions on a Banach space. Any locally best quantizer with points inside the support acts like a globally best one. It satisfies the same stationarity condition that marks an optimum.
Catalog record
| CREATOR | Harald Luschgy, Gilles Pagès |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08681
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Locally Optimal Functional Quantization Harald Luschgy, Gilles Pagès Abstract In this note we demonstrate that locally optimal functional quantizers for probability distributions P P on a Banach space lying in the support of P P behave exactly like globally optimal functional quantizers in terms of stationarity. Keywords: functional quantization ; stationary quantizer ; locally optimal quantizers. 1 Introduction We will use the notations of [ 1 ] . Let X be a Radon random vector on a probability space (\Omega,{\cal A},\mathbb{P}) taking its values in a Banach space (E,\|\cdot\|) equipped with its Borel \sigma -algebra {\cal B}or(E) . This means that X is \big({\cal A},{\cal B}or(E)\big) -measurable and its distribution P=\mathbb{P}_{{}_{X}} is a Radon probability measure on {\cal B}or(E) (in the sense that it is inner regular). Notice that stochastic processes in continuous time can often be seen as random vectors having values in a Banach function space. Let d(x,A):=\inf\{\|x-a\|:\;a\!\in A\} denote the distance of x\!\in E to the nonempty subset A\subset E . For n\!\in\mathbb{N} and r\!\in(0,+\infty) the L^{r} -quantization problem for P (or X ) at level n consists in minimizing e_{r}(\Gamma,P):=\big(\mathbb{E}\,d(X,\Gamma)^{r}\big)^{1/r} (1) over all subsets \Gamma\subset E , \Gamma\neq\varnothing with {\rm card}(\Gamma)\leq n . Such a subset is called n -quantizer (or n -codebook or n -grid ). Definition 1.1 . (a) The n th-level L^{r} -quantization error of P is defined as e_{r,n}(P,E):=\inf\big\{e_{r}(\Gamma,P):\Gamma\subset E,\;1\leq{\rm card}((\Gamma)\leq n\big\}. (b) Assume \mathbb{E}\,\|X\|^{r}=\int\|x\|^{r}dP(x)<+\infty (so that e_{r,n}(P,E)<+\infty for every n\geq 1 ). A quantizer \Gamma\subset E with {\rm card}(\Gamma)\leq n is called L^{r} -optimal n -quantizer for P of e_{r}(\Gamma,P)=e_{r,n}(P,E). Let {\cal C}_{r,n}(P,E) denote the set of all L^{r} -optimal n -quantizers for P . A Voronoi quantization of X induced by a finite quantizer \Gamma\subset E is simply the projection of X onto \Gamma following the nearest neighbour rule as explained below. Definition 1.2 . Let \Gamma\subset E be a finite quantizer and a\!\in\Gamma . Then V_{a}(\Gamma):=\big\{x\!\in E:\|x-a\|=d(x,\Gamma)\big\} is called the (closed) Voronoi cell and W_{a}(\Gamma):=\big\{x\!\in E:\|x-a\|<d(x,\Gamma\setminus\{a\})\big\} the open Voronoi cell of a induced by \Gamma . A Borel measurable partition \{C_{a}(\Gamma):a\!\in\Gamma\} of E is called Voronoi partition induced by \Gamma if C_{a}(\Gamma)\subset V_{a}(\Gamma)\;\mbox{ for every }a\!\in\Gamma. Since the distance function is continuous, V_{a}(\Gamma) is in fact a closed set of E and W_{a}(\Gamma) an open set. It should also be obvious that, for a Voronoi partition \{C_{a}(\Gamma):a\!\in\Gamma\} , W_{a}(\Gamma)\subset C_{a}(\Gamma)\mbox{ for every }\;a\!\in\Gamma. (2) Given a finite quantizer \Gamma\subset E and a Voronoi partition \{C_{a}(\Gamma):a\!\in\Gamma\} of E induced by \Gamma , define {\rm Proj}_{\Gamma}:E\to E,\quad{\rm Proj}_{\Gamma}(x):=\sum_{a\in\Gamma}\mbox{\bf 1}_{C_{a}(\Gamma)}(x). Note that {\rm Proj}_{\Gamma} depends on the Voronoi partition and not only on \Gamma . The random vector \widehat{X}=\widehat{X}^{\Gamma}={\rm Proj}_{\Gamma}(X) is called Voronoi quantization of X induced by \Gamma or \Gamma -quantization of X . Its L^{r} -(mean)error satisfies \big(\mathbb{E}\,\|X-\widehat{X}\|^{r}\big)^{1/r}=e_{r}(\Gamma,P) and so does not depend on the specific choice of the Voronoi partition induced by \Gamma . Functional quantization can thus be seen as a way to discretize the path space of a stochastic process. So far, we have dealt with (functional) quantizers viewed as a finite subset of E . For our present purpose it is convenient to introduce them also a n -tuples. The L^{r} -distortion function of level n is defined by G_{r,n}^{P}:E^{n}\to\mathbb{R}_{+},\;G_{r,n}^{P}(a):=\mathbb{E}\min_{1\leq i\leq n}\|X-a_{i}\|^{r}. (3) Note that G_{r,n}^{P} is continuous w.r.t. the product topology on E^{n} (in fact (G_{r,n}^{P})^{1/r} is even Lipschitz continuous with Lipschitz coefficient 1 w.r.t. the \max -norm \|(x_{1},\ldots,x_{n})\|_{\ell^{\infty}}:=\max_{1\leq i\leq n}\|x_{i}\| on E^{n} if r\geq 1 ), convex for n=1 and r\geq 1 but typically not convex if n\geq 2 . We have e_{r,n}(P,E)^{r}=\inf_{a\in E^{n}}G_{r,n}^{P}(a). We will introduce the notion of L^{r} -stationarity quantizers as critical points of G_{r,n}^{P} . The Banach space E and its norm \|\cdot\| is said to be smooth if the norm is Gâteaux-differentiable at any x\neq 0 , where a function F:E\to\mathbb{R} is Gâteaux-differentiable at x\!\in E if there exists \nabla F(x)\!\in E^{*} (topological dual space of E ) such that \lim_{t\to 0}\frac{F(x+ty)-F(x)}{t}=\langle\nabla F(x),y\rangle for every y\!\in E . We write \langle u,y\rangle for u(y) for u\!\in E^{*} and y\!\in E . Then \nabla\|\cdot\|(x) is contained in the unit sphere of E^{*} when the norm is Gâteaux-differentiable at x . In fact, we only need almost sure smoothness of the norm. (This weaker condition is of interest e.g. for L^{1} -spaces E .). For convenience, a finite quantizer \Gamma\subset E is called admissible for P if P\left(\bigcup_{a\in\Gamma}W_{a}(\Gamma)\right)=1. (4) An n -tuple (a_{1},\ldots,a_{n})\!\in E^{n} with a_{i}\neq a_{j} is admissible for P if its associated n -quantizer \{a_{1},\ldots,a_{n}\} is. Proposition 1.3 . Let r\geq 1 and assume \displaystyle\int_{E}\|x\|^{r}dP(x)<+\infty . Assume that the norm is Gâteaux-differentiable at a-x P(dx) - a.e. on E\setminus\{a\} . Let r>1 . Then the L^{r} -distortion function G_{r,n}^{P} is Gâteaux-differentiable at every admissible n -tuple (a_{1},\ldots,a_{n}) with a Gâteaux derivative given by \nabla G^{P}_{r,n}(a_{1},\ldots,a_{n})=r\bigg(\mathbb{E}\,\mbox{\bf 1}_{C_{a_{i}}(\Gamma)\setminus\{a_{i}\}}(X)\|X-a_{i}\|^{r-1}\nabla\|\cdot\|(a_{i}-X)\bigg)_{1\leq i\leq n}\!\in(E^{*})^{n}, where \{C_{a_{i}}(\Gamma):1\leq i\leq n\} denotes any Voronoi partition induced by \Gamma=\{a_{1},\ldots,a_{n}\} . When r=1 , the above result holds true for admissible n -tuples (a_{1},\ldots,a_{n}) satisfying P(\{a_{1},\ldots,a_{n}\})=0 . Proof. See Proposition 1.3.1 in [ 1 ] . \Box Note that (E^{n})^{*}=(E^{*})^{n} with duality \langle u,x\rangle=\sum_{j=1}^{n}\langle u_{j},x_{j}\rangle , where u=(u_{1},\ldots,u_{n})\!\in(E^{*})^{n} and x=(x_{1},\ldots,x_{n})\!\in E^{n} . Let us point out that the integrals (expectations) occurring in the above formulas for \nabla G_{r,n}^{P} and in the subsequent definition are to be seen as Gelfand integrals . Our notion of stationarity avoids admissibility. Definition 1.4 . Let r\geq 1 and assume \displaystyle\int_{E}\|x\|^{r}dP(x)<+\infty . Assume that the norm is Gâteaux-differentiable at a-x P(dx) - a.e. on E\setminus\{a\} for every a\!\in E . A quantizer \Gamma\subset E with {\rm card}(\Gamma)=n and P(\Gamma)=0 when r=1 is called L^{r} stationary n -quantizer for P if there exists a Voronoi partition \{C_{a}(\Gamma):a\!\in\Gamma\} induced by \Gamma such that P\big(C_{a}(\Gamma)\big)>0 and \mathbb{E}\,\mbox{\bf 1}_{C_{a}(\Gamma)\setminus\{a\}}(X)\|X-a\|^{r-1}\nabla\|\cdot\|(a-X)\stackrel{{\scriptstyle E^{*}}}{{=}}0 (5) for every a\!\in\Gamma . (Here x\stackrel{{\scriptstyle E^{*}}}{{=}}0 means that x is equal to the zero of E^{*} ). 2 Local minima of the distortion functions Let {\rm supp}(P) denote the support of P which exists in our setting. Local minima of the L^{r} -distortion function G_{r,n}^{P} with components lying in {\rm supp}(P) behave exactly like global minima although G_{r,n}^{P} is not convex for n\geq 2 . For global minima see [ 1 , Sections 1.2 and 1.3] . In the subsequent results let r\!\in(0,+\infty) and assume \displaystyle\int_{E}\|x\|^{r}dP(x)<+\infty . Theorem 2.1 . Let a=(a_{1},\ldots,a_{n}) be a local minimum of G_{r,n}^{P} with a_{i} a non-isolated point of {\rm supp}(P) for every i\!\in\{1,\ldots,n\} . (a) The components a_{i} of a are pairwise distinct and if r\geq 1 , then for every i\!\in\{1,\ldots,n\} and every C\!\in{\cal B}(E) with W_{a_{i}}\big(\{a_{1},\ldots,a_{n}\}\big)\subset C\subset V_{a_{i}}\big(\{a_{1},\ldots,a_{n}\}\big) , a_{i}\!\in{\rm argmin}_{y\in E}G_{r,1}^{P(\cdot|C)}(y) or, equivalently, \{a_{i}\}\!\in{\cal C}_{r,1}\big(P(\cdot\,|\,C),E\big) . (b) Let r\geq 1 . Assume that the norm is Gâteaux differentiable at b-x P(\mathrm{d}x) -a.e. on E\setminus\{b\} for every element b of E and P(\{a_{i}\})=0 for every i when r=1 . Then \Gamma=\{a_{1},\ldots,a_{n}\} is an L^{r} -stationary n -quantizer for P . If E is strictly convex, then \Gamma is admissible for P . Proof. (a) Let U\subset E^{n} be an open neighbourhood of a such that G_{r,n}^{P} has a global minimum at a on U . We may assume that U=\prod_{i=1}^{n}U_{i} has a product form, where U_{i}\subset E are open neighbourhoods of a_{i} . Let N denote the number of