Computing Sparse Representation in a Highly Coherent Dictionary Based on Difference of \(L_1\) and \(L_2\)

We study analytical and numerical properties of the \(L_1-L_2\) minimization problem for sparse representation of a signal over a highly coherent dictionary. Though the \(L_1-L_2\) metric is non-convex, it is Lipschitz continuous. The difference of convex algorithm (DCA) is readily applicable for computing the sparse representation coefficients. The \(L_1\) minimization appears as an initialization step of DCA. We further integrate DCA with a non-standard simulated annealing methodology to approximate globally sparse solutions. Non-Gaussian random perturbations are more effective than standard Gaussian perturbations for improving sparsity of solutions. In numerical experiments, we conduct an extensive comparison among sparse penalties such as \(L_0, L_1, L_p\) for \(p\in (0,1)\) based on data from three specific applications (over-sampled discreet cosine basis, differential absorption optical spectroscopy, and image denoising) where highly coherent dictionaries arise. We find numerically that the \(L_1-L_2\) minimization persistently produces better results than \(L_1\) minimization, especially when the sensing matrix is ill-conditioned. In addition, the DCA method outperforms many existing algorithms for other nonconvex metrics.