The purpose of this homework is to understand matching pursuit and sparse coding. You may use any programming language you'd like but you may not use a matching pursuit package such as MPTK.

**You may work in teams of two but it is not required.** If you work alone, please speak with me directly about simplifying the homework assignment.

- Implement the matching pursuit algorithm for fitting Gammatone atoms to audio sequences (Smith & Lewicki). Use 64 Gammatone atoms as your dictionary. Instructions will be given in class for computing these.
- Run the algorithm on an audio file of your choosing to 20dB SNR. Generate a reconstructed version of your audio. Generate a reconstructed version of the residual. What does the residual sound like?
- Generate plots for your audio similar (but not necessarily identical) to Figure 3 and Figure 4 of Manzagol et.al. Be sure to include a spectrogram plot!
- Extra credit: If your basic matching pursuit algorithm works, try to speed it up. We will discuss several ideas in class for doing this, such as limiting the codebook as computation progresses, working causally (left-to-right) through the signal, making clever use of the FFT to avoid excessive correlation (convolution) computations. Compare an encoding at 20dB SNR to that of the original model in terms of computational efficiency as well as quality.

Some kernels are found here.

A function for reading in, cropping and plotting kernels: load_and_plot_kernels.py

- Generate sparse codes
**using your algorithm or another one such as the MPTK**for the audio in the Tzanetakis genre dataset. (To be provided in class). As this will be computationally intensive, you may contact me for obtaining time on our computer cluster for running your job. - Once you have encoded the audio, use the resulting sparse codes as input to a classification algorithm of your choice for classifying the audio by genre. Use the first 30 songs for each genre as training and the next 70 songs for each genre as testing. We will discuss strategies and techniques for achieving this in class.
- Analyze your results.
- Extra credit: Try at least two strategies for using the sparse code as input to a classifier. The simplest is probably a histogram of spike counts by frequency bin (as used in Manzagol et.al.)

The datasets can be found here. Use genre.zip for the full set and genre100.zip for a test set. (Username is "ift6080"; password to be given in class).

- You must submit your source code and a report containing plots and descriptions. A web page is also fine.
- Your report can be in French or English.
- Submit your homework as a single compressed .zip or .tgz file containing all code and the report via email to douglas.eck@umontreal.ca.
- The subject of the email should be "ift6080 hw1"
- If you work in teams of two, each person must be familiar with both parts of the homework. Please indicate who did what work in your report