2015/12/21 by Dmitriy Bilyk, Michael T. Lacey, Bilyk, Dmitriy +1 · 1 citation
Computer Science · Mathematics · #Classical Analysis and ODEs (math.CA) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.IT #math.CA #math.IT
paper · pdf · doi:10.48550/arxiv.1512.06697
22 pages, 2 figures
arxiv created 2015/12/21 · arxiv updated 2015/12/22
We obtain mproved bounds for one bit sensing. For instance, let Ks 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 ↦ [ sgn ⟨ x,gj ⟩ ] j=1 m, where gj are iid gaussian vectors on \mathbb R n+1, with high probability has δ-RIP from Ks into the m-dimensional Hamming cube. These bounds match the bounds for the linear δ-RIP given by x ↦ \frac 1m[⟨ x,gj ⟩ ] j=1 m , from the sparse vectors in \mathbb R n into ℓ 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.