Covering point-sets with parallel hyperplanes and sparse signal recovery (Q2689251)

An \(n\times d\) matrix \(A\) is called a sensing matrix for \(l\)-sparse signals if no \(l\) columns of \(A\) are linearly dependent. For applications in compressive sensing theory it is important to find integer sensing matrices with large \(d\) and small \(|A|=\max |a_ij|\). In this paper it is shown that for all \(n\geq n_0\) there exist \(n\times d\) integer sensing matrices \(A\) for \(l\)-sparse vectors, \(1\leq l\leq n-1\) such that \(|A|=2\) and \(d\geq (\frac{n+2}{2})^{1+2/(3l-2)}\). The construction comes from particular sets of difference vectors of pointsets in \(\mathbb{R}^n\) that cannot be covered by few parallel hyperplanes. This is related with Tarski's problem about covering of convex bodies by strips between parallel hyperplanes.