MEGS: A Penalty for Mutually Exclusive Group Sparsity

Abstract

Penalty functions or regularization terms that promote structured solutions to optimization problems are of great interest in many fields. We introduce MEGS, a nonconvex structured sparsity penalty that promotes mutual exclusivity between components in solutions to optimization problems. This enforces, or promotes, 1-sparsity within arbitrary overlapping groups in a vector. The mutual exclusivity structure is represented by a matrix ${\bf {S}}$. We discuss the design of ${\bf {S}}$ from engineering principles and show example use cases including the modeling of occlusions in 3D imaging and a total variation variant with uses in image restoration. We also demonstrate synergy between MEGS and other regularizers and propose an algorithm to efficiently solve problems regularized or constrained by MEGS.

Keywords

• Sparsity
• structured sparsity
• group sparsity
• regularization
• inverse problems