Random Tessellations, Restricted Isometric Embeddings, and One Bit Sensing

Abstract

We obtain mproved bounds for one bit sensing. For instance, let $K_s$ denote the set of $s$-sparse unit vectors in the sphere ${\mathbb{S}}^n$ in dimension $n+1$ with sparsity parameter $0<s<n+1$ and assume that $0<\delta <1$. We show that for $m\gtrsim {\delta }^{-2}s\log \frac{n}{s}$, the one-bit map $$x\mapsto [sgn⟨x,g_j⟩{]}_{j=1}^m,$$ where $g_j$ are iid gaussian vectors on ${\mathbb{R}}^{n+1}$, with high probability has $\delta$-RIP from $K_s$ into the $m$-dimensional Hamming cube. These bounds match the bounds for the {linear} $\delta$-RIP given by $x\mapsto \frac{1}{m}[⟨x,g_j⟩{]}_{j=1}^m$, from the sparse vectors in ${\mathbb{R}}^n$ into ${\ell }^1$. In other words, the one bit and linear RIPs are equally effective. There are corresponding improvements for other one-bit properties, such as the sign-product RIP property.

22 pages, 2 figures

References in corpus (2)

• Quantized Iterative Hard Thresholding: Bridging 1-bit and High-Resolution Quantized Compressed Sensing
• One Bit Sensing, Discrepancy, and Stolarsky Principle