QUANTIZED OVERCOMPLETE EXPANSIONS IN IRN - ANALYSIS, SYNTHESIS, AND ALGORITHMS

Coefficient quantization has peculiar qualitative effects on represent ations of vectors in IRN with respect to overcomplete sets of vectors, These effects are investigated in two settings: frame expansions (rep resentations obtained by forming inner products with each element of t he set) and matching pursuit expansions (approximations obtained by gr eedily forming linear combinations), Zn both cases, based on the conce pt of consistency, it is shown that traditional linear reconstruction methods are suboptimal, and better consistent reconstruction algorithm s are given, The proposed consistent reconstruction algorithms were in each case implemented, and experimental results are included, For fra me 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 tha t optimal reconstruction methods will yield O(1/r(2)) mean-squared err or (MSE), and that consistency is sufficient to insure this asymptotic behavior, A result on the asymptotic tightness of random frames is al so 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 wi th a nonlinear (consistent) reconstruction algorithm, and generally co mpetitive performance at low bit rates.