Necessary and Sufficient Conditions of Solution Uniqueness in l1 Minimizationms

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|