Binary and MultiBit Coding for Stable Random Projections
[edit]
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:14301438, 2017.
Abstract
The recent work [17] developed a 1bit compressed sensing (CS) algorithm based on $α$stable random projections. Although the work in [17] showed that the method is a strong competitor of other existing 1bit algorithms, the procedure requires knowing $K$, the sparsity. Note that $K$ is the $l_0$ norm of the signal. Other existing 1bit CS algorithms require the $l_2$ norm of the signal. In this paper, we develop an estimation procedure for the $l_α$ norm of the signal, where $0<α\leq2$ from binary or multibit measurements. We demonstrate that using a simple closedform estimator with merely 1bit information does not result in a significant loss of accuracy if the parameter is chosen appropriately. Theoretical tail bounds are also provided. Using 2 or more bits per measurement reduces the variance and importantly, stabilizes the estimate so that the variance is not too sensitive to chosen parameters.
Related Material


