The l1-synthesis and l1-analysis models recover structured signals from their undersampled measurements. The solution of the former model is often a sparse sum of dictionary atoms, and that of the latter model often 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 necessary and sufficient condition that guarantees the recovery to be unique and exact and that also guarantees the recovery is robust in presence of measurement noise. The condition is one-for-all in the sense that it applies to both of the l1-synthesis and l1-analysis models, and to both of their constrained and unconstrained formulations. Furthermore, a convex infinity-norm program is introduced for numerically verifying the condition. The comparison with related existing conditions are included.
Citation
Rice CAAM technical report 13-10