<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Implementing Fourier Transforms
Abhishek Chakraborty
A look at how to implement Fourier Transforms on a computer.
Discrete Fourier Transforms
Analytically, the Fourier Transform is used for continuous functions. However, when we want to implement things on a computer, discreteness naturally creeps in. 
Here we do the following
Step1:  Generating the signal
First we generate a signal. For discrete fourier transforms,the signal is sampled at a finite number of points after regular intervals, which we attribute to the response time of the measuring apparatus. The number of samples is a power of 2 for reasons that will be clear later when we discuss the Fast Fourier Transform.
Step2:  Now we create the function that will perform the discrete fourier transform.
Step3:  A look into the mathematical treatment of the DFT should convince you that this is the way to go.
Taking the Discrete Fourier Transform
Step4:  Regenerating the signal
Regenerating the signal shouldn't be too difficult as it just involves the inverse of the matrix. We choose only the real part as the signal was initially also purely real.
Step5:  This verifies that the DFT we obtained was correct.
Editing the fourier transform
Let's play around with this now. It's obvious from the above plot that the major contributors are the first and last elements in the fourier transformed coefficients. So let's and see how that changes the signal
Step6:  Regenerating the modified signal
Step7:  Notice that the amplitude of the regenerated signal is a lot less than the original signal. This is attributed to the fact that when you take away the contributions due to certian frequencies, a lesser number of harmonics generate the new signal and this signal has a lower amplitude.
Fast Fourier Transform
Discrete Fourier Transforms are great but they are also horribly slow, with a time complexity of $\mathcal{O}(n^2)$. For matrices that are large (i.e. a high sampling rate), this means it takes practically forever to perform a DFT. However, Given the nature of the matrix used to obtain the DFT, an optimization is possible. Let's use the same signal as before.
Step8:  We intend to use recursion as our friend in this one. So we'll define a function which implements this recursion. Why we define the function this particular way will be clear if you look at the mathematical treatment for the optimization of the FFT.
Step9:  Taking the Fast Fourier Transform
Step10:  Time Comparison
Discrete Fourier Transform
Step11:  Fast Fourier Transform
<ASSISTANT_TASK:>
Python Code:
%pylab inline
import scipy.linalg as la
Explanation: Implementing Fourier Transforms
Abhishek Chakraborty
A look at how to implement Fourier Transforms on a computer.
Discrete Fourier Transforms
Analytically, the Fourier Transform is used for continuous functions. However, when we want to implement things on a computer, discreteness naturally creeps in. 
Here we do the following:
1. Generate a discretely sampled signal.
2. Define a funcion to perform the DFT.
3. Regenerate the signal as verification.
4. Alter the DFT and see the result.
End of explanation
def signal(t):
    return 1-(t-2)**2 if (t<3 and t>1) else 0
num_samples = rows = cols = 2**12
time_list  = linspace(0.0001,4,num_samples)
signal_list = [signal(time) for time in time_list]
plot(time_list,signal_list)
Explanation: Generating the signal
First we generate a signal. For discrete fourier transforms,the signal is sampled at a finite number of points after regular intervals, which we attribute to the response time of the measuring apparatus. The number of samples is a power of 2 for reasons that will be clear later when we discuss the Fast Fourier Transform.
End of explanation
def DFT(x,inverse=False):
    x = asarray(x,dtype=float)
    n = arange(num_samples)
    k = n.reshape((num_samples,1))        
    mat = exp(2j * pi * k *n/num_samples)
    return dot(la.inv(mat),x) if inverse else dot(mat,x)
Explanation: Now we create the function that will perform the discrete fourier transform.
End of explanation
g = DFT(signal_list)
plot(absolute(g))
Explanation: A look into the mathematical treatment of the DFT should convince you that this is the way to go.
Taking the Discrete Fourier Transform
End of explanation
f = DFT(g,inverse=True)
plot(time_list,f.real)
Explanation: Regenerating the signal
Regenerating the signal shouldn't be too difficult as it just involves the inverse of the matrix. We choose only the real part as the signal was initially also purely real.
End of explanation
g[0] = g[-1] =  0
plot(absolute(g))
Explanation: This verifies that the DFT we obtained was correct.
Editing the fourier transform
Let's play around with this now. It's obvious from the above plot that the major contributors are the first and last elements in the fourier transformed coefficients. So let's and see how that changes the signal
End of explanation
f = DFT(g,inverse=True)
plot(time_list,f.real)
Explanation: Regenerating the modified signal
End of explanation
plot(time_list,signal_list)
Explanation: Notice that the amplitude of the regenerated signal is a lot less than the original signal. This is attributed to the fact that when you take away the contributions due to certian frequencies, a lesser number of harmonics generate the new signal and this signal has a lower amplitude.
Fast Fourier Transform
Discrete Fourier Transforms are great but they are also horribly slow, with a time complexity of $\mathcal{O}(n^2)$. For matrices that are large (i.e. a high sampling rate), this means it takes practically forever to perform a DFT. However, Given the nature of the matrix used to obtain the DFT, an optimization is possible. Let's use the same signal as before.
End of explanation
def FFT(x):
    x = asarray(x,dtype=float)
    N = x.shape[0]
    if N == 1:
        return x
    else:
        X_even = FFT(x[0::2])
        X_odd = FFT(x[1::2])
        factor = exp(-2j * pi * arange(N) / N)
        return concatenate([X_even + factor[:N / 2] * X_odd, X_even + factor[N / 2:] * X_odd])
Explanation: We intend to use recursion as our friend in this one. So we'll define a function which implements this recursion. Why we define the function this particular way will be clear if you look at the mathematical treatment for the optimization of the FFT.
End of explanation
h = FFT(signal_list)
plot(absolute(h))
Explanation: Taking the Fast Fourier Transform
End of explanation
%timeit DFT(signal_list) 
Explanation: Time Comparison
Discrete Fourier Transform
End of explanation
%timeit FFT(signal_list)
Explanation: Fast Fourier Transform
End of explanation
<END_TASK>