One condition for all: solution uniqueness and robustness of -synthesis and -analysis minimizations

Submitted for publication

• Technical report

Overview

The -synthesis and -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 -synthesis and -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

H. Zhang, M. Yan, and W. Yin, One condition for all: solution uniqueness and robustness of -synthesis and -analysis minimizations, Rice CAAM technical report 13-10, 2013.