Random Tessellations, Restricted Isometric Embeddings, and One Bit Sensing

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$\mathrm{.}Weshowthatfor$ m \gtrsim \delta ^{-2} s \log \frac ns$, 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 ${\mathrm{\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.