A totally unimodular view of structured sparsity

2014/11/07 by Marwa El Halabi, Volkan Cevher, Halabi, Marwa El +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Blind Source Separation Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1411.1990

openalex publication_date 2014/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• A Sparse-Group Lasso
• Provable Submodular Minimization using Wolfe's Algorithm

Cited by

• Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting

Related

• Structured sparsity through convex optimization
• Structured Sparsity: Discrete and Convex approaches
• Lower Bound Convex Programs for Exact Sparse Optimization
• A General Framework for Structured Sparsity via Proximal Optimization
• Simultaneously Structured Models with Application to Sparse and Low-rank\n Matrices