2019/04/02 by Bubacarr Bah, Bah, Bubacarr, Jannis Kurtz +3 · 1 citation
Computer Science · Engineering · Medicine · #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Medical Imaging Techniques and Applications #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1904.01542
openalex publication_date 2019/04/02 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
In this article we study the problem of signal recovery for group models.\nMore precisely for a given set of groups, each containing a small subset of\nindices, and for given linear sketches of the true signal vector which is known\nto be group-sparse in the sense that its support is contained in the union of a\nsmall number of these groups, we study algorithms which successfully recover\nthe true signal just by the knowledge of its linear sketches. We derive model\nprojection complexity results and algorithms for more general group models than\nthe state-of-the-art. We consider two versions of the classical Iterative Hard\nThresholding algorithm (IHT). The classical version iteratively calculates the\nexact projection of a vector onto the group model, while the approximate\nversion (AM-IHT) uses a head- and a tail-approximation iteratively. We apply\nboth variants to group models and analyse the two cases where the sensing\nmatrix is a Gaussian matrix and a model expander matrix.\n To solve the exact projection problem on the group model, which is known to\nbe equivalent to the maximum weight coverage problem, we use discrete\noptimization methods based on dynamic programming and Benders' Decomposition.\nThe head- and tail-approximations are derived by a classical greedy-method and\nLP-rounding, respectively.\n