Matching pursuit

Algorithms and methods for sparse approximation in structured dictionaries

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.

EPFL2007

Image compression using an edge adapted redundant dictionary and wavelets

Lorenzo Granai, Lorenzo Peotta, Pierre Vandergheynst

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

Very low bit rate image coding using redundant dictionaries

Lorenzo Granai, Lorenzo Peotta, Pierre Vandergheynst

Very 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 images in a redundant geometrically inspired library of functions, followed by suitable coding techniques. Best N-term 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. Finally the last step in our algorithm is an enhancement layer that encodes the residual image: in our simulation we have used a genuine embedded wavelet codec.

SPIE2003

Hybrid Video Coding based on Bidimensional Matching Pursuit

Lorenzo Granai, Emilio Maggio, Lorenzo Peotta, Pierre Vandergheynst

Hybrid video coding combines together two stages: first, motion estimation and compensation predict each frame from the neighboring frames, then the prediction error is coded, reducing the correlation in the spatial domain. In this work, we focus on the latter stage, presenting a scheme that profits from some of the features introduced by the standard H.264/AVC for motion estimation and replaces the transform in the spatial domain. The prediction error is so coded using the matching pursuit algorithm which decomposes the signal over an appositely designed bidimensional, anisotropic, redundant dictionary. Comparisons are made among the proposed technique, H.264, and a DCT-based coding scheme. Moreover, we introduce fast techniques for atom selection, which exploit the spatial localization of the atoms. An adaptive coding scheme aimed at optimizing the resource allocation is also presented, together with a rate-distortion study for the matching pursuit algorithm. Results show that the proposed scheme outperforms the standard DCT, especially at very low bit rates.

2004

Hybrid video coding using bi-dimensional matching pursuit

Lorenzo Granai, Emilio Maggio, Lorenzo Peotta, Pierre Vandergheynst

In this report we propose a new coding scheme based on the Matching Pursuit algorithm and exploiting some of the new features introduced by H.264 for motion estimation. Main points of this work are the design of a redundant dictionary suitable for coding displaced frame dierences, the use of fast techniques for atom selection, which work in the Fourier domain and exploit the spatial localization of the atoms, the adaptive coding scheme aimed at optimizing the resouce allocation for transmitting the atom parameters and the Rate-Distortion optimization.

2003

Matching Pursuit with Block Incoherent Dictionaries

Lorenzo Peotta, Pierre Vandergheynst

There has been an intense activity recently 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. This paper investigates a new class of overcomplete dictionaries, called block incoherent dictionaries, where coherence can be arbitrarily big. 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.

2007

On the Use of A Priori Information for Sparse Signal Representations

Oscar Divorra Escoda, Lorenzo Granai, Pierre Vandergheynst

This report studies the effect of introducing a priori knowledge to recover sparse representations when overcomplete dictionaries are used. We focus mainly on Greedy algorithms and Basis Pursuit as for our algorithmic basement, while a priori is incorporated by suitably weighting the elements of the dictionary. A unique sufficient condition is provided under which Orthogonal Matching Pursuit, Matching Pursuit and Basis Pursuit are able to recover the optimally sparse representation of a signal when a priori information is available. Theoretical results show how the use of "reliable" a priori information can improve the performances of these algorithms. In particular, we prove that sufficient conditions to guarantee the retrieval of the sparsest solution can be established for dictionaries unable to satisfy the results of Gribonval and Vandergheynst and Tropp. As one might expect, our results reduce to the classical case when no a priori information is available. Some examples illustrate our theoretical findings.

2004

Algorithmic aspects of sparse approximations

Philippe Jost

Typical tasks in signal processing may be done in simpler ways or more efficiently if the signals to analyze are represented in a proper way. This thesis deals with some algorithmic problems related to signal approximation, more precisely, in the novel field of sparse approximation using redundant dictionaries of functions. Orthogonal bases permit to approximate signals by just taking the N waveforms whose associated projections have maximal amplitudes. This nice property is no longer valid if the used base is redundant. In fact, finding the best decomposition becomes a NP Hard problem in the general case. Thus, suboptimal heuristics have been developed; the best known ones are Matching Pursuit and Basis Pursuit. Both remain highly complex which prevent them from being used in practice in many situations. The first part of the thesis is concerned with this computational bottleneck. We propose to create a tree structure endowing the dictionary and grouping similar atoms in the same branches. An approximation algorithm, called Tree-Based Pursuit, exploiting this structure is presented. It considerably lowers the cost of finding good approximations with redundant dictionaries. The quality of the representation does not only depend on the approximation algorithm but also on the dictionary used. One of the main advantages of these techniques is that the atoms can be tailored to match the features present in the signal. It might happen that some knowledge about the class of signals to approximate directly leads to the dictionary. For most natural signals, however, the underlying structures are not clearly known and may be obfuscated. Learning dictionaries based on examples is an alternative to manual design and is gaining in interest. Most natural signals exhibit behaviors invariant to translations in space or in time. Thus, we propose an algorithm to learn redundant dictionaries under the translation invariance constraint. In the case of images, the proposed solution is able to recover atoms similar to Gabor functions, line edge detectors and curved edge detectors. The two first categories were already observed and the third one completes the range of natural features and is a major contribution of this algorithm. Sparsity is used to define the efficiency of approximation algorithms as well as to characterize good dictionaries. It directly comes from the fact that these techniques aim at approximating signals with few significant terms. This property was successfully exploited as a dimension reduction method for different signal processing tasks as analysis, de-noising or compression. In the last chapter, we tackle the problem of finding the nearest neighbor to a query signal in a set of signals that have a sparse representation. We take advantage of sparsity to approximate quickly the distance between the query and all elements of the database. In this way, we are able to prune recursively all elements that do not match the query, while providing bounds on the true distance. Validation of this technique on synthetic and real data sets confirms that it could be very well suited to process queries over large databases of compressed signals, avoiding most of the burden of decoding.

EPFL2007

Sparsity & [and] dictionaries - algorithms & [and] design

Karin Schnass

With the flood of information available today the question how to deal with high dimensional data/signals, which are cumbersome to handle, to calculate with and to store, is highly important. One approach to reducing this flood is to find sparse signal representations, as a signal that is the linear combination of a few elements from a pool of building blocks, can be reduced to the few coefficients of this representation. If these building blocks form a basis, finding the sparse representation poses no problem but unfortunately not many signal classes are sparse in a basis. Taking more building blocks, i.e. a redundant dictionary, increases the chances of having sparse representations, but actually finding them becomes very hard. This led to the development of numerous strategies and algorithms for finding sparse representations, with varying complexity and success rate. The first part of the thesis deals with two of those algorithms, Thresholding and Matching Pursuit, from a more theoretical point of view. It is shown that both those greedy algorithms can be improved with a little trick, that does not increase their complexity, and that when considering their average instead of their worst case performance they perform quite well in comparison to more complex methods. The second part of thesis treats questions concerning the whole dictionary and its properties. First it gives more evidence that sparsity is useful by extending the concept of compressed sensing to signals that are sparse not in a basis but in a redundant dictionary. Thus to record a sparse signal it is not necessary to make as many measurements as the dimension of the signal but only a multiple of the number of dictionary elements used to represent it. Next we show that dictionaries cannot only provide sparse representations but that their geometric properties can also be exploited to model data structures. Here we explain how to model different subclasses of a class of signals by incoherent subspaces, present an algorithm to learn a dictionary made out of these subspaces and then use it for classification of faces. Finally we turn back to the sparse representation problem and study the fundamental question how to find a dictionary providing sparse representations. We pick up the idea to learn a dictionary via minimisation of a continuous cost function and provide conditions, guaranteeing that the decomposition of a collection of training signals into a dictionary and a coefficient matrix constitutes a local minimum. We also analyse statistically when these conditions are fulfilled with high probability.