Asymptotics of Constrained Quantization for Compactly Supported Measures

Chenxing Qian · 2025

Read Asymptotics of Constrained Quantization for Compactly Supported Measures by Chenxing Qian (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-2505-10801.txt.

Introduction

Chenxing Qian studies compressed summaries limited to an allowed region in this 2025 paper, writing alone. Quantization replaces a probability distribution with a few representative points. The constrained version forces those points to live inside a chosen set, as when sensors may sit only in certain places.

Qian tracks the error as the point count grows. The error falls toward a floor set by the distance to the allowed set. He bounds the gap using a nearest-point map that pushes the distribution into the region. Different error powers get matching bounds, and a growth condition yields precise decay rates. The results sharpen a tool used in coding and machine learning.

Catalog record

CREATORChenxing Qian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE109 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-10801

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asymptotics of Constrained Quantization for Compactly Supported Measures Chenxing Qian Abstract . We study constrained quantization of a compactly supported probability P P on ℝ D \mathbb{R}^{D} using codebooks in a nonempty closed set S S . For 0 < r ≤ ∞ 0<r\leq\infty , the constrained quantization error and its baseline are e n , r = inf α ⊂ S 1 ≤ | α | ≤ n ‖ dist ⁡ ( ⋅ , α ) ‖ L r ​ ( P ) , L r = ‖ dist ⁡ ( ⋅ , S ) ‖ L r ​ ( P ) . e_{n,r}=\inf_{\begin{subarray}{c}\alpha\subset S\\ 1\leq|\alpha|\leq n\end{subarray}}\|\operatorname{dist}(\cdot,\alpha)\|_{L^{r}(P)},\qquad L_{r}=\|\operatorname{dist}(\cdot,S)\|_{L^{r}(P)}. We establish attainment and convergence e n , r ↓ L r e_{n,r}\downarrow L_{r} . For finite r r , set Δ n , r = e n , r r − L r r \Delta_{n,r}=e_{n,r}^{r}-L_{r}^{r} . A Borel nearest-point selector T T gives a projected measure μ = T ∗ ​ P \mu=T_{*}P . For a probability η \eta and s > 0 s>0 , define the quantization error q n , s ​ ( η ) = inf α ⊂ ℝ D 1 ≤ | α | ≤ n ‖ dist ⁡ ( ⋅ , α ) ‖ L s ​ ( η ) . q_{n,s}(\eta)=\inf_{\begin{subarray}{c}\alpha\subset\mathbb{R}^{D}\\ 1\leq|\alpha|\leq n\end{subarray}}\|\operatorname{dist}(\cdot,\alpha)\|_{L^{s}(\eta)}. We obtain e n , r − L r ≤ 2 q n , r ( μ ) , Δ n , r ≤ C r q n , 1 ( μ ) ( 1 ≤ r < ∞ ) , e_{n,r}-L_{r}\leq 2q_{n,r}(\mu),\qquad\Delta_{n,r}\leq C_{r}q_{n,1}(\mu)\quad(1\leq r<\infty), with C r C_{r} independent of n n , and Δ n , r ≤ 2 r ​ q n , r ​ ( μ ) r \Delta_{n,r}\leq 2^{r}q_{n,r}(\mu)^{r} for 0 < r < 1 0<r<1 . In addition, e n , ∞ − L ∞ ≤ 2 ​ c n ​ ( E ) e_{n,\infty}-L_{\infty}\leq 2c_{n}(E) , where E E is the nearest-point image of supp ​ ( P ) \text{supp}{(P)} and c n ​ ( E ) c_{n}(E) is its covering radius. For a finite measure ν \nu , define the quantization cost 𝒱 n , β ​ ( ν ) = inf α ⊂ ℝ D 1 ≤ | α | ≤ n ∫ dist ⁡ ( y , α ) β ​ 𝑑 ν ​ ( y ) . \mathcal{V}_{n,\beta}(\nu)=\inf_{\begin{subarray}{c}\alpha\subset\mathbb{R}^{D}\\ 1\leq|\alpha|\leq n\end{subarray}}\int\operatorname{dist}(y,\alpha)^{\beta}\,d\nu(y). For 1 ≤ r < ∞ 1\leq r<\infty , a weighted power-growth condition with exponent β > 0 \beta>0 on a fixed source set F F gives Δ n , r ≥ 𝒱 n , β ​ ( ν F ) \Delta_{n,r}\geq\mathcal{V}_{n,\beta}(\nu_{F}) , where ν F = T ∗ ​ ( w ​ P | F ) \nu_{F}=T_{*}(wP|_{F}) . If d ​ ν F = w ^ ​ d ​ η d\nu_{F}=\widehat{w}\,d\eta for a compactly supported reference probability η \eta and w ^ ∈ A p ​ ( η ) \widehat{w}\in A_{p}(\eta) , 1 < p < ∞ 1<p<\infty , then Δ n , r ≥ ν F ​ ( ℝ D ) [ w ^ ] A p ​ ( η ) ​ q n , β / p ​ ( η ) β . \Delta_{n,r}\geq\frac{\nu_{F}(\mathbb{R}^{D})}{[\widehat{w}]_{A_{p}(\eta)}}q_{n,\beta/p}(\eta)^{\beta}. These comparisons yield bounds for the quantization dimensions defined by e n , r − L r e_{n,r}-L_{r} and Δ n , r 1 / r \Delta_{n,r}^{1/r} , with distinct behavior at positive and zero baselines. Convex and uniformly prox-regular constraints supply the growth weights through their projection inequalities. Circle and lifted Cantor distributions give matching quadratic-excess rates, while rectifiable weighted projections give lower Zador estimates. 2020 Mathematics Subject Classification Primary 41A29; Secondary 60D05, 28A80 1. Introduction 1.1. Background and the problem Quantization studies the approximation of a probability distribution by a finite set of representatives. Its asymptotic theory relates the number of representatives and the approximation error to the distribution of mass; see Graf and Luschgy [ GL00 ] for the general theory and Gray and Neuhoff [ GN98 ] for its information-theoretic background. For singular probabilities, the quantization dimension also records features of the measure that enter the approximation rate; self-similar distributions provide a central class of examples [ GL01 , GL02 ] . In constrained quantization, the representatives must belong to a prescribed closed set S\subset\mathbb{R}^{D} . Pandey and Roychowdhury determine optimal codebooks and errors for uniform distributions with line and circle constraints [ PR26 ] , and for the Cantor distribution under several constraints [ PR24 ] . These explicit configurations show how the constraint affects both the limiting error and the rate at which it is approached. When the source is separated from S , that limit is positive, so the asymptotic problem can be formulated as estimating the difference between the quantization error and its limit. For an upper estimate, choose finitely many centers that approximate the nearest points on S . The triangle inequality bounds the distance from a source point to these centers by its distance to S plus the approximation error of its nearest point. For a lower estimate, one instead controls how much the source-to-center distance increases as the center moves away from a nearest point. Integrating this increase over a suitable part of the source gives a lower bound for the excess. Our first main result is an upper comparison based on nearest-point projection. A Borel nearest-point selector transfers ordinary quantization estimates for the projected source measure to upper bounds for the constrained excess. This comparison holds for arbitrary nonempty closed constraints, without requiring unique nearest points, continuity of the selector, or local concentration estimates. At infinite order, we obtain an upper bound by covering the full nearest-point image of the source support. For lower bounds, we allow the power-growth coefficient to vary with the source point and incorporate it into a weighted projected measure. An A_{p} condition on its density gives a comparison with ordinary quantization errors of a reference probability measure, without imposing small-ball regularity on that measure. Under uniform growth and an upper ball-mass estimate, the power-law lower bound also follows from the general distortion theorem of Riegler, Koliander and Bölcskei [ RKB23 ] ; see Example 22 . The weighted formulation applies to convex and uniformly prox-regular constraints and allows growth weights with no positive uniform lower bound. For the smaller concentric disk and the lifted Cantor distribution, we obtain \Delta_{n,2}=e_{n,2}^{2}-L_{2}^{2}\asymp n^{-2/d} , where d is the Hausdorff dimension of the projected support. 1.2. Notation and main results Throughout the article, P is a Borel probability with nonempty compact support K\subset\mathbb{R}^{D} , and S\subset\mathbb{R}^{D} is nonempty and closed, except in the finite-moment existence statement. Write \rho(x,y)=|x-y| and \rho(x,A)=\inf_{a\in A}|x-a| for a nonempty set A . For n\geq 1 , put \mathcal{A}_{n}(S)=\{\alpha\subset S:1\leq|\alpha|\leq n\}. An admissible codebook for e_{n,r}(P;S) means a nonempty finite set \alpha\subset S with |\alpha|\leq n , that is, \alpha\in\mathcal{A}_{n}(S) . For a different constraint A , admissibility means membership in \mathcal{A}_{n}(A) . For 0<r<\infty define (1.1) F_{r}(\alpha)=\left(\int_{K}\rho(x,\alpha)^{r}\,dP(x)\right)^{1/r},\qquad e_{n,r}(P;S)=\inf_{\alpha\in\mathcal{A}_{n}(S)}F_{r}(\alpha). For r=\infty , use F_{\infty}(\alpha)=\max_{x\in K}\rho(x,\alpha) . The collection of minimizers is denoted by C_{n,r}(P;S) . When the source and constraint are fixed, we write e_{n,r} . The metric projection and distance baseline are (1.2) \begin{gathered}b(x)=\rho(x,S),\qquad\pi_{S}(x)=\{a\in S:|x-a|=b(x)\},\qquad

Read the complete text