Show simple item record

dc.contributor.authorZhang, Hui
Yin, Wotao
Cheng, Lizhi
dc.date.accessioned 2018-06-19T17:48:01Z
dc.date.available 2018-06-19T17:48:01Z
dc.date.issued 2012-08
dc.identifier.citation Zhang, Hui, Yin, Wotao and Cheng, Lizhi. "Necessary and Sufficient Conditions of Solution Uniqueness in l1 Minimizationms." (2012) https://hdl.handle.net/1911/102207.
dc.identifier.urihttps://hdl.handle.net/1911/102207
dc.description.abstract This paper shows that the solutions to various convex l1 minimization problems are unique if and only if a common set of conditions are satisfied. This result applies broadly to the basis pursuit model, basis pursuit denoising model, Lasso model, as well as other l1 models that either minimize f(Ax-b) or impose the constraint f(Ax-b) <= sigma, where f is a strictly convex function. For these models, this paper proves that, given a solution x* and defining I=supp(x*) and s=sign(x*I), x is the unique solution if and only if AI has full column rank and there exists y such that A'Iy=s and |a'iy|<1 for i not in I. This condition is previously known to be sufficient for the basis pursuit model to have a unique solution supported on I. Indeed, it is also necessary, and applies to a variety of other l1 models. The paper also discusses ways to recognize unique solutions and verify the uniqueness conditions numerically.
dc.format.extent 11 pp
dc.title Necessary and Sufficient Conditions of Solution Uniqueness in l1 Minimizationms
dc.type Technical report
dc.date.note August 2012
dc.identifier.digital TR12-18
dc.type.dcmi Text


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record