Gribonval, R.Figueras i Ventura, R.Vandergheynst, P.2006-06-142006-06-142006-06-14200510.1109/ICASSP.2005.1416404https://infoscience.epfl.ch/handle/20.500.14299/231618Approximating a signal or an image with a sparse linear expansion from an over-complete 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 over-complete models in the presence of noise, for a fairly large class of sparse priors.approximationbasis pursuitBayesian estimationconvex programmingFOCUSSgreedy algorithmidenti abilityinverse problemLTS2matching pur- suitovercomplete dictionarysparse priorsparse representationtext::conference output::conference proceedings::conference paper