Assignment 3: The DFT, function approximation and signal smoothing

Please complete the following assignment in Jupyter, and upload the file on blackboasrd by midnight on 3 June 2016.

You are strongly encouraged to work out the problems on your own. If you use existing solutions, existing code, help online or collaborate with other students, you will still receive full credit provided that you make this clear and cite your sources. If you collaborate with other students, please submit individual solutions and be specific in giving credit for what each student contributed.

In this assignment we will create a type called FourFun to represent functions periodic on [0,2π). This will allow us to do the following:

n=11        # number of points used
f=FourFun(θ->cos(cos(θ-0.1)),n)  # calculate the Fourier coefficients of cos(cos(θ-0.1))
f(0.1)      # evaluate the approximate Fourier series at 0.1
plot(f)     # plots h

We will support addition:

g=FourFun(θ->cos(θ),3)    # another function with a different number of coefficients
h=f+g       # add two Fourier series with different lengths
h(0.5)      # should approximate cos(cos(0.4)) + cos(0.5)

We will use this type to do signal smoothing:

f=FourFun(θ->cos(cos(θ-0.1)) + 0.1randn(),10000)
g=resize(f,-12,12)   # drops all but the coefficients between -12 and 12
f(0.5)   # should be approximately cos(cos(θ-0.1))

FourFun type

The starting point is creating the type FourFun, that will represent the finite Fourier series $$ \sum_{k=\alpha}^\beta f_k e^{i k \theta} $$

It has two fields: negative, containing the negative coefficients in decreasing order, that is, $[ f_{-1}, f_{-2}, \ldots, f_\alpha]$ and nonnegative, containing the non-negative coefficients in increasing order, that is, $[ f_0, f_1, \ldots, f_\beta]$.

In [1]:
type FourFun
    negative::Vector{Complex128}
    nonnegative::Vector{Complex128}
end
Out[1]:
FourFun

Exercise 1(a) Complete the following function FourFun that calculates n Fourier coefficients of f, and returns FourFun. You can assume n is an integer, and if desired you can use the fft. (Hint: the fft assumes the values of the function are at $[\theta_0,\theta_1,\ldots,\theta_{n-1}]$ where $\theta_k = {2 \pi k \over n}$. Using the fft will save some time in the last exercise.)

In [ ]:
points(n) = linspace(0,2π-2π/n,n)


# INPUT: a Function and an Integer
# OUTPUT: a FourFun whose coefficients correspond to the Fourier series that interpolates 
#  f at the points [θ_0,θ_1,…,θ_{n-1},θ_n]

function FourFun(f::Function,n::Integer)
    # TODO: create a FourFun
end

Exercise 1(b) Complete the following override of call to evaluate the finite Fourier series represented by f at the point t:

$$ \sum_{k=\alpha}^\beta f e^{i k t} $$
In [4]:
import Base.call

# INPUT: a FourFun f and a point 0≤t≤2π
# OUTPUT: The finite Fourier series that f encodes evalauted at t

function call(f::FourFun,t)
    # TODO: sum the finite Fourier series encoded by f
end
Out[4]:
call (generic function with 1089 methods)

Exercise 1(c) Override + to sum two finite Fourier series. Make sure that you pad the lengths of the vectors! Test that the example at the beginning works.

In [33]:
import Base.+

# INPUT: Two FourFuns f and g
# OUTPUT: A FourFun whose nonnegative/negative coefficients are the addition 
#   of the nonnegative/negative coefficients of f and g.  Make sure you pad the 
#   vectors to have the same length.


#TODO: Override +
Out[33]:
+ (generic function with 175 methods)

Plotting

Exercise 2(a) Override plot(f::FourFun) to plot both the real and imaginary parts of the finite Fourier series encoded by f. Make sure the number of plot points depends on the number of coefficients so that the function looks smooth regardless of the length. (Hint: it's faster to use ifft, but not mandatory.)

In [51]:
using PyPlot

import PyPlot.plot

function plot(f::FourFun)
    # TODO: plot the finite Fourier series encodded by `f`
end
Out[51]:
plot (generic function with 2 methods)

Exercise 2(b) Plot f, g and f+g where

f=FourFun(θ->cos(cos(θ-0.1)),11)
g=FourFun(θ->cos(θ),3)

Signal smoothing

Exercise 3(a) Write a routine resize(f::FourFun,a,b) that resizes the Fourier coefficients to have -a negative coefficients and b+1 nonnegative coefficients. You can assume -a ≤ length(f.negative) and b +1 ≤ length(f.nonnegative).

In [124]:
# INPUT: a FourFun f, a negative integer a and a positive integer b
# OUTPUT: a FourFun, with the first -a negative coefficients and 
#         the first b+1 nonnegative coefficients of f 

# TODO: write resize(f::FourFun,a,b)

Exercise 3(b) Plot the FourFun approximations of

f=FourFun(θ->cos(cos(θ-0.1)),25)

noisycos(θ::Number) = cos(cos(θ-0.1)) + 0.1randn()
noisycos(θ::AbstractVector) = cos(cos(θ-0.1)) + 0.1randn(length(θ))

fr=FourFun(noisycos,200)
g=resize(fr,-12,12)
In [ ]:

Exercise 3(c) Use a loglog estimate the convergence rate of

fr=FourFun(noisycos,n)
g=resize(fr,-12,12)
g(0.1)-cos(cos(0.))

as a function of n, as $O(n^{-\gamma})$ where $\gamma$ may not be an integer. This shows that a sufficiently large number of samples allows us to de-noise. (Hint: If you used the fft in exercise 1(a) this will go faster.)

In [ ]: