A totally unimodular view of structured sparsity

This paper describes a simple framework for structured sparse recovery based on convex op-timization. We show that many interesting struc-tured sparsity models can be naturally repre-sented by linear matrix inequalities on the sup-port of the unknown parameters, where the con-straint matrix has a totally unimodular (TU) structure. For such structured models, tight con-vex relaxations can be obtained in polynomial time via linear programming. Our modeling framework unifies the prevalent structured spar-sity norms in the literature, introduces new in-teresting ones, and renders their tightness and tractability arguments transparent.