Predictive Matching Pursuit and Its Application to Real-time Seizure Detection
Matching pursuit is an effective method of signal representation widely used in neural signal analysis. However, its traditional algorithm is so slow and resource-consuming that it can be hardly applied in real-time, especially when the analyzed data has a lot of channels such as in electroencephalography (EEG). The main objective of this research is to develop an improved matching pursuit algorithm called predictive matching pursuit and verify its speed improvement in neural signal applications.
Matching Pursuit
Matching pursuit (MP) is an algorithm that decomposes any signal into a linear expansion of waveforms that are selected from a redundant dictionary of functions. From this large dictionary of possible functions, a sub-family of time-frequency atoms is chosen in such a way as to best match the local signal structures. The family of time-frequency atoms is created by scaling, translating, and modulating a window function g(t):
where s > 0 is scale, ξ is frequency modulation, and u is translation.
The minimum of time-bandwidth product is obtained when g(t) is Gaussian. In this case, gγ are called Gabor functions (Gauss modulated by sinus).
The animation above shows the time-frequency distribution of a signal that consists of two slightly different Gabor atoms whose internal frequencies progressively increase.
Applictions of Matching Pursuit to Neural Signals
The waveforms selected by matching pursuit are adaptively matched to the local signal patterns. This kind of analysis is especially suitable for characterizing transients appearing randomly in the signal, such as sleep spindles, K-complexes, epileptic spikes and HFOs.
For example, the time-frequency map of an epileptic signal can be drawn with a better resolution than the Fourier Transform and the wavelet transform. In addition, the parameters extracted by matching pursuit can be also used to do seizure detection and foci localization.
The figure above is the two-dimensional representation of energy density of matching pursuit atoms in an intracranial recording with a seizure (Franaszczuk et al, 1998). Horizontal axis-time [s], vertical (on the time-frequency plot) [Hz].
Traditional Matching Pursuit
The traditional matching pursuit algorithms are restricted within every time bin, and never utilize information collected from the previous time bins. The animations above illustrate the decomposition process of three successive time bins within an ECoG signal using the traditional matching pursuit. In each frame, the figure below shows the reconstructed signal, and the figure above shows the atoms already selected by matching pursuit. (Every black pixel represents an atom in the dictionary. When it is selected, it turns white.) According to these animations, the traditional matching pursuit searches among the whole dictionary no matter how many time bins it has processed.
In fact, large datasets have to be divided into a lot of time bins before applying matching pursuit. As the MP algorithm decomposes the time bins one by one orderly, we get more and more information about the signal structure, which can be used to make the decomposition of the latter time bins faster and less resource-consuming.
Predictive Matching Pursuit
Since the feature number of a certain signal is limited, a majority of Gabors have a very low probability of appearing in the decomposition. Therefore, as we get more and more information about the signal structure during matching pursuit, we can reduce the size of the Gabor dictionary according to some criterion.
The animations above illustrate the decomposition process of the same three time bins using the predictive matching pursuit. Even though search among the whole dictionary is still required for the first time bin, the dictionary sizes for the second and third time bins are greatly reduced based on the prediction of their signal structure. As a result, the decomposition of the same signal can be done with a much higher speed and nearly no precision loss.
Performance Evaluation
The figure compares the performance of the predictive matching pursuit with that of the traditional matching pursuit. For the two exemplary time bins, the error curves of the two methods share the same downtrend before reaching a reconstruction accuracy of 99.99%. This means using only 20% of the original dictionary, the predictive matching pursuit can do the decomposition as well as the traditional one.