– C. Herzet (Inria) : Beyond Uniform Conditions for Sparse Reconstruction

Carte non disponible

Date/heure
Date(s) - 20 février 2015

Catégories Pas de Catégories


Beyond Uniform Conditions for Sparse Reconstruction\nBy Cédric Herzet, Inria\n\nThis talk takes place within the context of sparse representations, in which one tries to decompose a vector/function as a combination of a few elementary signals. This model has recently been shown to be well-suited to the characterization of many signals and has thus sparked a surge of interest in the scientific community. Unfortunatley, given a particular set of elementary signals, the search of the sparsest solution is known to be NP-Hard. Hence, many heuristic algorithms have been proposed in the literature to compute approximate but tractable solutions. Because these algorithms are suboptimal (in the sense that they do not address the exact sparse representation problem), the derivation of conditions ensuring their success is of particular interest. \n\nIn this talk, we will focus our attention on the guarantees of success of two particular algorithms : “Orthogonal Matching Pursuit” (OMP) and “Orthogonal Least Squares” (OLS). While the behavior of OMP has been known for a decade, the condition of success of OLS has only been derived recently. We will review these conditions and show how they can be adapted/relaxed in two particular cases of practical interest : i) when some prior information is available about the position of the nonzero coefficients\ ; ii) when the nonzero coefficients of the sparse signal obey some decay. \n\nThe presentation will be based on the following set of papers :\n\nC. Herzet , A. Drémeau, C. Soussen, « Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay », ArXiV 1401.7533 \nC. Herzet, C. Soussen, J. Idier, R. Gribonval, « Exact Recovery Conditions for Sparse Representations With Partial Support Information », IEEE Trans. on Information Theory, vol 59, nr 11, 2013. \nC. Soussen, R. Gribonval, J. Idier, C. Herzet, « Joint k-step analysis of Orthogonal Matching Pursuit and Orthogonal Least Squares », IEEE Trans. on Information Theory, vol 59, nr 5, May 2013.[