Sparsity via Sparse Group $k$-max Regularization
This is an incremental improvement for sparsity regularization in linear inverse problems, such as signal processing or machine learning.
The paper tackles the NP-hard linear inverse problem with sparsity constraints by proposing a sparse group k-max regularization to enhance group-wise and in-group sparsity without magnitude restraints, and numerical experiments verify its effectiveness.
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.