Question icon
Your Current Search
Choose below to refine your search
Research Topic
Download abstract book

Download the NI2012 abstract book here. The page numbers in the index are clickable for easy browsing.


Matching Pursuit Algorithm based on L1 norm


Tomasz Spustek (University of Warsaw, Faculty of Physics, ul. Hoża 69, 00-681 Warszawa, Poland), Rafał Kuś (University of Warsaw, Faculty of Physics, ul. Hoża 69, 00-681 Warszawa, Poland), Urszula Malinowska (University of Warsaw, Faculty of Physics, ul. Hoża 69, 00-681 Warszawa, Poland), Piotr Durka (University of Warsaw, Faculty of Physics, ul. Hoża 69, 00-681 Warszawa, Poland)

Matching pursuit algorithm (MP), introduced by Mallat and Zhang [1], is a greedy iterative algorithm used for adaptive decomposition of a given signal. The idea of Matching Pursuit is to provide a suboptimal solution to the problem of finding a best linear expansion of a signal in a redundant set of functions. In each of the consecutive steps, a waveform is matched to the signal. Choosing best matching function is most commonly done, by means of largest dot product (called L2 norm) with the residual signal, left after subtracting results of previous iterations [2].

In most cases MP provides a detailed description of structures present in EEG (electroencephalogram) time series. Signal patterns are described not only in terms of their frequency and amplitude, but also their exact time positions and durations are determined. However it is expected, that such procedure applied to a periodic signal would result in a Fourier expansion instead of preferred explicit parameterization of separate structures, as in Figure 1A.

Due to the described problem new Matching Pursuit procedure has been implemented. The idea was to change function selection criterion in such way, to use L1 norm instead of L2. Pilot application of this algorithm to the EEG signal from EEG-fMRI (functional magnetic resonance
imaging) coregistration allowed for a new approach dealing with EEG artifacts. Instead of filtering the signal before further processing, which may lead to a potential bias of further analyses, relevant structures of interest (in this case sleep spindles) have been detected directly in the raw signal (Figure 1B). Identification of the sleep spindle was made according to [3]:
frequency 10-15 Hz, width 0.5-2.5 Hz, amplitude above 12 μV.

[1] S. Mallat and Z. Zhang. Matching pursuit with time-frequency dictionaries. IEE Transactions on Signal Processing, 41:3397-3415, 1993.

[2] P. J. Durka. Matching Pursuit and Unification in EEG Analysis, Artech House 2007, ISBN 978-1-58053-304-1

[3] U. Malinowska, P. J. Durka, K. J. Blinowska, W. Szelenberger, A. Wakarow. Micro- and macrostructure of sleep EEG. IEEE Engineering in Medicine and Biology Magazine, 2005.
Matching Pursuit Algorithm based on L1 norm
In Fig. 1C, a raw coregistration 4 sec long signal containing a sleep spindle is presented. Energy density estimation obtained by MP: map A- based on L2 norm, map B - based on L1 norm. Identified sleep spindle was marked with a red circle.
Preferred presentation format: Poster
Topic: Computational neuroscience