Reduced complexity bounded error subset selection

A reduced complexity version of the bounded error subset selection (BESS) algorithm is proposed. By relaxing the integer constraint in the original BESS algorithm, we show that the BESS problem can be reformulated as an ordinary linear program instead of an integer program with exponential worst-case complexity. We retain the sparseness of the representation in the modified BESS by weighting the dictionary with the minimum 2-norm solution of the subset selection problem corresponding to the BESS problem at hand. The proposed algorithm is compared to the basis pursuit, orthogonal matching pursuit, and the best orthogonal basis algorithms. It is shown that the proposed algorithm has a better packing property and an improved rate-distortion behavior.