Welcome to Hamming Compressed Sensing Homepage

Compressed sensing (CS) proves that a sparse or compressible signal can be exactly recovered from its linear measurements, rather than uniform samplings, at a rate significantly lower than the Nyquist rate.However, CS and 1-bit CS cannot directly recover quantized signals preferred in digital systems and require time consuming recovery. We introduce Hamming compressed sensing (HCS) that directly recovers a k-bit quantized signal of dimension n from its O(log n) 1-bit measurements via invoking n times of Kullback-Leibler divergence based nearest neighbor search. Compared to CS and 1-bit CS, HCS allows the signal to be dense, takes considerably less (linear) recovery time and requires substantially less measurements (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.

Underlying Idea of HCS:

Sacrificing and leveraging quantization error (note this error is inevitable in digital systems) for decreasing the number of measurements. Whereas CS leveraging sparsity of signal for decreasing the number of measurements.

Extensions of HCS in Machine Learning:

Since machine learning problems always aim at predicting qiantized signals such as 0-1 labels and ranking, it is very natural to extend HCS to solving many significant machine learning problems, with the benefits of reducing problem complexity and improving the prediction performance.

Multi-label Learning: compressed labeling (CL) on distilled labelsets (published on Machine Learning Journal). A brief introduction can be found here. PDF can be downloaded here.


Submissions, accepted papers, technique reports of Hamming Compressed Sensing. 


Signal quantization recovery experimental results. 


Code of Hamming Compressed Sensing 


Please feel free to contact us if you are interested in Hamming Compressed Sensing