Convolution and the Discrete Trigonometric Transforms
This is mostly distilled from Stephen Martucci’s paper (pdf).
\[\def\wsws{\small \text{WSWS}} \def\wawa{\small \text{WAWA}} \def\wswa{\small \text{WSWA}} \def\waws{\small \text{WAWS}} \def\hshs{\small \text{HSHS}} \def\haha{\small \text{HAHA}} \def\hsha{\small \text{HSHA}} \def\hahs{\small \text{HAHS}} \def\F{\mathcal{F}} \def\C{\mathcal{C}} \def\S{\mathcal{S}} \def\E{\mathcal{E}} \def\P{\mathcal{P}}\]The Discrete Fourier Transform and its inverse are linear operators that map periodic signals to periodic signals
\[(\F x)[k] = \sum_{t = 0}^{m - 1} x[t] e^{-i 2 \pi k t / m} = (\F x)[k + m]\] \[(\F^{-1} x)[k] = \sum_{t = 0}^{m - 1} x[t] e^{i 2 \pi k t / m} = (\F^{-1} x)[k + m] \enspace .\]Any signal with period \(m\) can be defined in terms of a finite vector of length \(m\) using the periodic extension operator \(\P\) defined \((\P u)[t] = u[t \bmod m]\). Whereas \(\F\) is the infinite transform, which maps periodic signals to periodic signals, let \(F\) denote the finite transform (matrix), which maps vectors to vectors. These are related through the periodic extension operator
\[\F \P = \P F \enspace .\]since \(\F \P u = \P F u\) for all \(u\).
The DCT-1
Similarly to the DFT, the Discrete Trigonometric Transforms are linear operators that map real and symmetric periodic signals to real and symmetric periodic signals. If \(x\) is a periodic signal \(x[t] = x[t + m]\) that is real and symmetric \(x[-t] = x[t]\) and has even period \(m = 2 n\), then its Fourier transform
\[\begin{align} (\F x)[k] & = \sum_{t = 0}^{2 n - 1} x[t] e^{-i 2 \pi k t / 2 n} \\ & = x[0] + \sum_{t = 1}^{n - 1} x[t] e^{-i \pi k t / n} + x[n] (-1)^{k} + \sum_{t = 1}^{n - 1} x[2 n - t] e^{-i \pi k (2 n - t) / n} \\ & = x[0] + \sum_{t = 1}^{n - 1} x[t] \left( e^{-i \pi k t / n} + e^{i \pi k t / n} \right) + x[n] (-1)^{k} \\ & = x[0] + \sum_{t = 1}^{n - 1} 2 x[t] \cos(\pi k t / n) + (-1)^{k} x[n] \enspace . \end{align}\]is also real and symmetric periodic \((\F x)[-t] = (\F x)[t]\). This is, in fact, the definition of the DCT-1. Whereas the DFT is defined for complex periodic signals, the DCT-1 is only defined for real and symmetric periodic signals.
Let \(E_{\wsws}\) be a \(2 n \times (n+1)\) matrix that maps an arbitrary vector to one period of a symmetric periodic signal
\[E_{\wsws} = \begin{bmatrix} 1 \\ & 1 \\ & & \cdot \\ & & & 1 \\ & & & & 1 \\ & & & 1 \\ & & \cdot \\ & 1 \end{bmatrix}\]such that
\[(E_{\wsws} u)[t] = \begin{cases} u[t] & \text{if } 0 \le t < n + 1 \\ u[2 n - t] & \text{if } n + 1 \le t < 2 n \end{cases}\]and let \(\E_{\wsws} = \P E_{\wsws}\) be the linear operator that maps an arbitrary vector to a symmetric periodic signal. The reason for the “WSWS” subscript will become evident later on. Any symmetric periodic signal \(x\) can be defined in terms of a finite vector \(x = \E_{\wsws} u\). Since the DCT-1 is equal to the DFT for symmetric periodic signals, the two transforms are related
\[\F \E_{\wsws} = \C_{1} \E_{\wsws} \enspace .\]Finite Transform
If \(x\) is real and symmetric periodic, then its transform \(\C_{1} x\) is also real and symmetric periodic. Therefore there exist vectors \(u\) and \(\hat{u}\) such that \(x = \E_{\wsws} u\) and \(\C_{1} x = \E_{\wsws} \hat{u}\). The finite DCT-1 transform is defined as the \((n+1) \times (n+1)\) matrix \(C_{1}\) that relates the unique elements of these two signals \(\hat{u} = C_{1} u\). The infinite and finite DCT-1 operators are therefore related
\[\C_{1} \E_{\wsws} = \E_{\wsws} C_{1} \enspace .\]The finite DCT-1 is related to the finite DFT
\[F E_{\wsws} = E_{\wsws} C_{1}\]since \(\F \E_{\wsws} = \F \P E_{\wsws} = \P F E_{\wsws}\) and \(\C_{1} \E_{\wsws} = \E_{\wsws} C_{1} = \P E_{\wsws} C_{1}\).
To obtain an explicit expression for \(C_{1}\) in terms of \(F\), let \(E_{\wsws}^{-1}\) denote a matrix that is the left inverse of \(E_{\wsws}\) such that
\[E_{\wsws}^{-1} E_{\wsws} = I \enspace .\]This is an \((n+1) \times 2 n\) matrix that extracts the unique elements from one period of a symmetric periodic signal. Using the left inverse yields
\[C_{1} = E_{\wsws}^{-1} F E_{\wsws} \enspace .\]Convolution
The relationship with the Fourier transform can be used to obtain a convolution theorem for symmetric signals. The convolution of two symmetric periodic signals is a symmetric periodic signal
\[\E_{\wsws} u * \E_{\wsws} v = \E_{\wsws} w\]whose unique elements are related by the finite transform
\[C_{1} w = C_{1} u \odot C_{1} v \enspace .\]Proof
Let \(z = \E_{\wsws} u * \E_{\wsws} v\). Its Fourier transform is
\[\F z = (\F \E_{\wsws} u) \odot (\F \E_{\wsws} v) = (\E_{\wsws} C_{1} u) \odot (\E_{\wsws} C_{1} v)\]using the Fourier convolution theorem and the properties of the DCT-1. Since the product of two symmetric signals is symmetric, this can be expressed
\[\F z = \E_{\wsws} (C_{1} u \odot C_{1} v) \enspace .\]Since the Fourier transform of \(z\) is real and symmetric, \(z\) itself must be real and symmetric \(z = E_{\wsws} w\), and the elements of \(w\) must satisfy
\[\begin{align} \E_{\wsws} u * \E_{\wsws} v & = \E_{\wsws} w \\ \E_{\wsws} (C_{1} u \odot C_{1} v) & = \E_{\wsws} C_{1} w \enspace . \end{align}\]q.e.d.
Orthogonality
The finite DFT is orthogonal \(F^{H} F = F F^{H} = m I\), which gives Parseval’s theorem \(\|F x\|^{2} = m \|x\|^{2}\). The finite DCT-1 is not orthogonal, although it does satisfy
\[\| E_{\wsws} C u \|^{2} = \| F E_{\wsws} u \|^{2} = m \| E_{\wsws} u \|^{2}\]due to the orthogonality of the Fourier transform. Substitute \(D = E_{\wsws}^{T} E_{\wsws}\) with \(D = (D^{\frac{1}{2}})^{2}\) diagonal and invertible to give
\[\| D^{\frac{1}{2}} C D^{-\frac{1}{2}} u \|^{2} = \| E_{\wsws} C D^{-\frac{1}{2}} u \|^{2} = m \| E_{\wsws} D^{-\frac{1}{2}} u \|^{2} = m \| u \|^{2} \enspace .\]Therefore, while \(C_{1}\) is not orthogonal, \(\tilde{C}_{1} = D^{\frac{1}{2}} C_{1} D^{-\frac{1}{2}}\) is. This is known as the orthogonal form of the DCT-1. The diagonal matrix \(D\) counts the number of times each unique element appears in the symmetric periodic extension
\[D = E^{T}_{\wsws} E_{\wsws} = \begin{bmatrix} 1 \\ & 2 \\ && 2 \\ &&& \cdot \\ &&&& 2 \\ &&&&& 1 \end{bmatrix} \enspace .\]More general symmetry
This section will introduce the DST-1, DCT-2 and DST-2 and generalise the above results.
Even more general symmetry
There are a total of sixteen DTTs, of which only four have been discussed so far. To compute the convolution of signals that are anti-periodic, i.e. that have one symmetric and one anti-symmetric reflection, it is necessary to introduce the DCT- and DST-3 and -4. To handle signals that have mixed whole and half symmetry, and therefore odd period, it is necessary to introduce the -odd variant of every transform. For the gritty details, refer to Stephen Martucci’s paper and PhD thesis.