joint entropy

Suppose we have two information sources; joint entropy is the measure of joint surprise when we are defined over more than one information source.

For a pair of random variables, \(X, Y\), their joint entropy is defined over a new random variable of \(X \cup Y\).

\begin{equation} H(x,y) = \sum_{i \in X}^{} \sum_{j \in Y}^{} P(X=i, Y=j) \log_{2} \qty(\frac{1}{P(X=i, Y=j)}) \end{equation}

If \(X \perp Y\), we can write \(H(x,y) = H(x)+H(y)\) (shown below.) Further, we have for all \(X\) and \(Y\), \(H(x,y) \leq H(x) + H(y)\) because you can never be more surprised than if you got two completely independent pieces of information.

We want a way of generating a Prefix-Free code for any Source Coding problem.

Huffman Coding

See Huffman Coding

Diadic Source

Diadic Source is an information source for which the probability of occurrence for each symbol is a member of \(\frac{1}{2^{n}}\) for integer \(n\).

That is, the probability of each symbol is in powers of \(\frac{1}{2}\).

In THESE sources, Huffman Coding will always result in a code that communicates the information in the same number of bits as the entropy of the source.

Non-IID Sequence Can Have Smaller Entropy

For sequences that are not IID, we may have:

\begin{equation} H(X_1, \dots, X_{n)} \ll \sum_{j=1}^{n} H(X_{j}) \end{equation}

This means that for very dependent sequences:

\begin{equation} \lim_{n \to \infty} \frac{H(X_1, \dots, X_{n})}{n} \ll \sum_{j=1}^{n}H(x_{j}) \end{equation}

so to measure how good our compression is, we should use this.

signal

a signal is, mathematically, just a function.

\begin{equation} f: \mathbb{R}^{n} \to \mathbb{R}^{m} \end{equation}

whereby the input is space (time, coordinates, etc.) and the output is the “signal” (pressure, level of gray, RGB, etc.)

Fourier Series as exactly a shifted sum of sinusoids

Key idea: every periodic function with period \(L\) can be represented as a sum of sinusoids

\begin{equation} f(t) = A_0 + \sum_{i=1}^{\infty} B_{j} \sin \qty(k \omega t + \phi_{j}) \end{equation}

where \(\omega = \frac{2\pi}{T}\). notice! without the \(A_0\) shift, our thing would integrate to \(0\) for every \(L\); hence, to bias the mean, we change \(A_0\).

Now, we ideally really want to get rid of that shift term \(\phi\), applying the sin sum formula:

Fourier Series components form a basis

Recall the definition of a basis, and in particular what an orthonormal basis is. In particular, recall that writing a vector as a linear combination of orthonormal basis is a thing you can do very easily.

Recall

Importantly, the Fourier Series is defined as:

\begin{equation} f(x) = a_0 + \sum_{k=1}^{\infty} \qty( a_{k} \cos(k \omega x) + b_{k} \sin(k \omega x)) \end{equation}

where \(\omega = \frac{2\pi}{L}\), and

\begin{equation} a_0 = \frac{\langle f, 1 \rangle}{ \langle 1,1 \rangle} = \frac{1}{L} \int_{0}^{L} f(x) \dd{x} \end{equation}