Hamming Compressed Sensing-recovering k-bit quantization from 1-bit measurements with linear non-iterative algorithm

We developed a new compressed sensing type signal acquisition paradigm called “Hamming Compressed Sensing (HCS)” to recover signal’s k-bit quantization rather than itself. Directly recovering quantization is much more preferred in practical digital systems. HCS provides a linear, non-iterative quantization recovery algorithm requiring a small amount of measurements, with strong theoretical guarantee of the recovery success. The underlying idea of HCS is to sacrifice the inevitable quantization error for reducing measurements and improving recovery efficiency substantially. Another compelling property of HCS is that it provides a very low-cost sampling scheme.

You can find the submitted HCS paper on Arxiv and especially more information (such as experimental results) on the HCS homepage.

Here is the abstract:

Compressed sensing (CS) and 1-bit CS cannot directly recover quantized signals and require time consuming recovery. In this paper, we introduce \textit{Hamming compressed sensing} (HCS) that directly recovers a k-bit quantized signal of dimensional $n$ from its 1-bit measurements via invoking $n$ times of Kullback-Leibler divergence based nearest neighbor search. Compared with CS and 1-bit CS, HCS allows the signal to be dense, takes considerably less (linear) recovery time and requires substantially less measurements ($\mathcal O(\log n)$). Moreover, HCS recovery can accelerate the subsequent 1-bit CS dequantizer. We study a quantized recovery error bound of HCS for general signals and “HCS+dequantizer” recovery error bound for sparse signals. Extensive numerical simulations verify the appealing accuracy, robustness, efficiency and consistency of HCS.

HCS aims to:

Recovers a k-bit quantized signal from its 1-bit measurements.

Highlighting Features of HCS:

1. HCS provides simple and low-cost sampling and recovery schemes: the sampling and sensing are integrated to 1-bit measurements, while the recovery and quantization are integrated to quantized recovery. Furthermore, both the 1-bit measurement and the quantized recovery do not require analog-to-digital converters (ADC) with a high sampling rate.

2. The recovery in HCS only requires to compute nk Kullback-Leibler (KL) divergences for obtaining k-bit recovery of an n-dimensional signal, and thus is a non-iterative, linear algorithm. Only simple computations are required.

3. According to the theoretical analysis of HCS, merely m=O(log n) 1-bit measurements are sufficient to produce a successful quantized recovery with high probability. Note there is no sparse assumption to the signal x.

About tianyizhou

Research Assistant at University Washington, Seattle, Working on Machine Learning & Statistics in MODE lab leaded by Prof. Carlos Guestrin, and MELODI lab leaded by Prof. Jeff Bilmes.
This entry was posted in Tianyi's work and tagged , , , . Bookmark the permalink.

3 Responses to Hamming Compressed Sensing-recovering k-bit quantization from 1-bit measurements with linear non-iterative algorithm

  1. Igor carron says:


    Do you intend on making an implementation of HCS available ?



    • tianyizhou says:

      Hi Igor,

      The answer is yes, but I am afraid the code will be released at the end of this month, because I have a travel plan recently and need to prepare for exams.


  2. Igor Carron says:


    Great. Let us know when it is available.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s