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 1bit 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 kbit quantized signal of dimension n from its O(log n) 1bit measurements via invoking n times of KullbackLeibler divergence based nearest neighbor search. Compared to CS and 1bit 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 1bit 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 kbit quantized signal from its 1bit measurements.
Highlighting Features of HCS:
1. HCS provides simple and lowcost sampling and recovery schemes: the sampling and sensing are integrated to 1bit measurements, while the recovery and quantization are integrated to quantized recovery. Furthermore, both the 1bit measurement and the quantized recovery do not require analogtodigital converters (ADC) with a high sampling rate.
2. The recovery in HCS only requires to compute nk KullbackLeibler (KL) divergences for obtaining kbit recovery of an ndimensional signal, and thus is a noniterative, linear algorithm. Only simple computations are required.
3. According to the theoretical analysis of HCS, merely m=O(log n) 1bit 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 01 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.
Multilabel Learning: compressed labeling (CL) on distilled labelsets (published on Machine Learning Journal). A brief introduction can be found here. PDF can be downloaded here.

ExperimentsSignal quantization recovery experimental results. 

Code


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