Back to search

Institutes outside Greece

Entropy in data compression, additive combinatorics and probability

Abstract

dc:description

This thesis has four parts:In the first part, the problem of lossless data compression with side information availableto both the encoder and the decoder is considered. The finite-blocklength fundamental limitsof the best achievable performance are defined, in two different versions of the problem:Reference-based compression, when a single side information string is used repeatedly incompressing different source messages, and pair-based compression, where a different sideinformation string is used for each source message. General achievability and conversetheorems are established for arbitrary source-side information pairs. Nonasymptotic normalapproximation expansions are proved for the optimal rate in both the reference-based and pairbased settings, for memoryless sources. These are stated in terms of explicit, finite-blocklengthbounds, that are tight up to third-order terms. Extensions that go significantly beyondthe class of memoryless sources are obtained. The relevant source dispersion is identifiedand its relationship with the conditional varentropy rate is established. Interestingly, thedispersion is different in reference-based and pair-based compression, and it is proved thatthe reference-based dispersion is in general smaller.Secondly, a discrete, asymptotic analogue of the entropy power inequality due to Tao isdiscussed. The nonasymptotic version of the result is obtained. Applications in informationtheory and connections with the entropic central limit theorem are discussed.In the third part, we recall some of the history of the information-theoretic approach toderiving core results in probability theory and give three new such proofs. A strengthenedversion of the central limit theorem for discrete random variables is established, relying onlyon information-theoretic tools and elementary arguments. It is shown that the relative entropybetween the standardised sum of n independent and identically distributed lattice randomvariables and an appropriately discretised Gaussian, vanishes as n tends to infinity. Then we give twonew information-theoretic proofs of finite versions of de Finetti’s classical representationtheorem for finite-valued random variables. We derive an upper bound on the relative entropy6between the distribution of the first k in a sequence of n exchangeable random variables,and an appropriate mixture over product distributions. The first result is stated for binaryrandom variables and the proof is based on estimating the dependence of the random variablesunder an appropriate conditioning. The second result is stated for random variables in ageneral finite alphabet. Its proof is nicely motivated by the Gibbs conditioning principle inconnection with statistical mechanics, and it follows along an appealing sequence of steps.The technical estimates required for these steps are obtained via the the method of types.The mixing measure is characterised in both cases as the law of the empirical measure of theoriginal sequence, and de Finetti’s result is recovered as a corollary.In the final part, we provide a collection of inequalities for the differential entropy of anarbitrary random variable convolved with a Gaussian. In terms of techniques, as well as ofthe results themselves, these inequalities lie in the interface between sumset inequalities forentropy and the central limit theorem.

Degree

thesis:*
Grantor dc:publisher
Institutes outside Greece
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Gavalakis, Lampros
  • Γαβαλάκης, Λάμπρος

Subjects

dc:subject × 24

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/57047

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Gavalakis, Lampros; Γαβαλάκης, Λάμπρος. Entropy in data compression, additive combinatorics and probability. Institutes outside Greece, 2022. http://hdl.handle.net/10442/hedi/57047