Information dimension

The entropy of a discrete random variable $Z$ is

:$\backslash mathbb\{H\}\_0(Z)=\backslash sum\_\{z\; \backslash in\; supp(P\_Z)\}P\_Z(z)\backslash log\_2\backslash 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 $\backslash \{z|z\; \backslash in\backslash mathcal\{Z\},P\_Z(z)>0\backslash \}$.

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

:$\backslash langle\; X\backslash rangle\_m=\backslash frac\{\backslash lfloor\; mX\backslash rfloor\}\{m\}$

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

:$\backslash underline\{d\}(X)=\backslash liminf\_\{m\; \backslash rightarrow\; \backslash infty\}\backslash frac\{\backslash mathbb\{H\}\_0(\backslash langle\; X\; \backslash rangle\_m)\}\{\backslash log\_2m\}$

and

:$\backslash bar\{d\}(X)=\backslash limsup\_\{m\; \backslash rightarrow\; \backslash infty\}\backslash frac\{\backslash mathbb\{H\}\_0(\backslash langle\; X\; \backslash rangle\_m)\}\{\backslash log\_2m\}$

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

:$d(X)=\backslash lim\_\{m\; \backslash rightarrow\; \backslash infty\}\backslash frac\{\backslash mathbb\{H\}\_0(\backslash langle\; X\; \backslash rangle\_m)\}\{\backslash log\_2m\}$

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

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

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

:$\backslash mathbb\{H\}\_\{d(X)\}(X)=\backslash lim\_\{n\; \backslash rightarrow\; +\; \backslash infty\}(\backslash mathbb\{H\}\_0(\backslash langle\; X\; \backslash rangle\_n)-d(X)\backslash log\_2n)$

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

In 1994, Kawabata and Dembo in {{harvnb|Kawabata|Dembo|1994}} proposed a new way of measuring information based on rate distortion value of a random variable. The measure is defined as

:$d\_R(X)=-2\backslash frac\{R(X,\; D)\}\{\backslash log\; D\},$

where $R(X,\; D)$ is the rate-distortion function that is defined as

:$R(X,\; D)\; =\; \backslash min\_\{\backslash |X-\backslash hat\{X\}\backslash |\_2\backslash leq\; D\}\; I(X,\; \backslash hat\{X\}),$

or equivalently, minimum information that could lead to a $D$-close approximation of $X$.

They further, proved that such definition is equivalent to the definition of information dimension. Formally,

:$d\_R(X)\; =\; d(X).$

Using the above definition of Rényi information dimension, a similar measure to d-dimensional entropy is defined in {{harvnb|Charusaie|Amini|Rini|2022}} . This value $b(X)$ that is named dimensional-rate bias is defined in a way to capture the finite term of rate-distortion function. Formally,

:$R(X,\; D)=-\backslash frac\{d(X)\}\{2\}\backslash log\; \backslash frac\{2\backslash pi\; e\; D\}\{d(X)\}+b(X).$

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, as one could find the mutual information $I(X;\; Y)$ using the following formula:

:$I(X;Y)\; =\; b(X)+b(Y)-b(X,\; Y).$

According to Lebesgue decomposition theorem,See {{harvnb|Çınlar|2011}}. a probability distribution can be uniquely represented by the mixture

$v=pP\_\{Xd\}+qP\_\{Xc\}+rP\_\{Xs\}$

Let $X$ be a random variable such that . Assume the distribution of $X$ can be represented as

$v=(1-\backslash rho)P\_\{Xd\}+\backslash rho\; P\_\{Xc\}$

$d(X)=\backslash rho$

$\backslash mathbb\{H\}\_\backslash rho(X)=(1-\backslash rho)\backslash mathbb\{H\}\_0(P\_\{Xd\})+\backslash rho\; h(P\_\{Xc\})+\backslash mathbb\{H\}\_0(\backslash rho)$

$\backslash mathbb\{H\}\_0(\backslash rho)=\backslash rho\backslash log\_2\backslash frac\{1\}\{\backslash rho\}+(1-\backslash rho)\backslash log\_2\backslash frac\{1\}\{1-\backslash rho\}$

File:A standard Gaussian distribution for illustration an example.png

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}

File:Rectified gaussian distribution.png

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)=\backslash rho=0.5$

$\backslash begin\{align\}$

\mathbb{H}_{0.5}(X)&=(1-0.5)(1\log_21)+0.5h(P_{Xc})+\mathbb{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}

It is shown See {{harvnb|Cover|Thomas|2012}}. that information dimension and differential entropy are tightly connected.

Let $X$ be a random variable with continuous density $f(x)$. File:A simple continuous function which are used to be quantized.png Suppose we divide the range of $X$ into bins of length $\backslash Delta$

. By the mean value theorem, there exists a value $x\_i$ within each bin such that

:$f(x\_i)\backslash Delta=\backslash int\_\{i\backslash Delta\}^\{(i+1)\backslash Delta\}f(x)\backslash ;\backslash mathrm\{d\}x$

Consider the discretized random variable $X^\backslash Delta=x\_i$ if .

File:F(x) which has already been quantized to several dirac function.png

The probability of each support point $X^\backslash Delta=x\_i$ is

:$P\_\{X^\backslash Delta\}(x\_i)=\backslash int\_\{i\backslash Delta\}^\{(i+1)\backslash Delta\}f(x)\backslash ;\backslash mathrm\{d\}x=f(x\_i)\backslash Delta$

Let $S\; =\; \backslash operatorname\{supp\}(P\_\{X^\backslash Delta\})$.

The entropy of $X^\backslash Delta$ is

:$$

\begin{align}

\mathbb{H}_0(X^\Delta)&=-\sum_{x_i \in S} P_{X^\Delta}\log_2P_{X^\Delta}\\

&=-\sum_{x_i \in S} f(x_i)\Delta\log_2(f(x_i)\Delta)\\

&=-\sum_{x_i \in S} \Delta f(x_i)\log_2f(x_i)-\sum_{x_i \in S} f(x_i)\Delta \log_2\Delta\\

&=-\sum_{x_i \in S} \Delta f(x_i)\log_2f(x_i)-\log_2\Delta\\

\end{align}

If we set $\backslash 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

:$\backslash mathbb\{H\}\_0(X^\{1/m\})=\backslash mathbb\{H\}\_0(\backslash langle\; X\backslash rangle\_m).$

This yields

:$\backslash mathbb\{H\}\_0(\backslash langle\; X\backslash rangle\_m)=-\backslash sum\; \backslash frac\{1\}\{m\}\; f(x\_i)\backslash log\_2f(x\_i)+\backslash log\_2m$

and when $m$ is sufficiently large,

:$-\backslash sum\; \backslash Delta\; f(x\_i)\backslash log\_2f(x\_i)\; \backslash approx\; \backslash int\; f(x)\backslash log\_2\; \backslash frac\{1\}\{f(x)\}\backslash 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)=\backslash lim\_\{m\backslash rightarrow\; \backslash infty\}\backslash mathbb\{H\}\_0(\backslash langle\; X\backslash rangle\_m)-\backslash log\_2(m).$

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

:$h(X)=\backslash mathbb\{H\}\_1(X).$

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

$d(\backslash vec\{X\})=n$

and

:$\backslash mathbb\{H\}\_n(\backslash vec\{X\})=\backslash int\backslash cdots\backslash int\; f\_\{\backslash vec\{X\}\}(\backslash vec\{x\})\backslash log\_2\backslash frac\{1\}\{f\_\{\backslash vec\{X\}\}(\backslash vec\{x\})\}\backslash mathrm\{d\}\backslash vec\{x\},$

if the integral exists.

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.

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

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

The block error probability is $\backslash mathcal\{P\}\backslash \{g\_n(f\_n(X^n))\backslash neq\; X^n\backslash \}$.

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

So $r(\backslash 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.See {{harvnb|Wu|Verdu|2010}}.

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

In order to get some nontrivial and meaningful conclusions, let $R^*(\backslash epsilon\; )$ the minimum $\backslash 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^*(\backslash epsilon)=d(X)$ for all Suppose we restrict the decoder to be a Lipschitz continuous function and holds, then the minimum $\backslash epsilon-$achievable rate $R(\backslash epsilon)\backslash geq\; \backslash bar\{d\}(X)$ for all .

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.See {{harvnb|Charusaie|Amini|Rini|2022}} This result allows for further compression that was not possible by considering only marginal distribution of the process.

• Fractal dimension
• Correlation dimension
• Entropy (information theory)

{{reflist}}

• {{Cite book

| first = Erhan

| last = Çınlar

| title = Probability and Stochastics

| publisher = Springer

| series = Graduate Texts in Mathematics

| year = 2011

| volume = 261

| doi = 10.1007/978-0-387-87859-1

| isbn = 978-0-387-87858-4

}}

• {{Cite book|first1=Thomas M.|last1=Cover|first2=Joy A.|last2=Thomas|title=Elements of Information Theory|url=https://books.google.com/books?id=VWq5GG6ycxMC|publisher=Wiley|edition=2nd|pages=247–248|date=2012|isbn=9781118585771}}

• {{Cite journal

| first = A.

| last = Rényi

| title = On the dimension and entropy of probability distributions

| journal = Acta Mathematica Academiae Scientiarum Hungaricae

| date = March 1959

| issn = 0001-5954

| pages = 193–215

| volume = 10

| issue = 1–2

| doi = 10.1007/BF02063299 | doi-access =free

| s2cid = 121006720

}}

• {{Cite journal

| first1 = Yihong

| last1 = Wu

| first2 = S.

| last2 = Verdu

| title = Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression

| journal = IEEE Transactions on Information Theory

| date = August 2010

| issn = 0018-9448

| pages = 3721–3748

| volume = 56

| issue = 8

| doi = 10.1109/TIT.2010.2050803

| s2cid = 206737933

}}

• {{Cite journal

| first1 = M.

| last1 = Charusaie

| first2 = A.

| last2 = Amini

| first3 = S.

| last3 = Rini

| title = Compressibility Measures for Affinely Singular Random Vectors

| journal = IEEE Transactions on Information Theory

| date = May 2022

| volume = 68

| issue = 9

| pages = 6245–6275

| doi = 10.1109/TIT.2022.3174623 | doi-access =free

| arxiv = 2001.03884

}}

• {{Cite journal

| first1 = T.

| last1 = Kawabata

| first2 = A.

| last2 = Dembo

| title = The Rate-Distortion Dimension of Sets and Measures

| journal = IEEE Transactions on Information Theory

| date = September 1994

| volume = 40

| issue = 5

| pages = 1564–1572

| doi = 10.1109/18.333868 | doi-access =free

}}

Category:Information theory