language: en

[16 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 1, JANUARY 1998]

Quantized Overcomplete Expansions in R N Analysis, Synthesis, and Algorithms

Vivek K Goyal, Student Member, IEEE, Martin Vetterli, Fellow, IEEE, and Nguyen T. Thao, Member, IEEE

Abstract|Coefficient quantization has peculiar qualitative effects on representations of vectors in R N with respect to overcomplete sets of vectors. These effects are investigated in two settings: frame expansions (representations obtained by forming inner products with each element of the set) and matching pursuit expansions (approximations obtained by greedily forming linear combinations). In both cases, based on the concept of consistency, it is shown that traditional linear reconstruction methods are suboptimal, and better consistent reconstruction algorithms are given. The proposed consistent reconstruction algorithms were in each case implemented, and experimental results are included. For frame expansions, results are proven to bound distortion as a function of frame redundancy r and quantization step size for linear, consistent, and optimal reconstruction methods. Taken together, these suggest that optimal reconstruction methods will yield O(1=r 2 ) MSE, and that consistency is sufficient to insure this asymptotic behavior. A result on the asymptotic tightness of random frames is also proven. Applicability of quantized matching pursuit to lossy vector compression is explored. Experiments demonstrate the likelihood that a linear reconstruction is inconsistent, the MSE reduction obtained with a nonlinear (consistent) reconstruction algorithm, and generally competitive performance at low bit rates.

Index Terms Consistent reconstruction, frames, matching pursuit, MSE bounds, optimal reconstruction, overcomplete representations, quantization, source coding

I. Introduction