On the Lagrangian biduality of sparsity minimization problems

Recent results in Compressive Sensing have shown that, under certain conditions, the solution to an underdetermined system of linear equations with sparsity-based regularization can be accurately recovered by solving convex relaxations of the original problem. In this work, we present a novel primal-dual analysis on a class of sparsity minimization problems. We show that the Lagrangian bidual (i.e., the Lagrangian dual of the Lagrangian dual) of the sparsity minimization problems can be used to derive interesting convex relaxations: the bidual of the ℓ0-minimization problem is the ℓ1-minimization problem; and the bidual of the ℓ0,1-minimization problem for enforcing group sparsity on structured data is the ℓ1,∞-minimization problem. The analysis provides a means to compute per-instance non-trivial lower bounds on the (group) sparsity of the desired solutions. In a real-world application, the bidual relaxation improves the performance of a sparsity-based classification framework applied to robust face recognition.This research was supported by ARO MURI W911NF-06-1-0076, ARL MAST-CTA W911NF-08-2-0004, NSF CNS-0931805, NSF CNS-0941463 and NSF grant 0834470. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute for Government purposes notwithstanding any copyright notation herein. (W911NF-06-1-0076 - ARO MURI; W911NF-08-2-0004 - ARL MAST-CTA; CNS-0931805 - NSF; CNS-0941463 - NSF; 0834470 - NSF