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

H. Zhang, M. Yan, and W. Yin

To appear in Advances in Computational Mathematics

Overview

The ell_1-synthesis and ell_1-analysis models recover structured signals from their undersampled measurements. The solution of the former mode is often 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 presence of measurement noise, to be robust. The condition is one-for-all in the sense that it applies to both of the ell_1-synthesis and ell_1-analysis models, to both of their constrained and unconstrained formulations, and to both the exact recovery and robust recovery cases. Furthermore, a convex infinity-norm program is introduced for numerically verifying the condition. A comprehensive comparison with related existing conditions are included.

Citation

H. Zhang, M. Yan, and W. Yin, One condition for solution uniqueness and robustness of both ell_1-synthesis and ell_1-analysis minimizations, Advances in Computational Mathematics, online first, 2016. DOI: 10.1007/s10444-016-9467-y


« Back