Backward sequential elimination for sparse vector subset selection

Selection of a subset of vectors from a larger dictionary of vectors arises in a wide variety of application areas. This problem is known to be NP-har d and many algorithms have been proposed for the suboptimal solution of thi s problem. The focus of this paper is the development of a backward sequent ial elimination algorithm wherein. starting from the full dictionary, eleme nts are deleted until a subset of a desired size is obtained. In contrast t o previous formulations, we start with an overcomplete dictionary of vector s which is often the problem faced in a signal representation context. Once enough vectors have been deleted to give a complete system.. the algorithm is modified to allow further deletion of vectors, In addition, the derived algorithm gives access to the coefficients associated with each vector in representing the signal. This allows us to experiment with different criter ia, including entropy-based and p-norm criteria. for selection of the vecto r to be deleted in each iteration. There is also the flexibility to combine criteria or to switch between criteria at a given stage of the algorithm, Following a series of simulations on a test-case system., we are able to co nclude that the p-norm. close to 1 performs best while the system considere d is overcomplete. A minimum representation error criterion gives the best results once the system considered becomes undercomplete. The performance o f the algorithm is also compared to that of forward selection algorithms on the test-case dictionary. (C) 2001 Elsevier Science B.V. All rights reserv ed.