Optimal vector quantization in terms of Wasserstein distance

  • The optimal quantizer in memory-size constrained vector quantization induces a quantization error which is equal to a Wasserstein distortion. However, for the optimal (Shannon-)entropy constrained quantization error a proof for a similar identity is still missing. Relying on principal results of the optimal mass transportation theory, we will prove that the optimal quantization error is equal to a Wasserstein distance. Since we will state the quantization problem in a very general setting, our approach includes the R\'enyi-$\alpha$-entropy as a complexity constraint, which includes the special case of (Shannon-)entropy constrained $(\alpha = 1)$ and memory-size constrained $(\alpha = 0)$ quantization. Additionally, we will derive for certain distance functions codecell convexity for quantizers with a finite codebook. Using other methods, this regularity in codecell geometry has already been proved earlier by Gy\"{o}rgy and Linder.

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • Export XML

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Wolfgang Kreitmeier
URN:urn:nbn:de:bvb:739-opus-22502
Document Type:Preprint
Language:English
Year of Completion:2011
Date of Publication (online):2011/04/18
Publishing Institution:Universität Passau
Release Date:2011/04/18
Tag:R\'enyi-$\alpha$-entropy; Wasserstein distance; codecell convexity; optimal quantization error
GND Keyword:Entropie; Maßtheorie; Quantisierung; Transporttheorie
Note:
This is a preprint of an article accepted for publication in the Journal of Multivariate Analysis ISSN 0047-259X. The original publication is available at http://www.elsevier.com/. The digital object identifier (DOI) of the definitive article is 10.1016/j.jmva.2011.04.005.
 
Source:Journal of Multivariate Analysis. ISSN 0047-259X
Institutes:Fakultät für Informatik und Mathematik / Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Classification:60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Bxx Probability theory on algebraic and topological structures / 60B10 Convergence of probability measures
60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Exx Distribution theory [See also 62Exx, 62Hxx] / 60E05 Distributions: general theory
62-XX STATISTICS / 62Exx Distribution theory [See also 60Exx] / 62E17 Approximations to distributions (nonasymptotic)
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Pxx Theory of data / 68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) [See also 94Axx]
94-XX INFORMATION AND COMMUNICATION, CIRCUITS / 94Axx Communication, information / 94A17 Measures of information, entropy
94-XX INFORMATION AND COMMUNICATION, CIRCUITS / 94Axx Communication, information / 94A29 Source coding [See also 68P30]
open_access (DINI-Set):open_access
Licence (German):License LogoStandardbedingung laut Einverständniserklärung

$Rev: 13581 $