Bounded subset selection with noninteger coefficients

The subset selection problem is known to be NP hard. It was recently shown that by relaxing the requirement that the reconstructed signal be equal to the original, one ends with a bounded error subset selection that admits a solution in polynomial time. In the bounded error subset selection problem, the reconstructed signal is allowed to differ from the original signal by a bounded error. This bounded error formulation is natural in many applications, such as coding. In this paper, we improve the accuracy and reduce the complexity of the previously proposed approach for solving the bounded error subset selection problem. In particular, unlike the previously proposed approach for solving the bounded error subset selection problem, our new algorithm accommodates cases where the coefficients of the closest sparse approximation to the underlying signal in the dictionary are not necessarily one. Our new algorithm is based on weighting the dictionary vectors by the minimum l₂ norm solution and relaxing the integer constraint on the coefficients of the dictionary vectors. It is shown to guarantee high signal accuracy and sparsity. Compared with the Basis Pursuit and the Method of Frames (MoF) algorithms, the proposed algorithm has a better rate-distortion behavior.