Resilience properties of redundant expansions under additive noise and quantization

Representing signals using coarsely quantized coefficients of redundant expansions is an interesting source coding paradigm, the most important practical case of which is oversampled analog-to-digital (A/D) conversion. Signal reconstruction from quantized redundant expansions and the accuracy of such representations are problems which are not well understood and we study them in this paper for uniform scalar quantization in finite-dimensional spaces. To give a more global perspective, we first present an analysis of the resilience of redundant expansions to degradation by additive noise in general, and then focus on the effects of uniform scalar quantization. The accuracy of signal representations obtained by applying uniform scalar quantization to coefficients of redundant expansions, measured as the mean-squared Euclidean norm of the reconstruction error, has been previously shown to be lower-bounded by an 1/r/sup 2/ expression. We establish some general conditions under which the 1/r/sup 2/ accuracy can actually be attained, and under those conditions prove a 1/r/sup 2/ upper error bound. For a particular kind of structured expansions, which includes many popular frame classes, we propose reconstruction algorithms which attain the 1/r/sup 2/ accuracy at low numerical complexity. These structured expansions, moreover, facilitate efficient encoding of quantized coefficients in a manner which requires only a logarithmic bit-rate increase in redundancy, resulting in an exponential error decay in the bit rate. Results presented in this paper are immediately applicable to oversampled A/D conversion of periodic bandlimited signals.