A simple test to check the optimality of sparse signal approximations

Rémi Gribonval (1) , Rosa Maria Figueras I Ventura (2) , Pierre Vandergheynst (2)

1 METISS - Speech and sound data modeling and processing
2 LTS2 - EPFL

Approximating a signal or an image with a sparse linear expansion from an overcomplete dictionary of atoms is an extremely useful tool to solve many signal processing problems. Finding the sparsest approximation of a signal from an arbitrary dictionary is an NP-hard problem. Despite of this, several algorithms have been proposed that provide sub-optimal solutions. However, it is generally difficult to know how close the computed solution is to being ``optimal'', and whether another algorithm could provide a better result. In this paper we provide a simple test to check whether the output of a sparse approximation algorithm is nearly optimal, in the sense that no significantly different linear expansion from the dictionary can provide both a smaller approximation error and a better sparsity. As a by-product of our theorems, we obtain results on the identifiability of sparse overcomplete models in the presence of noise, for a fairly large class of sparse priors.

Domaines: Traitement du signal et de l'image [eess.SP]; Traitement du signal et de l'image [eess.SP]

Rémi Gribonval, Rosa Maria Figueras I Ventura, Pierre Vandergheynst. A simple test to check the optimality of sparse signal approximations. Acoustics, Speech and Signal Processing, 2005. ICASSP 2005. IEEE International Conference on, Mar 2005, Philadelphia, PA, United States. pp.V/717 -- V/720, ⟨10.1109/ICASSP.2005.1416404⟩. ⟨inria-00564503⟩