Wikipedia / Information dimension
Wikipedia / Information dimension
In information theory, information dimension is an information measure for random vectors in Euclidean space, based on the normalized entropy of finely quantized versions of the random vectors. This concept was first introduced by Alfréd Rényi in 1959.
Simply speaking, it is a measure of the fractal dimension of a probability distribution. It characterizes the growth rate of the Shannon entropy given by successively finer discretizations of the space.
In 2010, Wu and Verdú gave an operational characterization of Rényi information dimension as the fundamental limit of almost lossless data compression for analog sources under various regularity constraints of the encoder/decoder.
Definition and Properties
The entropy of a discrete random variable is
is the probability measure.
be an arbitrary real-valued random variable. Given a positive integer, we create a new discrete random variable
is the floor operator which converts a real number to the greatest integer less than it. Then
and
,
:
.
.
It is sufficient to calculate the upper and lower information dimensions when restricting to the exponential.
are kept unchanged if rounding or ceiling functions are used in quantization.
d-Dimensional Entropy
-dimensional entropy of this distribution by
, the zero-dimensional entropy equals the standard Shannon entropy-fold integral defining the respective differential entropy.
An equivalent definition of Information Dimension
In 1994, Kawabata and Dembo in proposed a new way of measuring information based on rate distortion value of a random variable. The measure is defined as
is the rate-distortion function that is defined as
.
They further, proved that such definition is equivalent to the definition of information dimension. Formally,
Dimensional-Rate Bias
Using the above definition of Rényi information dimension, a similar measure to d-dimensional entropy is defined in that is named dimensional-rate bias is defined in a way to capture the finite term of rate-distortion function. Formally,
The dimensional-rate bias is equal to d-dimensional rate for continuous, discrete, and discrete-continuous mixed distribution. Furthermore, it is calculable for a set of singular random variables, while d-dimensional entropy does not necessarily exist there.
Finally, dimensional-rate bias generalizes the Shannon's entropy and differential entropy using the following formula:
Discrete-Continuous Mixture Distributions
According to Lebesgue decomposition theorem, a probability distribution can be uniquely represented by the mixture is a probability measure singular with respect to Lebesgue measure but with no atoms (singular part).
be a random variable can be represented as is a discrete measure. Then-Dimensional Entropy is simply given by and given by
Example
Consider a signal which has a Gaussian probability distribution.
We pass the signal through a half-wave rectifier which converts all negative value to 0, and maintains all other values. The half-wave rectifier can be characterized by the function Then, at the output of the rectifier, the signal has a rectified Gaussian distribution.
-dimensional entropy., hence
Connection to Differential Entropy
It is shown that information dimension and differential entropy are tightly connected.
. . By the mean value theorem within each bin such that
. is
is
then we are doing exactly the same quantization as the definition of information dimension. Since relabeling the events of a discrete random variable does not change its entropy, we have
This yields
is sufficiently large,
is Riemann integrable, then
-dimensional entropy shows that the differential entropy is exactly the one-dimensional entropy
and
if the integral exists.
Lossless data compression
The information dimension of a distribution gives a theoretical upper bound on the compression rate, if one wants to compress a variable coming from this distribution. In the context of lossless data compression, we try to compress real number with less real number which both have infinite precision.
is a pair of mappings:
which converts information from a source into symbols for communication or storage;
is the reverse process, converting code symbols back into a form that the recipient understands.
.
to be the infimum.
basically gives the ratio between the code length and the source length, it shows how good a specific encoder decoder pair is. The fundamental limits in lossless source coding are as follows.
. It means that one can build an encoder-decoder pair with infinity compression rate.
Suppose we restrict the decoder to be a Lipschitz continuous function.
The fundamental role of information dimension in lossless data compression further extends beyond the i.i.d. data. It is shown that for specified processes (e.g., moving-average processes) the ratio of lossless compression is also equal to the information dimension rate. This result allows for further compression that was not possible by considering only marginal distribution of the process.