Covering point-sets with parallel hyperplanes and sparse signal recovery (Q2689251)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Covering point-sets with parallel hyperplanes and sparse signal recovery |
scientific article |
Statements
Covering point-sets with parallel hyperplanes and sparse signal recovery (English)
0 references
9 March 2023
0 references
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.
0 references
covering
0 references
hyperplane
0 references
integer cube
0 references
sensing matrix
0 references
sparse recovery
0 references
Tarski's plank problem
0 references