Why Are JPEG DCT Basis Functions Orthogonal?

This article explores the mathematical foundations behind the orthogonality of the basis functions in the Discrete Cosine Transform (DCT-II) used in JPEG compression. Orthogonality ensures that image data can be decomposed into independent frequency components without redundant information, allowing for efficient energy compaction and lossless invertibility before quantization. Below is an examination of the exact trigonometric identities, discrete boundary conditions, and algebraic properties that make these basis functions orthogonal.

The DCT-II Basis Functions

In standard JPEG image compression, an \(8 \times 8\) block is transformed using the one-dimensional DCT-II applied across rows and columns. The one-dimensional discrete cosine transform basis sequence of length \(N\) is defined as:

\[f_k[n] = \cos \left( \frac{\pi}{N} \left(n + \frac{1}{2}\right) k \right)\]

where \(n \in \{0, 1, \dots, N-1\}\) is the spatial sample index, and \(k \in \{0, 1, \dots, N-1\}\) is the frequency index.

Orthogonality requires the discrete inner product of any two distinct basis vectors \(f_k\) and \(f_m\) (\(k \neq m\)) over the domain of \(n\) to equal zero:

\[\langle f_k, f_m \rangle = \sum_{n=0}^{N-1} \cos \left( \frac{\pi}{N} \left(n + \frac{1}{2}\right) k \right) \cos \left( \frac{\pi}{N} \left(n + \frac{1}{2}\right) m \right) = 0 \quad \text{for } k \neq m\]

1. Product-to-Sum Trigonometric Identities

The first mathematical property enabling orthogonality is the cosine product-to-sum identity:

\[\cos(A)\cos(B) = \frac{1}{2} \left[ \cos(A - B) + \cos(A + B) \right]\]

Applying this identity to the inner product transforms the product of two basis functions into the sum of two separate cosine series:

\[\langle f_k, f_m \rangle = \frac{1}{2} \sum_{n=0}^{N-1} \cos \left( \frac{\pi (k - m)}{N} \left(n + \frac{1}{2}\right) \right) + \frac{1}{2} \sum_{n=0}^{N-1} \cos \left( \frac{\pi (k + m)}{N} \left(n + \frac{1}{2}\right) \right)\]

Evaluating orthogonality reduces to showing that sums of the form \(S(p) = \sum_{n=0}^{N-1} \cos \left( \frac{\pi p}{N} \left(n + \frac{1}{2}\right) \right)\) evaluate to zero when \(p = k \pm m \neq 0\).

2. Geometric Cancellation over Half-Sample Shifts

The half-sample shift \((n + 1/2)\) creates symmetric phase distribution across the discrete interval. By representing the cosine term as the real part of a complex exponential using Euler's formula:

\[S(p) = \text{Re} \left\{ \sum_{n=0}^{N-1} e^{i \frac{\pi p}{N} (n + 1/2)} \right\} = \text{Re} \left\{ e^{i \frac{\pi p}{2N}} \sum_{n=0}^{N-1} \left(e^{i \frac{\pi p}{N}}\right)^n \right\}\]

Applying the finite geometric series formula \(\sum_{n=0}^{N-1} r^n = \frac{1 - r^N}{1 - r}\):

\[\sum_{n=0}^{N-1} \left(e^{i \frac{\pi p}{N}}\right)^n = \frac{1 - e^{i \pi p}}{1 - e^{i \frac{\pi p}{N}}}\]

Multiplying by the leading phase term \(e^{i \frac{\pi p}{2N}}\) and simplifying yields:

\[S(p) = \frac{\sin(\pi p)}{2 \sin\left(\frac{\pi p}{2N}\right)}\]

For any non-zero integer \(p\), the numerator \(\sin(\pi p)\) is identically zero. Because \(k, m \in \{0, 1, \dots, N-1\}\) and \(k \neq m\), the arguments \(p = k - m\) and \(p = k + m\) satisfy \(0 < |p| < 2N\), ensuring the denominator \(\sin\left(\frac{\pi p}{2N}\right)\) never vanishes. Consequently, both summation terms vanish:

\[S(k - m) = 0 \quad \text{and} \quad S(k + m) = 0\]

This establishes that \(\langle f_k, f_m \rangle = 0\) whenever \(k \neq m\).

3. Spectral Theorem and Eigenvalues of Tridiagonal Matrices

From a linear algebra perspective, DCT-II basis functions are the discrete eigenvectors of a second-order difference operator with Neumann boundary conditions. The operator can be represented as a symmetric tridiagonal matrix \(T\):

\[T = \begin{pmatrix} 1 & -1 & 0 & \dots & 0 \\ -1 & 2 & -1 & \dots & 0 \\ 0 & -1 & 2 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & -1 \\ 0 & 0 & \dots & -1 & 1 \end{pmatrix}\]

Because \(T\) is a real symmetric matrix (\(T = T^T\)), the Spectral Theorem guarantees that:

• All of its eigenvalues are real.
• Eigenvectors corresponding to distinct eigenvalues are mutually orthogonal.

The sequences \(f_k[n] = \cos\left(\frac{\pi k (2n+1)}{2N}\right)\) satisfy the discrete boundary-value eigenvalue equation:

\[2 f_k[n] - f_k[n-1] - f_k[n+1] = \lambda_k f_k[n]\]

with the specific symmetric boundary extensions \(f_k[-1] = f_k[0]\) and \(f_k[N] = f_k[N-1]\). The resulting eigenvalues are:

\[\lambda_k = 2 - 2\cos\left(\frac{\pi k}{N}\right) = 4 \sin^2\left(\frac{\pi k}{2N}\right)\]

Since each \(k \in \{0, 1, \dots, N-1\}\) yields a distinct eigenvalue \(\lambda_k\), the corresponding eigenvectors are inherently orthogonal.

4. Connection to Chebyshev Polynomials

The basis functions can also be viewed as Chebyshev polynomials of the first kind, defined as \(T_k(x) = \cos(k \arccos(x))\). Evaluating \(T_k(x)\) at the discrete nodes:

\[x_n = \cos\left(\frac{\pi (n + 1/2)}{N}\right)\]

directly yields the DCT-II basis \(T_k(x_n) = \cos\left(\frac{\pi k (n + 1/2)}{N}\right)\). These nodes \(x_n\) are the roots of the degree-\(N\) Chebyshev polynomial \(T_N(x)\). By the properties of Gauss-Chebyshev quadrature, Chebyshev polynomials satisfy discrete orthogonality when sampled at the zeros of higher-degree Chebyshev polynomials:

\[\sum_{n=0}^{N-1} T_k(x_n) T_m(x_n) = 0 \quad \text{for } k \neq m < N\]

This polynomial relationship reinforces the geometric and algebraic derivation of orthogonality in the discrete domain.