A nonconvex ADMM algorithm for group sparsity with sparse groups

TLDR

The authors develop an efficient algorithm to compute sparse representations with only a few nonzero groups. The method employs nonconvex optimization solved via an efficient ADMM algorithm that uses a novel shrinkage operator to jointly enforce sparsity and group sparsity. Experiments show that combining sparsity and group sparsity, and using nonconvex optimization, yields better signal reconstruction accuracy than either approach alone or convex optimization.

Abstract

We present an efficient algorithm for computing sparse representations whose nonzero coefficients can be divided into groups, few of which are nonzero. In addition to this group sparsity, we further impose that the nonzero groups themselves be sparse. We use a nonconvex optimization approach for this purpose, and use an efficient ADMM algorithm to solve the nonconvex problem. The efficiency comes from using a novel shrinkage operator, one that minimizes nonconvex penalty functions for enforcing sparsity and group sparsity simultaneously. Our numerical experiments show that combining sparsity and group sparsity improves signal reconstruction accuracy compared with either property alone. We also find that using nonconvex optimization significantly improves results in comparison with convex optimization.