On the Trade-Off between Bit Depth and Number of Samples for a Basic Approach to Structured Signal Recovery from b -Bit Quantized Linear Measurements

Martin Slawski, Ping Li

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We consider the problem of recovering a high-dimensional structured signal from independent Gaussian linear measurements each of which is quantized to $b$ bits. The focus is on a specific method of signal recovery that extends a procedure originally proposed by Plan and Vershynin for one-bit quantization to a multi-bit setting. At the heart of this paper is a characterization of the optimal trade-off between the number of measurements m and the bit depth per measurement $b$ given a total budget of B = m b bits when the goal is to minimize the expected -2 -error in estimating the signal. It turns out that the choice b = 1 is optimal for estimating the unit vector (direction) corresponding to the signal for any level of additive Gaussian noise before quantization as well as for a specific model of adversarial noise, whereas in a noiseless setting the choice b = 2 is optimal for estimating the direction and the norm (scale) of the signal. Moreover, Lloyd-Max quantization is shown to be an optimal quantization scheme with respect to ell -2 -estimation error. Our analysis is corroborated by the numerical experiments showing nearly perfect agreement with our theoretical predictions. This paper is complemented by an empirical comparison to alternative methods of signal recovery. The results of that comparison point to a regime change depending on the noise level: in a low-noise setting, the approach under study falls short of more sophisticated competitors while being competitive in moderate- and high-noise settings.

Original languageEnglish (US)
Pages (from-to)4159-4178
Number of pages20
JournalIEEE Transactions on Information Theory
Volume64
Issue number6
DOIs
StatePublished - Jun 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Compressed sensing
  • Gaussian width
  • low-complexity signals
  • quantization

Fingerprint

Dive into the research topics of 'On the Trade-Off between Bit Depth and Number of Samples for a Basic Approach to Structured Signal Recovery from b -Bit Quantized Linear Measurements'. Together they form a unique fingerprint.

Cite this