Abstract
Sparse reconstruction approaches using the re-weighted ℓ1-penalty have been shown, both empirically and theoretically, to provide a significant improvement in recovering sparse signals in comparison to the ℓ1-relaxation. However, numerical optimization of such penalties involves solving problems with ℓ1-norms in the objective many times. Using the direct link of reweighted ℓ1-penalties to the concave log-regularizer for sparsity, we derive a simple proximal-like algorithm for the log-regularized formulation. The proximal splitting step of the algorithm has a closed form solution, and we call the algorithm log-thresholding in analogy to soft thresholding for the ℓ1-penalty. We establish convergence results, and demonstrate that log-thresholding provides more accurate sparse reconstructions compared to both soft and hard thresholding. Furthermore, the approach can be directly extended to optimization over matrices with penalty for rank (i.e. the nuclear norm penalty and its re-weighted version), where we suggest a singular-value log-thresholding approach. © 2014 IEEE.