Parameter choices for sparse regularization with the l1 norm

We consider a regularization problem whose objective function consists of a convex fidelity term and a regularization term determined by the 21 norm com-posed with a linear transform. Empirical results show that the regularization with the 21 norm can promote sparsity of a regularized solution. The goal of this paper is to understand theoretically the effect of the regularization parameter on the sparsity of the regularized solutions. We establish a characterization of the sparsity under the transform matrix of the solution. When the objective function is block-separable or an error bound of the regularized solution to a known function is available, the resulting characterization can be taken as a regularization parameter choice strategy with which the regularization problem has a solution having a sparsity of a certain level. When the objective function is not block-separable, we propose an iterative algorithm which simultaneously determines the regularization parameter and its corresponding solution with a prescribed sparsity level. Moreover, we study choices of the regularization parameter so that the regularization term can alleviate the ill-posedness and promote sparsity of the resulting regularized solution. Numerical experiments demonstrate that the proposed algorithm is effective and efficient, and the choices of the regularization parameters can balance the sparsity of the regu-larized solution and its approximation to the minimizer of the fidelity function.

Automated summary

This paper studies a regularization problem that combines a convex fidelity term and a regularization term based on the 21 norm and linear transform. The empirical results demonstrate that the regularization with the 21 norm promotes sparsity in the solution. The main goal of this paper is to theoretically understand the impact of the regularization parameter on the sparsity of the solution. The paper establishes a characterization of the sparsity under the transform matrix of the solution and proposes iterative algorithms for determining the regularization parameter and its corresponding solution with a prescribed sparsity level.