Finding sparse representation of quantized frame coefficients using 0-1 integer programming

The use of overcomplete dictionaries, or frames, has received increased attention in low-bit-rate compression. Several vector selection algorithms, such as Matching Pursuit, Orthogonal Matching Pursuit and FOCUSS have been developed to get sparse representations of signals. In these algorithms, continuous valued coefficients are found and subsequently quantized. The latter part can cause unwanted effects on the quality of the reconstructed signal. We propose an algorithm that merges the selection and quantization procedures by using 0-1 integer programming. The object is to minimize the distortion measured by the l ₁-norm, subject to a bound on the number of “ones” in a binary representation of the frame coefficients. This bound is an indirect measure of the bit rate. Our new algorithm finds the globally optimal solution based on the abovementioned criteria