Binary and Multi-Bit Coding for Stable Random Projections

Abstract

We develop efficient binary (i.e., 1-bit) and multi-bit coding schemes for estimating the scale parameter of $\alpha$-stable distributions. The work is motivated by the recent work on one scan 1-bit compressed sensing (sparse signal recovery) using $\alpha$-stable random projections, which requires estimating of the scale parameter at bits-level. Our technique can be naturally applied to data stream computations for estimating the $\alpha$-th frequency moment. In fact, the method applies to the general scale family of distributions, not limited to $\alpha$-stable distributions. Due to the heavy-tailed nature of $\alpha$-stable distributions, using traditional estimators will potentially need many bits to store each measurement in order to ensure sufficient accuracy. Interestingly, our paper demonstrates that, using a simple closed-form estimator with merely 1-bit information does not result in a significant loss of accuracy if the parameter is chosen appropriately. For example, when $\alpha=0+$, 1, and 2, the coefficients of the optimal estimation variances using full (i.e., infinite-bit) information are 1, 2, and 2, respectively. With the 1-bit scheme and appropriately chosen parameters, the corresponding variance coefficients are 1.544, $\pi^2/4$, and 3.066, respectively. Theoretical tail bounds are also provided. Using 2 or more bits per measurements reduces the estimation variance and importantly, stabilizes the estimate so that the variance is not sensitive to parameters. With look-up tables, the computational cost is minimal.