Optimization Online


Group Sparse Optimization by Alternating Direction Method

Wei Deng(wei.deng***at***rice.edu)
Wotao Yin(wotao.yin***at***rice.edu)
Yin Zhang(yzhang***at***rice.edu)

Abstract: This paper proposes efficient algorithms for group sparse optimization with mixed L21-regularization, which arises from the reconstruction of group sparse signals in compressive sensing, and the group Lasso problem in statistics and machine learning. It is known that encoding the group information in addition to sparsity will lead to better signal recovery/feature selection. The L21-regularization promotes group sparsity, but the resulting problem, due to the mixed-norm structure and possible grouping irregularity, is considered more difficult to solve than the conventional L1-regularized problem. Our approach is based on a variable splitting strategy and the classic alternating direction method (ADM). Two algorithms are presented, one derived from the primal and the other from the dual of the L21-regularized problem. The convergence of the proposed algorithms is guaranteed by the existing ADM theory. General group configurations such as overlapping groups and incomplete covers can be easily handled by our approach. Computational results show that on random problems the proposed ADM algorithms exhibit good efficiency, and strong stability and robustness.

Keywords: group sparsity, joint sparsity, mixed norm, compressive sensing, group Lasso, alternating direction method, augmented Lagrangian

Category 1: Convex and Nonsmooth Optimization

Category 2: Applications -- Science and Engineering

Citation: Technical Report TR11-06, Department of Computational and Applied Mathematics, Rice University, 2011

Download: [PDF]

Entry Submitted: 04/22/2011
Entry Accepted: 04/22/2011
Entry Last Modified: 04/22/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society