One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations

The ? ₁-synthesis model and the ? ₁-analysis model recover structured signals from their undersampled measurements. The solution of the former is a sparse sum of dictionary atoms, and that of the latter makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We answer the question with a condition that is both necessary and sufficient to guarantee the recovery to be unique and exact and, in the presence of measurement noise, to be robust. The condition is one–for–all in the sense that it applies to both the ? ₁-synthesis and ? ₁-analysis models, to both constrained and unconstrained formulations, and to both the exact recovery and robust recovery cases. Furthermore, a convex infinity–norm optimization problem is introduced for numerically verifying the condition. A comprehensive comparison with related existing conditions is included.