On the Lagrangian biduality of sparsity minimization problems

We present a novel primal-dual analysis on a class of NP-hard sparsity minimization problems to provide new interpretations for their well known convex relaxations. 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 ℓ₀-minimization problem is ℓ₁-minimization; and the bidual of ℓ_0,1-minimization for enforcing group sparsity on structured data is ℓ_1,∞-minimization problem. Intuitions from the bidual-based relaxation are used to introduce a new family of relaxations for the group sparsity minimization problem.