Classification of unions of subspaces with sparse representations

We propose a preliminary investigation on the benefits and limitations of classifiers based on sparse representations. We specifically focus on the union of subspaces data model and examine binary classifiers built on a sparse non linear mapping (in a redundant dictionary) followed by a linear classifier. We study two common sparse non linear mappings (namely \ell_0 and \ell_1) and show that, in both cases, there exists a finite dictionary such that the classifier discriminates the two classes correctly. This result paves the way towards a better understanding of the increasingly popular classifiers based on sparse representation