**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Matching pursuit

Summary

Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary D. The basic idea is to approximately represent a signal f from Hilbert space H as a weighted sum of finitely many functions g_{\gamma_n} (called atoms) taken from D. An approximation with N atoms has the form
: f(t) \approx \hat f_N(t) := \sum_{n=1}^{N} a_n g_{\gamma_n}(t)
where g_{\gamma_n} is the \gamma_nth column of the matrix D and a_n is the scalar weighting factor (amplitude) for the atom g_{\gamma_n}. Normally, not every atom in D will be used in this sum. Instead, matching pursuit chooses the atoms one at a time in order to maximally (greedily) reduce the approximation error. This is achieved by finding the atom that has

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (13)

Related publications (77)

Loading

Loading

Loading

Related concepts (3)

Compressed sensing

Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a signal, by finding solu

Sparse approximation

Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in application

Basis pursuit

Basis pursuit is the mathematical optimization problem of the form
: \min_x |x|_1 \quad \text{subject to} \quad y = Ax,
where x is a N-dimensional solution vector (signal), y is a M-d

Related units (3)

Related courses (2)

EE-512: Applied biomedical signal processing

The goal of this course is twofold: (1) to introduce physiological basis, signal acquisition solutions (sensors) and state-of-the-art signal processing techniques, and (2) to propose concrete examples of applications for vital sign monitoring and diagnosis purposes.

MATH-412: Statistical machine learning

A course on statistical machine learning for supervised and unsupervised learning

Related lectures (2)

2001

In the last decade we observed an increasing interaction between data compression and sparse signals approximations. Sparse approximations are desirable because they compact the energy of the signals in few elements and correspond to a structural simplification of the approximated signals. In the first part of this dissertation we consider the low bit rate image coding problem. The state of the art in image compression is to use two-dimensional (2-D) wavelets. The main advantage of wavelet bases lie in their multiscale nature and in their ability to sparsely represent functions that are piecewise smooth. Their main problem on the other hand, is that 2-D wavelets are not able to deal with the natural geometry of images, i.e. they cannot sparsely represent objects that are smooth away from regular submanifolds. We propose an approach based on building a sparse approximation of the edge part of images in a redundant geometrically inspired library of functions, followed by suitable coding techniques. The edge-oriented dictionary is built by anisotropically scaling, orienting and bending a generating function. The new bending transform generates elementary waveforms that efficiently approximate the edges; with few waveforms we are able to approximate long edges. The sparse approximations over the redundant dictionary are computed using a sub-optimal greedy strategy, as indeed finding the best m-terms non-linear approximations in general dictionaries is a NP-hard problem. Recently there has been an intense activity in the field of sparse approximations with redundant dictionaries, largely motivated by the practical performances of algorithms such as Matching Pursuit and Basis Pursuit. However, most of the theoretical results obtained so far are valid only for the restricted class of incoherent dictionaries. The second part of the dissertation investigates a new class of overcomplete dictionaries, called block incoherent dictionaries, where coherence can be arbitrarily large. We show that a simple greedy algorithm can correctly identify stable subdictionaries (called blocks) and demonstrate how one can use the extra coherence freedom for approximation purposes. With the aim of improving the sparse approximations over redundant dictionaries obtained with greedy algorithms, in the last part we develop a new decomposition algorithm characterized by the computational cost of MP and global optimization properties typical of the re-weighted minimum norm algorithms such as FOCUSS. We introduce the concept of sub-dictionary, a subset of the redundant dictionary which depends on the signal to be approximated, and we propose a sub-dictionary selection algorithm based on greedy techniques. The low computational cost greedy algorithm selects a sub-dictionary that contains the solution of more complex algorithms, which are utilized to obtain the approximation over the sub-dictionary. In the first part we studied image and video sparse approximation, however the concepts we present in the second part of the dissertation are general and can be applied to any kind of structured signal.

, ,

Low bit rate image coding is an important problem regarding applications such as storage on low memory devices or streaming data on the internet. The state of the art in image compression is to use 2-D wavelets. The advantages of wavelet bases lie in their multiscale nature and in their ability to sparsely represent functions that are piecewise smooth. Their main problem on the other hand, is that in 2-D wavelets are not able to deal with the natural geometry of images, i.e they cannot sparsely represent objects that are smooth away from regular submanifolds. In this paper we propose an approach based on building a sparse representation of the edge part of images in a redundant geometrically inspired library of functions, followed by suitable coding techniques. Best N-terms non-linear approximations in general dictionaries is, in most cases, a NP-hard problem and sub-optimal approaches have to be followed. In this work we use a greedy strategy, also known as Matching Pursuit to compute the expansion. The residual, that we suppose to be the smooth and texture part, is then coded using wavelets. A rate distortion optimization procedure choses the number of functions from the redundant dictionary and the wavelet basis.

2006