# Binary and Multi-Bit Coding for Stable Random Projections

arXiv: https://arxiv.org/abs/1503.06876 · HTML: https://mlsanity.com/paper/1503.06876/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2015.

## Built on by (most cited first, 3 of 3)

- [One Loss for Quantization: Deep Hashing with Discrete Wasserstein Distributional Matching](https://mlsanity.com/paper/2205.15721/) (2022)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Noisy ℓ0-Sparse Subspace Clustering on Dimensionality Reduced Data](https://mlsanity.com/paper/2206.11079/) (2022)

## Abstract (arXiv)

We develop efficient binary (i.e., 1-bit) and multi-bit coding schemes for estimating the scale parameter of α-stable distributions. The work is motivated by the recent work on one scan 1-bit compressed sensing (sparse signal recovery) using α-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 α-th frequency moment. In fact, the method applies to the general scale family of distributions, not limited to α-stable distributions. Due to the heavy-tailed nature of α-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 α=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, π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.