On the Use of A Priori Information for Sparse Signal Approximations

Recent results have underlined the importance of incoherence in redundant dictionaries for a good behavior of decomposition algorithms like Matching and Basis Pursuits. However, appropriate dictionaries for a given application may not necessarily be able to meet the incoherence condition. In such case, decomposition algorithms may completely fail in the retrieval of the sparsest approximation. This paper studies the effect of introducing a priori knowledge when recovering sparse approximations over redundant dictionaries. Theoretical results show how the use of reliable a priori information (which in this work appears under the form of weights) can improve the performances of standard approaches such as greedy algorithms and relaxation methods. Our results reduce to the classical case when no a priori information is available. Examples validate and illustrate our theoretical statements.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Oscar Divorra Escoda, Lorenzo Granai, Pierre Vandergheynst
2006
Article

Résumé

Official source

https://infoscience.epfl.ch/record/87274?ln=fr

À propos de ce résultat

Concepts associés (6)

Concepts associés

Chargement

Publications associées (4)

Publications associées

Chargement

Poursuite de base

La poursuite de base (de l'anglais basis pursuit), aussi appelée recouvrement par norme \ell_1 ou plus simplement recouvrement \ell_1, est une technique d'optimisation mathém

Algorithme glouton

Un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afi

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

On the Use of A Priori Information for Sparse Signal Approximations

Oscar Divorra Escoda, Lorenzo Granai, Pierre Vandergheynst

This report is the extension to the case of sparse approximations of our previous study on the effects of introducing a priori knowledge to solve the recovery of sparse representations when overcomplete dictionaries are used. Greedy algorithms and Basis Pursuit Denoising are considered in this work. Theoretical results show how the use of "reliable" a priori information (which in this work appears under the form of weights) can improve the performances of these methods. In particular, we generalize the sufficient conditions established by Tropp and Gribonval & Vandergheynst, that guarantee the retrieval of the sparsest solution, to the case where a priori information is used. We prove how the use of prior models at the signal decomposition stage influences these sufficient conditions. The results found in this work reduce to the classical case of Tropp and Gribonval & Vandergheynst when no a priori information about the signal is available. Finally, examples validate and illustrate the theoretical results. Finally, examples validate and illustrate theoretical results.

2004

Chargement

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

Chargement

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

Chargement