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
    0 references
    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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references