Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals
share
A universal 1-bit compressive sensing (CS) scheme consists of a measurement matrix A such that for all signals x belonging to a particular class, x can be approximately recovered from sign(Ax). 1-bit CS models extreme quantization effects where only one bit of information is revealed per measurement. We focus on universal support recovery for 1-bit CS in the case of sparse signals with bounded dynamic range. Specifically, a vector x ∈ℝ^n is said to have sparsity k if it has at most k nonzero entries, and dynamic range R if the ratio between its largest and smallest nonzero entries is at most R in magnitude. Our main result shows that if the entries of the measurement matrix A are i.i.d. Gaussians, then under mild assumptions on the scaling of k and R, the number of measurements needs to be Ω̃(Rk^3/2) to recover the support of k-sparse signals with dynamic range R using 1-bit CS. In addition, we show that a near-matching O(R k^3/2log n) upper bound follows as a simple corollary of known results. The k^3/2 scaling contrasts with the known lower bound of Ω̃(k^2 log n) for the number of measurements to recover the support of arbitrary k-sparse signals.
READ FULL TEXT