On the Lagrangian Biduality of Sparsity Minimization Problems

Details On the Lagrangian Biduality of Sparsity Minimization Problems On the Lagrangian Biduality of Sparsity Minimization Problems

2012-01-18

arxiv.org/abs/1201.3674v1

Computer Science

Computer Vision and Pattern Recognition

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Lagrangian Biduality of Sparsity Minimization Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Lagrangian Biduality of Sparsity Minimization Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Lagrangian Biduality of Sparsity Minimization Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-396100