A simple test to check the optimality of a sparse signal approximation

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 a 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 sma


Published in:
Signal Processing, 86, 3, 496-510
Year:
2006
Keywords:
Laboratories:




 Record created 2006-06-14, last modified 2018-12-03


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)