Parameter Choices for Sparse Regularization with the ${\ell }_1$ Norm

Abstract

We consider a regularization problem whose objective function consists of a convex fidelity term and a regularization term determined by the ${\ell }_1$ norm composed with a linear transform. Empirical results show that the regularization with the ${\ell }_1$ norm can promote sparsity of a regularized solution. It is the goal of this paper 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 fidelity term has a special structure and the transform matrix coincides with a identity matrix, 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. We study choices of the regularization parameter so that the regularization term alleviates the ill-posedness and promote sparsity of the resulting regularized solution. Numerical experiments demonstrate that choices of the regularization parameters can balance the sparsity of the solutions of the regularization problem and its approximation to the minimizer of the fidelity function.

References in corpus (12)

• On the "degrees of freedom" of the lasso
• The solution path of the generalized lasso
• Proximal Methods for Hierarchical Sparse Coding
• Degrees of freedom in lasso problems
• Sparse Regularization with $l^q$ Penalty Term
• Convergence rates and source conditions for Tikhonov regularization with sparsity constraints
• Reproducing Kernel Banach Spaces with the l1 Norm
• Efficient First Order Methods for Linear Composite Regularizers
• Tikhonov regularization in Hilbert scales under conditional stability assumptions
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Supervised Learning of Sparsity-Promoting Regularizers for Denoising
• Representer Theorems in Banach Spaces: Minimum Norm Interpolation, Regularized Learning and Semi-Discrete Inverse Problems