Sparsity via Sparse Group $k$-max Regularization
Qinghua Tao Xiangming Xi Jun Xu Johan A. K. Suykens
For the linear inverse problem with sparsity constraints, the $l_0$
regularized problem is NP-hard, and existing approaches either utilize greedy
algorithms to find almost-optimal solutions or to approximate the $l_0$
regularization with its convex counterparts. In this paper, we propose a novel
and concise regularization, namely the sparse group $k$-max regularization,
which can not only simultaneously enhance the group-wise and in-group sparsity,
but also casts no additional restraints on the magnitude of variables in each
group, which is especially important for variables at different scales, so that
it approximate the $l_0$ norm more closely. We also establish an iterative soft
thresholding algorithm with local optimality conditions and complexity analysis
provided. Through numerical experiments on both synthetic and real-world
datasets, we verify the effectiveness and flexibility of the proposed method.