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

详细信息    查看全文

• 作者：Hui Zhang ; Ming Yan ; Wotao Yin
• 关键词：Exact recovery ; Robust recovery ; ℓ1 ; analysis ; ℓ1 ; synthesis ; Sparse optimization ; Compressive sensing
• 刊名：Advances in Computational Mathematics
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：42
• 期：6
• 页码：1381-1399
• 全文大小：342 KB
• 刊物类别：Computer Science
• 刊物主题：Numeric Computing
  Calculus of Variations and Optimal Control
  Mathematics
  Algebra
  Theory of Computation
  
• 出版者：Springer U.S.
• ISSN：1572-9044
• 卷排序：42

文摘

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.