Matching Pursuit Algorithm

This file contains the details regarding the installation of matching pursuit algorithm. Please read all sections carefully.

0. Updates
This code can now be compiled on both Linux and Windows, thanks to Dr. Bart Krekelberg. The executable gabord in /source that is generated when the code is compiled in Linux also works on Mac OSX, at least on 10.9 (Mavericks).


1. Authors and Copyrights
This version of MP employs the software routines written in C by Dr. Stephane Mallat and Dr. Zhifeng Zhang, for their interactive program called mpp (matching pursuit program), which was made available with their original paper in 1993 (no longer available online). Dr. Mallat has kindly allowed us to put their code online for academic purposes. 

The source code for signal decomposition was modified by Dr. Piotr Franaszczuk and Dr. Christophe Jouny and integrated with a larger software system for analysis of continuous intracranial EEG recordings in the Epilepsy Research Laboratory at Johns Hopkins Medical Institutions (http://erl.neuro.jhmi.edu). Some Matlab routines were later added by Dr. Supratim Ray so that mp could be run directly from Matlab. In this package matlab routines are provided for running mp and reconstructing the signal/energy from decomposed atoms. Dr. Bart Krekelberg has modified the code so that it can also be compiled on Windows.

A nonexclusive license to use this software and its documentation for scholarly and research purposes only is hereby granted. There is no fee to use this software for these purposes. In using the software and documentation for scholarly and research purposes you may copy or modify them but (a) you must include the copyright notice and the original authors' names on each copy or modification you make of the software and of the supporting documentation; and (b) you may not use, rewrite, or adapt the software or the documentation (or any part of either) as the basis for any commercial software or hardware product, without in each instance obtaining the prior written consent by sending an email with subject "license" to the email address: pfranasz@jhmi.edu.


2. Limitations
The Epilepsy Research Laboratory software system is designed for multi-channel clinical signals. The Matlab routines are simple patch-ups to make the Matlab data compatible with this design. As a result, a lot of otherwise useful options, such as changing the reference montage to average reference/bipolar reference etc. are disabled. Further, the algorithm is rigorously tested only for a limited number of sampling frequencies, lengths etc. If you find a bug while using certain parameters, please contact us. In most cases the program itself will generate an error message if some parameters are incompatible. Some other limitations are:

¥ The algorithm assumes a zero mean signal. So the mean is subtracted from each signal prior to mp analysis. This affects the DC value of the spectrum.
¥ This limited version works for signal epochs of lengths that are powers of two (N=2^k), with a maximum length of 4096.
¥ For clinical settings, the sampling frequency is usually set to 200 Hz or 1000 Hz. We have tried some other frequencies and it seems to work fine, but it has not been rigorously tested for all sampling frequencies.
¥ Border (edge) issues: The MP algorithm assumes that the analyzed epoch of length N is one period of an infinite signal of period N. This means that the atoms are wrapped around Ð an atom with a center position close to one edge will be continued from the other edge.  Note that this is an assumption commonly used in signal analysisÐ DFT coefficients, for example, are by definition the Discrete Fourier Series coefficients of a periodic signal generated by making infinite copies of the original signal, shifted by multiples of N. The effect of this assumption is usually most prominent at the edges of the signal  Ð a burst of energy at one edge of the signal could cause some energy to appear at the other edge Ð but might be visible in the whole analysis window. As in the case of all other signal processing methods, special care must be taken to minimize the boundary effects. Typical strategies include: multiplying the signal by a window function with zero values at edges prior to decomposition, making sure that both the edges are in the baseline period with little activity, and taking signals much longer than necessary and analyzing only the middle portion. In some experiments where the paradigm includes repetition of the same condition in regular intervals, the best strategy might be to use this interval (trial) as the window of analysis. In general, a choice of analysis interval with large signal differences at edges should be avoided.


3. Installations, Main programs and data format
An C-compiled executable is required for mp analysis. This executable, gabord, does the gabor decomposition. To generate the executable, use the set of commands shown below. These should work for most linux/unix workstations with the GNU gcc compiler installed.

cd gabord-0.1
./configure
make
The executable is generated in the folder src.
ls src/gabord 

importData and runGabor
Two matlab programs are used to run MP directly from matlab. 
1. importData.m is used to convert the matlab data in a format that can be used by gabord. 
2. runGabor runs the gabord program Ð which does the mp decomposition.

The starting input data is a three-dimensional matlab variable of size LxMxN, where L=length of the signal, M = number of trials and N = number of channels. As explained above, the data format is for multi-channel analysis. However, there is no interaction between different trials or channels (eg, no average referencing etc), so the individual signals can be considered independent. For example, if you have neurophysiological data of length 1024 under two conditions (condition 1 and 2, M trials each), it is all right to generate a 3-D array of size 1024xMx2, and consider the two conditions as separate ÔchannelsÕ. 

For each 3-D variable, two variables ÔfolderNameÕ and ÔtagÕ are used Ð all the results are stored in the folder folderName/tag (for example, folderName could be your home directory and ÔtagÕ could be ÔNeuron1/Õ.

Please ignore the additional variables Ð the functionalities will be expanded in the next release. 

For compiling in Windows, please see the instructions in the /windows folder. Note that the executables gabord and gabord.exe already present in /source folder seem to work fine for a variety of platforms, so it may not be necessary to compile these.


4. Visualization
After gabor decomposition, some matlab files are provided for the retrieval and visualization of gabor atoms. These files were originally located in the folder viewData, but now all the files are in a single folder called matlab. Use getGaborData.m to retrieve the information about gabor atoms. The signal can be reconstructed from the atoms with the program reconstructSignalFromAtomsMPP. The time-frequency wigner-ville spectrum can be generated using the program reconstructEnergyFromAtomsMPP. Mathematical details of the energy reconstruction are explained in wignerVille.pdf.


5. Example
An example program called exampleMP.m is provided to perform a basic MP analysis and show the results. 
 

6. Other implementations
Matching pursuit with Gabor dictionaries have been implemented in some other packages, such as MPTK (Matching pursuit Toolkit; http://mptk.irisa.fr/) and LastWave (http://www.cmap.polytechnique.fr/~bacry/LastWave/). However, at present the field of application is primarily in speech processing, and their applicability in Neurophysiological data analysis is being tested.

 
7. Contact information
For reporting bugs or for technical assistance, please contact Dr. Supratim Ray at sray@cns.iisc.ernet.in.