M.Sc. on matching pursuit theory

Adaptive time-frequency approximations provide an important signal processing tool, used e.g. for analysis of the brain s electrical activity (EEG). They are usually implemented via the matching pursuit algorithm with redundant sets of Gabor functions (time-frequency dictionaries). We start with derivation of the analytical formula for a scalar product of two vectors representing sampled discrete Gabors. It allows for a significant acceleration of the algorithm, compared to the previously used approach of direct numerical calculations. Simplified version of the above formula allows for a construction of a dictionary with an optimal distribution. For this purpose, we define and calculate a product-based metric in the space of Gabor functions. We construct a dictionary with approximately uniform distribution with respect to this metric. In such dictionary, we estimate the parameter describing the loss of accuracy, which stems from using finite subsets of a potentially infinite dictionaries. All the above results are implemented in an improved version of the software for matching pursuit decomposition of signals. It is faster than the previous versions, yet retains the stochastic character of the dictionary, which results in a bias-free decomposition.

Master thesis, Laboratory of Medical Physics, Warsaw University 2004