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:**

**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.

Tianyi,

Do you intend on making an implementation of HCS available ?

Cheers,

Igor

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.

Cheers,

Tianyi

Tianyi,

Great. Let us know when it is available.

Cheers,

Igor.