Necessary and Sufficient Conditions of Solution Uniqueness in l(sub 1) Minimization (Preprint)
Abstract
This paper shows that the solutions to various convex l(sub 1) 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 l(sub 1) models that either minimize f(Ax-b) or impose the constraint f(Ax-b) < or = to sigma, where f is a strictly convex function. For these models, this paper proves that x* is the unique solution if and only if A(sub I) has full column rank and there exists y. 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 l(sub 1) models. The paper also discusses ways to recognize unique solutions and verify the uniqueness conditions numerically.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 2012
- Accession Number
- ADA580582
Entities
People
- Hui Zhang
- Lizhi Cheng
- Wotao Yin
Organizations
- Rice University