Paper Info
Title
Ratio And Difference Of L(1) And L(2) Norms And Sparse Representation With Coherent Dictionaries
Abstract
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.
Year
DOI
Venue
2014
10.4310/CIS.2014.v14.n2.a2
COMMUNICATIONS IN INFORMATION AND SYSTEMS
Keywords
DocType
Volume
l(1) and l(2) norms, ratio and difference, coherent dictionary, sparse representation
Journal
14
Issue
ISSN
Citations 
2
1526-7555
2
PageRank 
References 
Authors
0.38
0
3
Name
Order
Citations
PageRank
Penghang Yin1609.03
Ernie Esser228610.74
Jack Xin321225.49