Matching Pursuit Algorithm based on L1 norm

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.