See discussions, stats, and author profiles for this publication at: [Link]
net/publication/334279836
Information Theory and Data Compression
Presentation · April 2019
CITATIONS READS
0 1,269
1 author:
Adric Peccarelli
Northern Illinois University
2 PUBLICATIONS 2 CITATIONS
SEE PROFILE
All content following this page was uploaded by Adric Peccarelli on 06 July 2019.
The user has requested enhancement of the downloaded file.
Information Theory and Data Compression
Adric Peccarelli
Northern Illinois University
April 19, 2019
[Link](NIU) Information Theory April 19, 2019 <1>
This presentation is for consideration for the completion of
the Math 795 PhD requirement and is based on:
Wu, Yihong and Verdu, S. (August 2010). "Rényi
Information Dimension: Fundamental Limits of Almost
Lossless Analog Compression". IEEE Transactions on
Information Theory. 56 (8): 3721:3748
[Link](NIU) Information Theory April 19, 2019 <2>
Outline
Background
Shannon’s Entropy
Information Dimension
Rényi’s Entropy
Data Compression
Conclusion
[Link](NIU) Information Theory April 19, 2019 <3>
Background
Information Theory is the study of the quantification and
transmission of information.
This area was developed in part by Claude Shannon in 1948
in an attempt to find fundamental limits on communication
operations.
Another key contributor in this area is Alfred Rényi, whose
contributions include the concept of Information Dimension.
After exploring these topics, we will relate them to data
compression and its use in many areas, including statistics.
[Link](NIU) Information Theory April 19, 2019 <4>
Background
A data communication source has three elements: the data,
a channel, and the receiver.
Shannon determined that one of the main issues is how well
the receiver deciphers the data based on what was provided
by the channel.
From this issue came one of the key measures of
Information Theory: entropy, or the measure of uncertainty
in a random variable or process.
Remark
Variance is another measure of uncertainty, which is centered
around the distribution mean, as opposed to entropy which
considers the distribution of data as a whole.
[Link](NIU) Information Theory April 19, 2019 <5>
Shannon’s Entropy
Shannon defined the Information Content for a random
variable X as I(X) = log2 (p (x )) and proposed four axioms
for information measures:
Monotonicity: I(X) is monotonic in p. Increases in the
probability decreases the information from an observed
event, and vice versa
I(1)=0. Events that always occur contain no information.
Non-Negativity: I(X) 0
I(X1 ; X2 ) = I(X1 ) + I(X2 ) for X1 ?? X2
[Link](NIU) Information Theory April 19, 2019 <6>
Shannon Entropy
For a discrete probability distribution where for i 2 N,
P (X = xi ) = pi (x ) 0 and ni=1 pi (x ) = 1, Shannon
Entropy is defined as the Expected Information Content:
Hs (X ) = Hs (p1 ; : : : pn )
= E [I(X)]
= E [ log2 (p (x ))]
= ni=1pi (x ) log2(pi (x ))
From here on, all log bases are assumed to equal 2.
[Link](NIU) Information Theory April 19, 2019 <7>
Properties of Shannon Entropy
Continuity: Hs (p1 ; : : : ; pn ) is continuous for
X 2 Rn 8pi ; i = 1; : : : ; n.
Symmetry: Hs (p1 ; p2 ; : : : ; pn ) = Hs (pn ; : : : ; p2 ; p1 ) is
invariant under permutations of X 8pi ; i = 1; : : : ; n.
Monotonicity: Maximum entropy occurs when all events are
equiprobable i.e.
Hs (p1 ; p2 ; : : : ; pn ) Hs ( n1 ; n1 ; : : : ; n1 ) = log(n )
pi (x ) log2 (pi (x )) = 0 for any pi (x ) = 0. (By convention)
Hs (X ) = 0 for any pi (x ) = 1
[Link](NIU) Information Theory April 19, 2019 <8>
Example of Shannon entropy
Consider a coin with p = 0:5
Hs (X ) = ni=1pi (x ) log(pi (x ))
= 2i =10:5 log(0:5)
= [0:5 ( 1) + 0:5 ( 1)]
= 1 bit of information per toss of the coin
Consider a biased coin with one side having p = 0:6
Hs (X ) = ni=1pi (x ) log(pi (x ))
= p log p q log q
= 0:6 log 0:6 0:4 log 0:4
0:97095 bits < 1 bit
[Link](NIU) Information Theory April 19, 2019 <9>
Information Dimension
Although not as well known as entropy, another important
measure in information theory was defined by Alfred Rényi
as the Information Dimension (or entropy dimension) of a
probability distribution.
Information dimension measures the rate of growth of the
information given by successively finer discretizations.
[Link](NIU) Information Theory April 19, 2019 <10>
Information Dimension
Definition 1: Let X be an arbitrary real-valued random
variable. For m 2 N, let the discretization of X be
hX im = bmX
m
c:
Define
Hs (hX im )
d (X ) = lim inf
m !1 log m
and
Hs (hX im )
d (X ) = lim sup
m !1 log m
where d (X ) and d (X ) are called the lower and upper
information dimensions of X (resp.)
[Link](NIU) Information Theory April 19, 2019 <11>
Information Dimension
When d (X ) = d (X ), we get what is called the information
dimension of X:
Hs (hX im )
d (X ) = lim
m !1 log m
Renyi also defined
!1(Hs (hX im )
c (X ) =
H lim d (x ) log m )
m
as the Entropy of Dimension d (X ).
[Link](NIU) Information Theory April 19, 2019 <12>
Properties of Information Dimension
Provided Hs (bX c) < 1; 0 d (X ) d (X ) 1.
If Hs (bX c) = 1, d (X ) = 1.
For X 2 Rn ; 0 d (X ) d (X ) n.
d (X ) and d (X ) are unchanged when ceiling or rounding
functions are used in lieu of the floor function.
[Link](NIU) Information Theory April 19, 2019 <13>
Decomposition
Lebesgue Decomposition Theorem: A probability
distribution can be uniquely represented as the mixture
F = pFd + qFc + rFs
where Fd is discrete, Fc is absolutely continuous, and Fs is
singular, with p + q + r = 1 and p ; q ; r 0
[Link](NIU) Information Theory April 19, 2019 <14>
Decomposition
Theorem 1: Let X be a random variable such that
Hs (bX c) < 1. Assume the distribution of X can be
expressed by the Lebesgue Decomposition Theorem as
F = (1 )Fd + Fc
where 0 1, then
d (X ) =
Furthermore, due to the finiteness of Hs (X )
c (X ) = (1
H )Hs (Fd ) + h (Fc ) + h2 ()
where Hs (Fd ) is the Shannon entropy of Fd , h (Fc ) is the
differential entropy of Fc , and
h2 () = log + (1 ) log
1 1
: (Binary Entropy)
1
[Link](NIU) Information Theory April 19, 2019 <15>
Consequences of Theorem 1
For a discrete random variable X, d (X ) = 0 and H
c (X ) is
the Shannon entropy of X.
For a absolutely continuous random variable X, d (X ) = 1
c (X ) is the differential entropy of X with support S
and H
given by Z
h (X ) = p (x ) log(p (x ))dx
S
For a discrete-continuous mixture, d (X ) = and H
c (X ) is
the weighted sum of the entropy of the discrete and
continuous parts of F plus the binary entropy of
[Link](NIU) Information Theory April 19, 2019 <16>
Examples of Theorem 1
(Discrete): Let X Unif (n ), 8n 2 N d (X ) = 0 and
c (X ) = log(n )
H
(Continuous): Let X N (; 2), d (X ) = 1 and
c (X ) = log( ) +
H
1
log(2e)
2
(Mixture): Let X 0:3Unif (n ) + 0:7N (; 2), d (X ) = 0:7
and
c (X ) = 0:3 log(n ) + 0:7[log( ) +
H
1
log(2e)] + h2(0:7)
2
[Link](NIU) Information Theory April 19, 2019 <17>
Rényi Entropy
Alfred Rényi also defined the Spectra of Information of
Order for a discrete random variable X as:
H (X ) = log(ni=1pi (x ))
1
where > 0; 6 1; 1. For
= = 1,
H1 (X ) = lim H (X ) = Hs (X )
!1
This measure is more commonly referred to as Rényi
entropy of order .
Remark
When > 1, H (X ) < 1.
ni=1pi (x ) < ni=1pi (x ) = 1 < 1
Generally, a finiteness assumption is necessary for < 1.
[Link](NIU) Information Theory April 19, 2019 <18>
Information Dimension of Order
Definition 2: For > 0, 6= 1; 1, define
d (X ) = lim inf H (hX im )
m !1 log m
and
d (X ) = lim sup
H ( hX i m ) :
m !1 log m
When d (X ) = d (X ), the common value d (X ) is called
the information dimensions of X of order . Furthermore,
c (X ) = lim (H
H m !1
(hX im ) d (x ) log m )
is defined as the entropy of X of order and dimension
d (X ).
[Link](NIU) Information Theory April 19, 2019 <19>
Data Compression
Let the source fXi : i 2 Ng be a stochastic process on
(X N; F N), where X represents the source alphabet and F
is a -algebra over X .
Let (Y ; G ) be a measurable space, where Y represents the
code alphabet and G a Borel -algebra over Y
Lossless data compression is the process of finding efficient
representations for source realizations x n 2 X n by y k 2 Y k
[Link](NIU) Information Theory April 19, 2019 <20>
Data Compression
Definition 3: An (n,k)-code for fXi : i 2 Ng over the code
space (Y ; G ) is a pair of mappings:
Encoder: fn : X !Y
n k that is measurable relative toF n
and k G
Decoder: gn : Y !X
n n that is measurable relative to G k
and n F
The block error probability is Pfgn (fn (X n )) 6= X n g.
Definition 4:(Lossless Data Compression) Let fXi : i 2 Ng
be a stochastic process on (X N ; F N ). Define the achievable
compression rate r () to be the infimimum of r > 0 such
that there exists a sequence of (n ; brn c)-codes over the code
space (Y ; G ), such that
Pfgn (fn (X n )) 6= X n g
for all large n.
[Link](NIU) Information Theory April 19, 2019 <21>
Data Compression
When encoding analog sources with analog symbols, we let
( X F RB )=( R)
YG = RB B[ ; ]
; ;
( ; ) ( ; R) or ([0; 1]; 01) if the encoder is required to
be bounded.
For linear encoders, we use the code alphabet Y = R. In
this case the only requirement of the decoder is that it is
Borel measurable. All other code alphabets Y are assumed
to be on [0,1].
[Link](NIU) Information Theory April 19, 2019 <22>
Linear Data Compression
Theorem 2:(Linear Encoding: General Achievability):
Suppose that the source is memoryless, the when
r () lim d (X )
"1
for all 0 < < 1:
Theorem 3:(Linear Encoding: Discrete-Continuous
Mixture): Suppose that the source is memoryless with a
discrete-continuous distribution. Then
r () = d (X )
for all 0 < < 1:
[Link](NIU) Information Theory April 19, 2019 <23>
Continuous Data Compression
When we drop the linearity requirement of the encoder, we
allow ourselves more general rules.
Theorem 4:(Continuous Encoder and Decoder): For
general sources
r () = 0
for all 0 < < 1:
Imposing addition continuity restraints on either the
encoder or decoder has little impact on the fundamental
limits because a continuous encoder or decoder can be
obtained at the cost of a small increase in , which can be
chosen to decrease with n.
[Link](NIU) Information Theory April 19, 2019 <24>
Data Compression
If we have countably infinite X and Y , zero rate [r () = 0]
is achievable with zero block error probability. This is
because the cardinality of Rn is the same for any n.
This holds even when we require either the encoder or
decoder to be Borel measurable.
Kuratowski’s Theorem: Every uncountable standard Borel
B
space is isomorphic to ([0; 1]; [0;1] ) if there exists a
measurable bijection whose inverse is also measurable.
This implies that a single real number has the capability of
encoding a real vector or sequence with a coding scheme
that is both universal and deterministic.
[Link](NIU) Information Theory April 19, 2019 <25>
Concluding Remarks
By studying the fundamental limits of lossless compression,
we learn the achievable limits more graceful lossless
encoding.
Why are we interested in data compression?
[Link](NIU) Information Theory April 19, 2019 <26>
Concluding Remarks
A lot of what we do as statisticians involves compression in
some way:
Linear regression
Variable selection
Principal Component Analysis
Statistical learning algorithms
etc.
[Link](NIU) Information Theory April 19, 2019 <27>
Questions?
View publication stats
[Link](NIU) Information Theory April 19, 2019 <28>