Proof of Theorems

We briefly prove the two major theorems used in this work

The DCT Least Squares Approximation Theorem

Given a set of $N$ samples of a signal $X = \{x_0, ..., x_N\}$, let $Y = \{y_0,...,y_n\}$ be the DCT coefficients of $X$. Then for any $1 \leq m \leq N$, the approximation

$$ p_m(t) = \frac{1}{\sqrt{n}}y_0 + \sqrt{\frac{2}{n}}\sum_{k=1}^m y_k \cos\left(\frac{k(2t+1)\pi}{2n}\right) $$

of $X$ minimizes the least squared error

$$ e_m = \sum_{i=0}^n (p_m(i) - x_i)^2 $

Proof. First consider that since Equation 1 represents the Discrete Cosine Transform, which is a Linear map, we can write rewrite it as

$$ D_m^Ty = x $$

where D_m is formed from the first $m$ rows of the DCT matrix, $y$ is a row vector of the DCT coefficients, and $x$ is a row vector of the original samples.

To solve for the least squares solution, we use the normal equations, that is we solve

$$ D_mD_m^Ty = D_mx $$

and since the DCT is an orthogonal transform, the rows of $D_m$ are orthogonal, so $D_mD_m^T = I$. Therefore

$$ y = D_mx $$

Since there is no contradiction, the least squares solution must use the first $m$ DCT coefficients.

The DCT Mean-Variance Theorem

Given a set of samples of a signal $X$ such that $\mathrm{E}[X] = 0$, let $Y$ be the DCT coefficients of $X$. Then

$$ \mathrm{Var}[X] = \mathrm{E}[Y^2] $$

Proof. Start by considering $\mathrm{Var}[X]$. We can rewrite this as

$$ \mathrm{Var}[X] = \mathrm{E}[X^2] - \mathrm{E}[X]^2 $$

Since we are given $\mathrm{E}[X] = 0$, this simplifies to

$$ \mathrm{Var}[X] = \mathrm{E}[X^2] $$

Next we express the DCT as a linear map such that $X = DY$ and rewrite the previous equation as

$$ \mathrm{Var}[X] = \mathrm{E}[(DY)^2] $$

Distributing the squaring operation gives

$$ \mathrm{E}[(DY)^2] = \mathrm{E}[D^TDY^2] $$

Since $D$ is orthogonal, this simplifies to

$$ \mathrm{E}[D^TDY^2] = \mathrm{E}[D^{-1}DY^2] = \mathrm{E}[Y^2] $$

Copyright © 2019 Max Ehrlich