Discrete Cosine Transform

The discussion in this article is based on [Str99].

There are four types of DCT transforms DCT-1, DCT-2, DCT-3 and DCT-4.

Consider the second difference equation:

\[y(n) = - x (n -1) + 2 x(n) - x(n + 1)\]

For finite signals \(x \in \RR^N\), the equation can be implemented by a linear transformation:

\[y = A x\]

where \(A\) is a circulant matrix:

\[\begin{split}A = \begin{bmatrix} 2 & -1 & & & & -1\\ -1 & 2 & -1 & & & \\ & -1 & 2 & -1 & & \\ & & & \ddots & & \\ & & & -1 & 2 & -1\\ -1 & & & & -1 & 2 \end{bmatrix}\end{split}\]

The unspecified values are 0. We can write the individual linear equations as:

\[\begin{split}\begin{aligned} y_1 &= - x_{N} + 2 x_1 - x_2 \\ y_j &= - x_{j-1} + 2 x_j - x_{j +1} \quad \forall 1 < j < N \\ y_N &= - x_{N_1} + 2 x_N - x_1 \end{aligned}\end{split}\]

The first and last equations are boundary conditions while the middle one represents the ordinary second difference equation.

The rows 1 and N of \(A\) are the boundary rows while all other rows are interior rows.

The interior rows correspond to the computation \(- x_{j-1} + 2 x_j - x_{j +1}\) which is the discretization of the second order derivative \(-x''\). The negative sign on the derivative makes the matrix \(A\) positive semi definite. This ensures that no eigen values of \(A\) are negative.

In the first and last rows, we need the values of \(x_0\) and \(x_{N + 1}\). In the periodic extension, we assume that \(x_0 = x_N\) and \(x_{N + 1} = x_1\). This gives the \(-1\) entries in the corners of \(A\) as shown above.

With \(\omega = \exp(2\pi i / N)\), it turns out that

\[v_k = (1, \omega^k, \omega^{2k}, \dots, \omega^{(N-1)k})\]

are eigen vectors for \(A\) for \(0 \leq k \leq N -1\). The corresponding eigen values are \((2 - 2 \cos(2\pi k / N)\).

The eigen vectors are nothing but the basis vectors for DFT basis. Note that the eigen values satisfy a relationship \(\lambda_k = \lambda_{N -k}\). So the linear combinations of the eigen vectors \(v_k\) and \(v_{N -k}\) are also eigen vectors.

It turns out that the real and imaginary parts of the vector \(v_k\) are also eigen vectors of \(A\). They can be easily constructed as linear combinations of \(v_k\) and \(v_{N -k}\).

We define:

\[c_k = \Re(v_k) = \left ( 1, \cos \frac{2\pi k}{ N}, \cos \frac{4\pi k}{ N}, \dots, \cos \frac{2 (N -1)\pi k}{ N} \right ).\]

\[s_k = \Im(v_k) = \left ( 0, \sin \frac{2\pi k}{ N}, \sin \frac{4\pi k}{ N}, \dots, \sin \frac{2 (N -1)\pi k}{ N} \right )\]

The exception to this rule is \(\lambda_0\) for which \(c_0 = (1, 1, \dots, 1)\) and \(s_0 = (0, 0, \dots, 0)\) where \(s_0\) is not an eigen vector while \(c_0\) is.

For even \(N\), there is another exception at \(\lambda_{N/2}\) with \(c_{N/2} = (1, -1, \dots, 1, -1)\) and \(s_0 = (0, 0, \dots, 0)\).

These two eigen vectors have length \(\sqrt{N\) while other eigen vectors \(c_k\) and \(s_k\) have length \(\sqrt{N/ 2}\).

TBD