The Discrete Cosine Transform and Chebyshev Expansions

Cosine series and the discrete Cosine transform are close relatives of Fourier series and the discrete Fourier transform. A Fourier series in triginometric polynomials is an expansion

$$f(\theta) = \sum_{k=0}^\infty c_k \cos k \theta + \sum_{k=1}^\infty s_k \sin k \theta,$$

where

$$ \begin{align*} c_0 &= {1 \over 2 \pi} \int_0^{2 \pi} f(\theta) \cos k \theta d \theta \cr c_k &= {1 \over \pi} \int_0^{2 \pi} f(\theta) \cos k \theta d \theta \cr s_k &= {1 \over \pi} \int_0^{2 \pi} f(\theta) \sin k \theta d \theta \cr \end{align*} $$

A Cosine series is an expansion like

$$f(\theta) = \sum_{k=0}^\infty c_k \cos k \theta$$

That is, it is a Fourier series with only cosine terms, no sine terms.

Cosine series for even functions

Even functions satisfy $f(\theta) = f(-\theta)$. Cosine expansions capture evenness, because each Cosine term is even: $\cos k \theta = \cos(-k\theta)$.

Exercise 1(a) Why is it true that, if $f$ is even, we have

$$s_k = 0?$$

Verify this statement for $k=1,2,3$ using quadgk for the even function $f(\theta) = e^{\cos \theta}$.

In [ ]:

Exercise 1(b) When $f$ is even, the integrals can be reduced to have a period. Explain why its true that

\begin{align*} c_0 &= {1 \over \pi} \int_0^{\pi} f(\theta) \cos k \theta d \theta \cr c_k &= {2\over \pi} \int_0^{\pi} f(\theta) \cos k \theta d \theta \cr \end{align*}

Verify this statement using quadgk for the even function $f(\theta) = e^{\cos \theta}$ for $k=0,1,2,3$.

In [ ]:

Exercise 1(c) Use quadgk to approximate $c_k$ for $f(\theta) = e^{\cos \theta}$. Verify

$$f(\theta) \approx \sum_{k=0}^9 c_k \cos k \theta$$
In [ ]:

Non-periodic functions and Chebyshev expansion

Consider a non-periodic function $f(x)$ on $[-1,1]$. Then $f(\cos \theta)$ is a periodic, even function on $[0,2\pi]$! Cosine expansion of $f(\cos \theta)$ combined with the change of variables $\theta = \hbox{acos}\, x$ leads to the Chebyshev expansion of a non-periodic function. Remarkably, this expansion is a polynomial expansion.

Exercise 2(a) Consider $f(x) = e^x$. Show that

$$f(x) \approx \sum_{k=0}^9 c_k T_k(x)$$

where $c_k$ are the cosine coefficients of $f(\cos \theta)$ and $T_k(x) \triangleq \cos k \, {\rm acos}\, x$.

In [ ]:

Exercise 2(b) Advanced Use the fact that

$$\int_0^\pi \cos k \theta \sin \theta d \theta = \begin{cases} 2/(1-k^2) & \hbox{$k$ even} \cr 0 & \hbox{otherwise} \end{cases}$$

to approximate

$$\int_{-1}^1 f(x) dx \approx \int_{-1}^1 \sum_{k=0}^{n-1} c_k T_k(x) dx$$

This is known as Clenshaw–Curtis quadrature.

In [ ]:

Exercise 2(c) Advanced Show that $T_k(x)$ are polynomials.

Exercise 2(d) Advanced Show that

$$\int_{-1}^1 {T_k(x) T_j(y) \over \sqrt{1-x^2}} dx = 0 $$

if $k \neq j$.

The DCT

The Trapezium rule over $[0,\pi]$ also leads to a discrete cosine transform. We can use the trap routine from lectures:

In [ ]:
function trap(f,a,b,n)
    h=(b-a)/n
    x=linspace(a,b,n+1)

    v=f(x)
    h/2*v[1]+sum(v[2:end-1]*h)+h/2*v[end]
end

Exercise 3(a) Use trap to complete the function mydct that returns approximations $[c_0^n,\ldots,c_{n-1}^n]$ to $c_k$. (Hint: make sure you use n-1 when calling trap.) Show experimentally that it is exact for $f(\theta) = \cos \omega \theta$ when $\omega > n$.

In [ ]:
function mydct(f::Function,n)
    c=zeros(n)
    # TODO: populate c
    c
end

The following command is a fast DCT-I.

In [ ]:
dctI(v) = FFTW.r2r(v, FFTW.REDFT00)

Exercise 3(b) Advanced Figure out how to calculate $c_k^n$ using dctI and $f$ evaluated at θ=linspace(0,π,n). (Hint: try it with $\cos k \theta$ for different choices of $k$.)

In [ ]: