Discrete optimization methods for group model selection in compressed sensing

In this article we study the problem of signal recovery for group models. More precisely for a given set of groups, each containing a small subset of indices, and for given linear sketches of the true signal vector which is known to be group-sparse in the sense that its support is contained in the u...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2021-11, Vol.190 (1-2), p.171-220
Main Authors: Bah, Bubacarr, Kurtz, Jannis, Schaudt, Oliver
Format: Article
Language:English
Subjects:
Algorithms
Benders decomposition
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Dynamic programming
Full Length Paper
Iterative methods
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Matrices (mathematics)
Numerical Analysis
Optimization
Projection
Rounding
Signal reconstruction
Sketches
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article we study the problem of signal recovery for group models. More precisely for a given set of groups, each containing a small subset of indices, and for given linear sketches of the true signal vector which is known to be group-sparse in the sense that its support is contained in the union of a small number of these groups, we study algorithms which successfully recover the true signal just by the knowledge of its linear sketches. We derive model projection complexity results and algorithms for more general group models than the state-of-the-art. We consider two versions of the classical iterative hard thresholding algorithm (IHT). The classical version iteratively calculates the exact projection of a vector onto the group model, while the approximate version (AM-IHT) uses a head- and a tail-approximation iteratively. We apply both variants to group models and analyse the two cases where the sensing matrix is a Gaussian matrix and a model expander matrix. To solve the exact projection problem on the group model, which is known to be equivalent to the maximum weight coverage problem, we use discrete optimization methods based on dynamic programming and Benders’ decomposition. The head- and tail-approximations are derived by a classical greedy-method and LP-rounding, respectively.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-020-01529-7