Ratio and difference of $l_1$ and $l_2$ norms and sparse representation with coherent dictionaries

The ratio of $l_1$ and $l_2$ norms has been used empirically to enforce sparsity of scale invariant solutions in non-convex blind source separation problems such as nonnegative matrix factorization and blind deblurring. In this paper, we study the mathematical theory of the sparsity promoting properties of the ratio metric in the context of basis pursuit via over-complete dictionaries. Due to the coherence in the dictionary elements, convex relaxations such as $l_1$ minimization or non-negative least squares may not find the sparsest solutions. We found sufficient conditions on the nonnegative solutions of the basis pursuit problem so that the sparsest solutions can be recovered exactly by minimizing the nonconvex ratio penalty. Similar results hold for the difference of $l_1$ and $l_2$ norms. In the unconstrained form of the basis pursuit problem, these penalties are robust and help select sparse if not the sparsest solutions. We give analytical and numerical examples and introduce sequentially convex algorithms to illustrate how the ratio and difference penalties are computed to produce both stable and sparse solutions.

Keywords

$l_1$ and $l_2$ norms, ratio and difference, coherent dictionary, sparse representation

2010 Mathematics Subject Classification

90C25, 90C26, 94A12, 94A15

Full Text (PDF format)

Published 31 October 2014