Random Tessellations, Restricted Isometric Embeddings, and One Bit Sensing

Original · EN

We obtain mproved bounds for one bit sensing. For instance, let Kₛ denote the set of s-sparse unit vectors in the sphere S ⁿ in dimension n+1 with sparsity parameter 0 < s < n+1 and assume that 0 < δ< 1. We show that for m δ⁻² s ns, the one-bit map x [sgn x,gⱼ] ⱼ₌₁ ᵐ, where gⱼ are iid gaussian vectors on R ⁿ⁺¹, with high probability has δ-RIP from Kₛ into the m-dimensional Hamming cube. These bounds match the bounds for the linear δ-RIP given by x 1m[x,gⱼ] ⱼ₌₁ ᵐ, from the sparse vectors in R ⁿ into ℓ ¹. 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.