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 < δ< 1$. We show that for $m \gtrsim δ^{-2} s \log \frac ns$, the one-bit map $x \mapsto \bigl[ {sgn} \langle x,g_j \rangle \bigr] _{j=1} ^{m},$ where $g_j$ are iid gaussian vectors on $\mathbb R ^{n+1}$, with high probability has $δ$-RIP from $K_s$ into the $m$-dimensional Hamming cube. These bounds match the bounds for the {linear} $δ$-RIP given by $x \mapsto \frac 1m[\langle x,g_j \rangle ] _{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.

No reviews yet.

No comments yet.