Quantization

Quantization is a necessary step in the acquisition of almost any physical signal. A significant part of my work involves understanding the effects of quantization in signal acquisition quality and methods to reduce those effects.

Compressive Sensing and Quantization

Compressive Sensing has delivered a significant reduction in sampling complexity, especially when measured in terms of number of measurements. However, the interaction of Compressive Sensing with Quantization is not well understood. One particularly pertinent question is whether Compressive Sensing is an efficient compression method compared to classical methods such as transform coding.

 In [1] I demonstrated that simple scalar quantization of compressive measurements is not using the resulting bits as efficiently as transform coding. If compressive sensing is to be used for efficient compression—i.e, if we are interested purely in minimizing the signal distortion at a given bitrate—a different quantization approach is necessary.

The geometric intuition is that a sparse signal occupies a union of low-dimensional subspaces of the signal space which, when projected through the measurement operator, occupy a low dimensional subspace of the measurement space. On the other hand, scalar quantization of the measurement space defines a quantization grid similar to the one shown on the left. As we can see from the figure, each low-dimensional subspace intersects very few quantization cells, i.e., uses very few of the quantization points available. Even when we consider the union of all the subspaces comprising the sparse signal set and count carefully the intersected cells, we can show the bit-use is suboptimal.

This intuition further suggests that we are better-off obtaining fewer measurements that are finely quantized—as long as we have enough to reconstruct the signal—rather than more measurements that are coarsely quantized. The caveat here is that his is purely a rate-distortion result assuming perfect measurements, e.g., for the purpose of compression. When it comes to sensing and sampling, we should also take the effects of measurement noise into account and the cost of implementing a high-precision quantizer. Once we do that, then coarse quantization schemes, such as 1-bit CS become much more appealing. On the other hand, when it comes to improving the rate-distortion trade-off, schemes such as universal quantization might be more appropriate.

Quantization and Saturation for CS

Another pertinent question is how to design a practical scalar quantizer for CS applications. In practice, finite-range uniform quantizers are widely available, inexpensive, and commonly used. For such quantizers, the main design parameters are the quantizer precision in bits, B and the saturation level G (or, alternatively, the quantization interval \Delta=2^{1-B}G). The smaller the quantization interval \Delta—i.e, the saturation level G—the smaller the error due to quantization; the smaller the saturation level G, the larger the error due to saturation.

In classical systems, conventional wisdom recommends a low saturation level (often selected using Lloyd-Max criteria, or some variant). However, the non-linear reconstruction algorithms used in CS and the democratic property of the measurements make that conventional wisdom obsolete [2]. In fact, it is recommended that CS acquisition systems are tuned to saturate significantly more. The saturated measurements can then either be rejected (based on the democratic property of CS measurements) or used as constraints in the reconstruction (also known as consistent reconstruction).

The figure on the right demonstrates this effect in a particular experimental setup. It plots the reconstruction performance in terms of reconstruction SNR (left y-axis) as a function of the saturation level (x-axis) and the corresponding fraction of saturated measurement (right y-axis). The three curves correspond to conventional CS reconstruction methods taking the saturated measurements at face value (solid line), rejecting them (dashed line), or treating them as constraints (dotted line). The reconstructed signal SNR improves as the saturation level increases, but only up to a point. Reducing the saturation further to be lower that ~10% actually hurts performance. While the performance of rejecting the measurements vs. imposing consistency seems similar, closer examination in a variety of signal conditions shows that consistent reconstruction reliably outperforms the rejection approach. However, it requires modification of the algorithms. When this is not possible, rejection is a very good close alternative;  [2] contains more details and extensive simulations.

Quantization of Frame Representations—Sigma-Delta generalizations

In my doctoral work I studied the limits of scalar quantization and revisited Sigma-Delta (ΣΔ) quantization (or ΣΔ noise shaping)[3]. Classical ΣΔ systems operate on uniformly oversampled signals, using a simple feedback loop, as shown in the figure on the right in on of its many discrete-time versions. The signal x[n] is an oversampled representation of the signal of interest. The quantized output signal is \hat{x}[n]. The quantization error e[n] is fed back through a loop filter and subtracted from x[n] before the next sample is quantized. The standard analysis of this loop is based on a simple additive noise model of quantization, which models the quantization error as additive white noise, independent of the signal. While this model is fairly inaccurate, especially at very coarse quantization levels, it has proved extremely useful in designing such systems.

My thesis and the followup papers provided a new interpretation of ΣΔ as a greedy algorithm that compensates quantization error using projections. This allows the extension of ΣΔ quantization schemes to arbitrary oversampled systems, such as frame representations, by modifying the feedback filter H_f(z) and the feedback sequence[4, 5, 3]. This new interpretation further reveals some design choices in ΣΔ quantization, such as a tree quantizer, which are not available for the classical uniformly oversampled frame. It also enables extensions to the compensation of other kinds of errors, such as erasures, in the coefficient stream [6, 7].


[1]

P. T. Boufounos and R. G. Baraniuk, “Quantization of sparse representations,” Rice University ECE Department Technical Report 0701. Summary appears in Proc. Data Compression Conference (DCC), Snowbird, UT, March 27-29, 2007.

[Bibtex]

@inproceedings{BB_DCC07,
  Address =   {Snowbird, UT},
  Author =   {Boufounos, P. T. and Baraniuk, R. G.},
  Booktitle =   {Rice University ECE Department Technical Report 0701. Summary appears in Proc. Data Compression Conference (DCC)},
  Month =   {March 27-29},
  Title =   {Quantization of sparse representations},
  Url =     {http://hdl.handle.net/1911/13034},
  Year =   {2007}
}

[2]

J. N. Laska, P. T. Boufounos, M. A. Davenport, and R. G. Baraniuk, “Democracy in action: Quantization, saturation, and compressive sensing,” Applied and Computational Harmonic Analysis, v. 31, no. 3, pp. 429-443, November, 2011.

[preprint] [Bibtex]

@article{LBDB_ACHA11,
  Author =   {Laska, J. N. and Boufounos, P. T. and Davenport, M. A. and Baraniuk, R. G.},
  Doi =     {j.acha.2011.02.002},
  Journal =   {Applied and Computational Harmonic Analysis},
  Month =   {November},
  Number =   {3},
  Pages =   {429-443},
  Pdf =     {http://boufounos.com/Publications/LBDB_Democracy09.pdf},
  Publisher =   {Elsevier},
  Title =   {Democracy in action: Quantization, saturation, and compressive sensing},
  Url =     {http://dx.doi.org/10.1016/j.acha.2011.02.002},
  Volume =   {31},
  Year =   {2011}
}

[3]

P. T. Boufounos, “Quantization and erasures in frame representations,” Cambridge, MA, January 2006, 2006.

[Bibtex]

@phdthesis{B_DSc06,
  Address =   {Cambridge, MA},
  Author =   {Boufounos, P. T.},
  Month =   {January 2006},
  School =   {MIT},
  Title =   {Quantization and erasures in frame representations},
  Type =   {D. Sc. Thesis},
  Url =          {http://boufounos.com/Publications/Boufounos_DScThesis06.pdf},
  Year =   {2006}
}

[4]

P. T. Boufounos and A. V. Oppenheim, “Quantization noise shaping on arbitrary frame expansions,” Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Philadelphia, PA, March 18-23, 2005.

[Bibtex]

@inproceedings{BO_ICASSP05,
  Address =   {Philadelphia, PA},
  Author =   {Boufounos, P. T. and Oppenheim, A. V.},
  Booktitle =   {Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP)},
  Doi =     {10.1109/ICASSP.2005.1415981},
  Month =   {March 18-23},
  Title =   {Quantization noise shaping on arbitrary frame expansions},
  Url =     {http://dx.doi.org/10.1109/ICASSP.2005.1415981},
  Year =   {2005}
}

[5]

P. T. Boufounos and A. V. Oppenheim, “Quantization noise shaping on arbitrary frame expansions,” EURASIP Journal on Applied Signal Processing, Special issue on Frames and Overcomplete Representations in Signal Processing, Communications, and Information Theory, v. 2006, 2006, Article ID 53807, 12 pages.

[preprint] [Bibtex]

@article{BO_JASP06,
  Author =   {Boufounos, P. T. and Oppenheim, A. V.},
  Doi =     {10.1155/ASP/2006/53807},
  Journal =   {EURASIP Journal on Applied Signal Processing, Special issue on Frames and Overcomplete Representations in Signal Processing, Communications, and Information Theory},
  Note =   {Article ID 53807, 12 pages},
  Pdf =     {http://boufounos.com/Publications/Boufounos_Oppenheim_JASP05.pdf},
  Publisher =   {Hindawi Publishing Corp.},
  Title =   {Quantization noise shaping on arbitrary frame expansions},
  Url =     {http://dx.doi.org/10.1155/ASP/2006/53807},
  Volume =   {2006},
  Year =   {2006}
}

[6]

P. T. Boufounos and A. V. Oppenheim, “Compensation of coefficient erasures in frame representations,” Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Toulouse, France, May 14-19, 2006.

[Bibtex]

@inproceedings{BO_ICASSP06,
  Address =   {Toulouse, France},
  Author =   {Boufounos, P. T. and Oppenheim, A. V.},
  Booktitle =   {Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP)},
  Doi =     {10.1109/ICASSP.2006.1660787},
  Month =   {May 14-19},
  Title =   {Compensation of coefficient erasures in frame representations},
  Url =     {http://dx.doi.org/10.1109/ICASSP.2006.1660787},
  Year =   {2006}
}

[7]

P. T. Boufounos, A. V. Oppenheim, and V. K. Goyal, “Causal compensation for erasures in frame representations,” IEEE Trans. Signal Processing, v. 56, no. 3, pp. 1071-1082, March, 2008.

[preprint] [Bibtex]

@article{BOG_TSP07,
  Author =   {Boufounos, P. T. and Oppenheim, A. V. and Goyal, V. K.},
  Doi =     {10.1109/TSP.2007.908963},
  Journal =   {IEEE Trans. Signal Processing},
  Month =   {March},
  Number =   {3},
  Pages =   {1071-1082},
  Pdf =     {http://boufounos.com/Publications/BOG_TSP08.pdf},
  Title =   {Causal compensation for erasures in frame representations},
  Url =     {http://dx.doi.org/10.1109/TSP.2007.908963},
  Volume =   {56},
  Year =   {2008}
}