Group Sparse Optimization via lp,q Regularization

Yaohua Hu, Chong Li, Kaiwen Meng, Jing Qin, Xiaoqi Yang.

Year: 2017, Volume: 18, Issue: 30, Pages: 1−52


In this paper, we investigate a group sparse optimization problem via $\ell_{p,q}$ regularization in three aspects: theory, algorithm and application. In the theoretical aspect, by introducing a notion of group restricted eigenvalue condition, we establish an oracle property and a global recovery bound of order $\mathcal{O}(\lambda^\frac{2}{2-q})$ for any point in a level set of the $\ell_{p,q}$ regularization problem, and by virtue of modern variational analysis techniques, we also provide a local analysis of recovery bound of order $\mathcal{O}(\lambda^2)$ for a path of local minima. In the algorithmic aspect, we apply the well-known proximal gradient method to solve the $\ell_{p,q}$ regularization problems, either by analytically solving some specific $\ell_{p,q}$ regularization subproblems, or by using the Newton method to solve general $\ell_{p,q}$ regularization subproblems. In particular, we establish a local linear convergence rate of the proximal gradient method for solving the $\ell_{1,q}$ regularization problem under some mild conditions and by first proving a second-order growth condition. As a consequence, the local linear convergence rate of proximal gradient method for solving the usual $\ell_{q}$ regularization problem ($0<q<1$) is obtained. Finally in the aspect of application, we present some numerical results on both the simulated data and the real data in gene transcriptional regulation.