A totally unimodular view of structured sparsity
This provides a unified and tractable approach to structured sparsity for machine learning and signal processing applications, though it appears incremental as it builds on existing convex optimization methods.
The paper tackles structured sparse recovery by showing that many structured sparsity models can be represented using totally unimodular matrices, enabling tight convex relaxations via linear programming in polynomial time. This framework unifies existing norms, introduces new ones, and makes their tightness and tractability transparent.
This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameters, where the constraint matrix has a totally unimodular (TU) structure. For such structured models, tight convex relaxations can be obtained in polynomial time via linear programming. Our modeling framework unifies the prevalent structured sparsity norms in the literature, introduces new interesting ones, and renders their tightness and tractability arguments transparent.