The Fourier Transform help bring the content of the music file from the time domain to the frequency domain which is easier to process, contrast and compare.

the Fourier Transform is based on the discovery that it is possible to take any periodic function of time f(t) and resolve it into an equivalent infinite summation of sine waves and cosine waves with frequencies that start at 0 and increase in integer multiples of a base frequency f0 = 1/T, where T is the period of f(t). The resulting infinite series is called the Fourier Series:

The job of a Fourier Transform is to figure out all the a_n and b_n values to produce a Fourier Series, given the base frequency and the function f(t).

returns 6 lists of frequency content broken down into small chunks for a given class of song.

With that in mind, to we are going to transform all the audio file that we need to work on using the FFT, Fast Fourier Transformation to obtain our raw data. After that we can apply the LDA method to form a training set that we can use to classify other audio file later on. Linear discriminant analysis (LDA) and the related Fisher's linear discriminant are methods used in statistics, pattern recognition and machine learning to find a linear combination of features which characterize or separate two or more classes of objects or events. The resulting combination may be used as a linear classifier, or, more commonly, for dimensionality reduction before later classification.

As we can see in these chart below which show the frequency of the sound from the audio files as time goes. There is quite some different between the distribution of sound frequency among genres. It is mainly because each genre use a certain kind of musc intrument and each instrument has its own frequency range. That give us a chance to run a classification

From wikipedia.org:

Consider a set of observations $\vec x$ (also called features, attributes, variables or measurements) for each sample of an object or event with known class y. This set of samples is called the training set. The classification problem is then to find a good predictor for the class y of any sample of the same distribution (not necessarily from the training set) given only an observation $\vec x$ .

LDA approaches the problem by assuming that the conditional probability density functions $p(\vec x|y=0)$ and $p(\vec x|y=1)$ are both normally distributed with mean and covariance parameters $\left(\vec \mu_0, \Sigma_{y=0}\right)$ and $\left(\vec \mu_1, \Sigma_{y=1}\right)$ , respectively. Under this assumption, the Bayes optimal solution is to predict points as being from the second class if the ratio of the log-likelihoods is below some threshold T, so that;

$(\vec x- \vec \mu_0)^T \Sigma_{y=0}^{-1} ( \vec x- \vec \mu_0)\ +\ \mathrm{ln}|\Sigma_{y=0}|\ -\ (\vec x- \vec \mu_1)^T \Sigma_{y=1}^{-1} ( \vec x- \vec \mu_1)\ -\ \mathrm{ln}|\Sigma_{y=1}| \ < \ T$

Without any further assumptions, the resulting classifier is referred to as QDA (quadratic discriminant analysis). LDA also makes the simplifying homoscedastic assumption (i.e. that the class covariances are identical, so Σ_{y = 0} = Σ_{y = 1} = Σ) and that the covariances have full rank. In this case, several terms cancel and the above decision criterion becomes a threshold on the dot product

$\vec w \cdot \vec x < c$

for some threshold constant c, where

$\vec w = \Sigma^{-1} (\vec \mu_1 - \vec \mu_0)$

This means that the criterion of an input $\vec x$ being in a class y is purely a function of this linear combination of the known observations.

It is often useful to see this conclusion in geometrical terms: the criterion of an input $\vec x$ being in a class y is purely a function of projection of multidimensional-space point $\vec x$ onto direction $\vec w$ . In other words, the observation belongs to y if corresponding $\vec x$ is located on a certain side of a hyperplane perpendicular to $\vec w$ . The location of the plane is defined by the threshold c.

The objective of LDA is to find out the optimal transformation matrix so the ratio of between class scatter matrix and within class scatter matrix reaches to its maximum. However, as processing a high quality audio file could take a lot of time, using a large sample size is not ideal. Using a small sample size raise the problem that the within class scatter mattrix would not tend to be a singular matrix and so the accuracy of the algorithm goes down. To overcome this problem, people has been using LDA in combianation with SVD, Singular Value Decomposition.

Formally, the singular value decomposition of an m×n real or complex matrix M is a factorization of the form

$M = U\Sigma V^*, \,$

where U is an m×m real or complex unitary matrix, Σ is an m×n diagonal matrix with nonnegative real numbers on the diagonal, and V* (the conjugate transpose of V) is an n×n real or complex unitary matrix. The diagonal entries Σ_i,i of Σ are known as the singular values of M. The m columns of U and the n columns ofV are called the left singular vectors and right singular vectors of M, respectively.

Singular value decomposition and eigendecomposition are closely related. Namely:

The left singular vectors of M are eigenvectors of MM ^* .
The right singular vectors of M are eigenvectors of M ^* M.
The non-zero singular values of Σ are the square roots of the non-zero eigenvalues of M ^* M or MM ^* .

Applications which employ the SVD include computing the pseudoinverse, least squares fitting of data, matrix approximation, and determining the rank, range and null space of a matrix.

The key idea here is to diagonalized the covariance matrix so that all the redundancies would be removed, and the largest variances of particular measurements are ordered. In other words the system has been written in terms of its principle components, which is mainly the idea of PCA, Principal Component Analisys.

The original idea was that a signal can be divided up into 6 separate signals, each consisting of the frequency content of the original signal from a certain range. This has the general effect of separating “notes” from different instrument groups and allowing them to be analyzed separately. We can chose to follow the method as an example, broking our signal into the bands 0-200Hz, 200-400Hz, 400-800Hz, 800-1600Hz, 1600-3200Hz, and finally above 3200Hz. This gave us a total of 6 bands to work with. We can do seperate classification on different band and combine the result for a final conclution, however this has not been successfully implemented.

Performs the PCA and LDA and produces the matrix U for projection and the threshold value for comparison.

- I haven't been able to optimizing the algorithm to the satisfying level. Some attemp coorporating R has failed mostly because I have difficulty making R talk to Sage effectively on procedure and data. The based version written on numpy worked extremely slow with unsure result returned.

- The numpy library even though interact well with Sage, doesn't support heavy proccessing of matrix very well. Their SVD function can fail sometimes even though in theory it should not. I have tried using the matlab/octave library instead but I had difficulty integrating them into the project.

- The algorithm can be further optimized by rewritten many of its component using other libraries to abuse their strength.

- Instead of processing a file as a whole, we can divided it into a lot of smaller randomly picked chunks for faster processing time for the same result and accuracy, and we can also revisit the idea of dividing the data into different frequency bands to target difference properties of different music genre more accurately.

“Audio Topics: The Frequencies of Music” PBS International 633 granite Court http://www.psbspeakers.com/audioTopics.php?fpId=8&page_num=1&start=0

Cheng, Kileen. Nazer, Bobak. Uppuluri, Jyoti. Verret, Ryan. “Beat This A Synchronization Project.” http://www.owlnet.rice.edu/~elec301/Projects01/beat_sync/beatalgo.html

Jimaa, Shihab. Krishnan, Sridhar. Umapathy, Karthikeyan. “Multigroup Classification of Audio Signals Using Time-Frequency Parameters.” http://ieeexplore.ieee.org/iel5/6046/30529/01407903.pdf?tp=&arnumber=1407903&isnumber=30529

Neeta Nain, Prashant Gour, Nitish Agarwal, Rakes P Talawar, Subhash Chandra "Face recognization using LDA, PCA and SVD". citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.148.9268