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.^[1]

Simply speaking, it is a measure of the 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 $Z$ is

$\H_0(Z)=\sum_{z \in supp(P_Z)}P_Z(z)\log_2\frac{1}{P_Z(z)}$

where $P_Z(z)$ is the probability measure of $Z$ when $Z=z$, and the $supp(P_Z)$ denotes a set $\{z|z \in\mathcal{Z},P_Z(z)>0\}$.

Let $X$ be an arbitrary real-valued random variable. Given a positive integer $m$, we create a new discrete random variable

$\langle X\rangle_m=\frac{\lfloor mX\rfloor}{m}$

where the $\lfloor \cdot \rfloor$ is the floor operator which converts a real number to the greatest integer less than it. Then

$\underline{d}(X)=\liminf_{m \rightarrow \infty}\frac{\H_0(\langle X \rangle_m)}{\log_2m}$

and

$\bar{d}(X)=\limsup_{m \rightarrow \infty}\frac{\H_0(\langle X \rangle_m)}{\log_2m}$

are called lower and upper information dimensions of $X$ respectively. When $\underline{d}(X)=\bar{d}(X)$, we call this value information dimension of $X$,

$d(X)=\lim_{m \rightarrow \infty}\frac{\H_0(\langle X \rangle_m)}{\log_2m}$

Some important properties of information dimension $d(X)$:

• If the mild condition $\H(\lfloor X\rfloor)<\infty$ is fulfilled, we have $0\leq\underline{d}(X)\leq\bar{d}(X)\leq1$.
• For an $n$-dimensional random vector $\vec{X}$, the first property can be generalized to $0\leq\underline{d}(\vec{X})\leq \bar{d}(\vec{X})\leq n$.
• It is sufficient to calculate the upper and lower information dimensions when restricting to the exponential subsequence $m=2^l$.
• $\underline{d}(X)$ and $\bar{d}(X)$ are kept unchanged if rounding or ceiling functions are used in quantization.

$d$-Dimensional Entropy

If the information dimension $d$ exists, one can define the $d$-dimensional entropy of this distribution by

$\H_{d(X)}(X)=\lim_{n \rightarrow + \infty}(\H_0(\langle X \rangle_m)-d(X)\log_2n)$

provided the limit exists. If $d=0$, the zero-dimensional entropy equals the standard Shannon entropy $\H_0(X)$. For integer dimension $d=n\ge 1$, the $n$-dimensional entropy is the $n$-fold integral defining the respective differential entropy.

Discrete-Continuous Mixture Distributions

According to Lebesgue decomposition theorem,^[2] a probability distribution can be uniquely represented by the mixture

$v=pP_{Xd}+qP_{Xc}+rP_{Xs}$

where $p+q+r=1$ and $p,q,r\geq0$; $P_{Xd}$ is a purely atomic probability measure (discrete part), $P_{Xc}$ is the absolutely continuous probability measure, and $P_{Xs}$ is a probability measure singular with respect to Lebesgue measure but with no atoms (singular part).

Let $X$ be a random variable such that $\H(\lfloor X \rfloor) < \infty$. Assume the distribution of $X$ can be represented as

$v=(1-\rho)P_{Xd}+\rho P_{Xc}$

where $P_{Xd}$ is a discrete measure and $P_{Xc}$ is the absolutely continuous probability measure with $0\leq\rho\leq1$. Then

$d(X)=\rho$

Moreover, given $\H_0(P_{Xd})$ and differential entropy $h(P_{Xc})$, the $d$-Dimensional Entropy is simply given by

$\H_\rho(X)=(1-\rho)\H_0(P_{Xd})+\rho h(P_{Xc})+\H_0(\rho)$

where $\H_0(\rho)$ is the Shannon entropy of a discrete random variable $Z$ with $P_Z(1)=\rho$ and $P_Z(0)=1-\rho$ and given by

$\H_0(\rho)=\rho\log_2\frac{1}{\rho}+(1-\rho)\log_2\frac{1}{1-\rho}$

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

$f(x)= \begin{cases} x,& \text{if } x\geq 0\\ 0,&x<0 \end{cases}$

Then, at the output of the rectifier, the signal has a rectified Gaussian distribution. It is characterized by an atomic mass of weight 0.5 and has a Gaussian PDF for all $x>0$.

With this mixture distribution, we apply the formula above and get the information dimension $d$ of the distribution and calculate the $d$-dimensional entropy.

$d(X)=\rho=0.5$

The normalized right part of the zero-mean Gaussian distribution has entropy $h(P_{Xc})=\frac{1}{2}\log_2(2\pi e\sigma^2)-1$, hence

$\begin{align} \H_{0.5}(X)&=(1-0.5)(1\log_21)+0.5h(P_{Xc})+\H_0(0.5)\\ &=0+\frac{1}{2}(\frac{1}{2}\log_2(2\pi e\sigma^2)-1)+1\\ &=\frac{1}{4}\log_2(2\pi e\sigma^2)+\frac{1}{2}\,\text{ bit(s)} \end{align}$

Connection to Differential Entropy

It is shown ^[3] that information dimension and differential entropy are tightly connected.

Let $X$ be a positive random variable with density $f(x)$.

Suppose we divide the range of $X$ into bins of length $\Delta$. By the mean value theorem, there exists a value $x_i$ within each bin such that

$f(x_i)\Delta=\int_{i\Delta}^{(i+1)\Delta}f(x)\;\mathrm{d}x$

Consider the discretized random variable $X^\Delta=x_i$ if $i\Delta\leq X< (i+1)\Delta$.

The probability of each support point $X^\Delta=x_i$ is

$P_{X^\Delta}(x_i)=\int_{i\Delta}^{(i+1)\Delta}f(x)\;\mathrm{d}x=f(x_i)\Delta$

The entropy of this variable is

$\begin{align} \H_0(X^\Delta)&=-\sum_{x_i \in supp(P_{X^\Delta})}P_{X^\Delta}\log_2P_{X^\Delta}\\ &=-\sum_{x_i \in supp(P_{X^\Delta})}f(x_i)\Delta\log_2(f(x_i)\Delta)\\ &=\sum_{x_i \in supp(P_{X^\Delta})} \Delta f(x_i)\log_2f(x_i)-\sum_{x_i \in supp(P_{X^\Delta})} f(x_i)\Delta \log_2\Delta\\ &=\sum_{x_i \in supp(P_{X^\Delta})} \Delta f(x_i)\log_2f(x_i)-\log_2\Delta\\ \end{align}$

If we set $\Delta=1/m$ and $x_i=i/m$ 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

$\H_0(X^{1/m})=\H_0(\langle X\rangle_m).$

This yields

$\H_0(\langle X\rangle_m)=-\sum \frac{1}{m} f(x_i)\log_2f(x_i)+\log_2m$

and when $m$ is sufficient large,

$-\sum \Delta f(x_i)\log_2f(x_i) \approx \int f(x)\log_2 \frac{1}{f(x)}\mathrm{d}x$

which is the differential entropy $h(x)$ of the continuous random variable. In particular, if $f(x)$ is Riemann integrable, then

$h(X)=\lim_{m\rightarrow \infty}\H_0(\langle X\rangle_m)-\log_2(m).$

Comparing this with the $d$-dimensional entropy shows that the differential entropy is exactly the one-dimensional entropy

$h(X)=\H_1(X).$

In fact, this can be generalized to higher dimensions. Rényi shows that, if $\vec{X}$ is a random vector in a $n$-dimensional Euclidean space $\real^n$ with an absolutely continuous distribution with a probability density function $f_{\vec{X}}(\vec{x})$ and finite entropy of the integer part ($H_0(\langle \vec{X} \rangle_m)<\infty$), we have $d(\vec{X})=n$

and

$\H_n(\vec{X})=\int\cdots\int f_{\vec{X}}(\vec{x})\log_2\frac{1}{f_{\vec{X}}(\vec{x})}\mathrm{d}\vec{x},$

if the integral exist.

Lossless Data Compression

The information dimension of a distribution gives a theoretical upper bound on the compression rate, if we want 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.

The main objective of the lossless data compression is to find efficient representations for source realizations $x^n\in \mathcal{X}^n$ by $y^n\in\mathcal{Y}^n$. A $(n,k)-$code for $\{X_i:i\in\mathcal{N}\}$ is a pair of mappings:

• encoder: $f_n:\mathcal{X}^n\rightarrow \mathcal{Y}^k$ which converts information from a source into symbols for communication or storage;
• decoder: $g_n:\mathcal{Y}^k\rightarrow\mathcal{X}^n$ is the reverse process, converting code symbols back into a form that the recipient understands.

The block error probability is $\mathcal{P}\{g_n(f_n(X^n))\neq X^n\}$.

Define $r(\epsilon)$ to be the infimum of $r\geq0$ such that there exists a sequence of $(n,\lfloor rn\rfloor)-$codes such that $\mathcal{P}\{g_n(f_n(X^n))\neq X^n\}\leq\epsilon$ for all sufficiently large $n$.

So $r(\epsilon)$ 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.^[4]

Consider a continuous encoder function $f(x):\real^n\rightarrow \real^{\lfloor Rn\rfloor}$ with its continuous decoder function $g(x):\real^{\lfloor Rn\rfloor}\rightarrow \real^n$. If we impose no regularity on $f(x)$ and $g(x)$, due to the rich structure of $\real$, we have the minimum $\epsilon$-achievable rate $R_0(\epsilon)=0$ for all $0<\epsilon\leq1$. It means that we can built a encoder/decoder pair with infinity compression rate.

In order to get some nontrivial and meaningful conclusions, let $R^*(\epsilon )$ the minimum $\epsilon-$achievable rate for linear encoder and Borel decoder. If random variable $X$ has a distribution which is a mixture of discrete and continuous part. Then $R^*(\epsilon)=d(X)$ for all $0<\epsilon\leq1$ Suppose we restrict the decoder to be a Lipschitz continuous function and $\bar{d}(X)<\infty$ holds, then the minimum $\epsilon-$achievable rate $R(\epsilon)\geq \bar{d}(X)$ for all $0<\epsilon\leq1$.

Notes

1. See Rényi 1959.
2. See Çınlar 2011.
3. See Cover & Thomas 2012.
4. See Wu & Verdu 2010.

References

• Çınlar, Erhan (2011). Probability and Stochastics. Graduate Texts in Mathematics 261. Springer. doi:10.1007/978-0-387-87859-1.

• Cover, Thomas M.; Thomas, Joy A. (2012). Elements of Information Theory (2nd ed.). Wiley. ISBN 9781118585771.

• Rényi, A. (March 1959). "On the dimension and entropy of probability distributions". Acta Mathematica Academiae Scientiarum Hungarica 10 (1-2): 193–215. doi:10.1007/BF02063299. ISSN 0001-5954.

• Wu, Yihong; Verdu, S. (August 2010). "Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression". IEEE Transactions on Information Theory 56 (8): 3721–3748. doi:10.1109/TIT.2010.2050803. ISSN 0018-9448.