  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 $\ell_0$-minimization problem is the
$\ell_1$-minimization problem; and the bidual of the $\ell_{0,1}$-minimization
problem for enforcing group sparsity on structured data is the
$\ell_{1,\infty}$-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.
