An algebraic approach to the subset selection problem

The need for decomposing a signal into its optimal representation arises in many applications. In such applications, one can usually represent the signal as a combination of an over-complete dictionary elements. The non-uniqueness of signal representation, in such dictionaries, provides us with the opportunity to adapt the signal representation to the signal. The adaptation is based on sparsity, resolution and stability of the signal representation. In this paper, we propose an algebraic approach for identifying the sparsest representation of a given signal in terms of a given over-complete dictionary. Unlike other current techniques, our approach is guaranteed to find the solution, given that certain conditions apply. We explain these conditions.