Group-based sparsity models are proven instrumental in linear regression
problems for recovering signals from much fewer measurements than standard
compressive sensing. A second promise of these models is to lead to
"interpretable" signals for which we identify its constituent groups. While
model identification can aid in signal recovery, we show that, in general,
group
based definitions of interpretability lead to NP-Hard problems, such as
weighted
max cover problem. Instead, leveraging a graph-based understanding of group
models, we describe group models which not only lead to interpretable
solutions
but also enable correct model identification in polynomial time. We also
consider several discrete relaxations based on Total unimodularity.