Polynomial Time and Stack Decoding Solutions to Bounded Error Subset Selection

The goal of bounded error subset selection (BESS) is to find the sparsest representation of an Ntimes1 vector b using vectors from a dictionary A of size NtimesM, such that the approximation is within a distance delta from b. Here delta is a user defined approximation threshold. Specifically, the goal is to find the sparsest vector x such that parAx - bpar les delta. The BESS is a reformulation of the classical subset selection problem. We describe two enumeration approaches with bounded complexities that find the optimal solution to the BESS problem. In particular, the paper describes the first exhaustive enumeration solution to subset selection type problems with polynomial complexity. Furthermore, it also describes a lower complexity stack decoding approach that finds a solution to the BESS problem with a complexity that is proportional to that of orthogonal matching pursuit. The approaches described here have a markedly better rate-distortion behavior than any of the other known solutions to the subset selection and BESS problems