Optimization Online


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

Hui Zhang(hhuuii.zhang***at***gmail.com)
Ming Yan(yanm***at***ucla.edu)
Wotao Yin(wotao.yin***at***rice.edu)

Abstract: 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.

Keywords: exact recovery, robust recovery, l1-analysis, l1-synthesis, sparse optimization, compressive sensing

Category 1: Convex and Nonsmooth Optimization

Category 2: Applications -- Science and Engineering (Statistics )

Citation: Rice CAAM technical report 13-10

Download: [PDF]

Entry Submitted: 06/09/2013
Entry Accepted: 06/09/2013
Entry Last Modified: 06/09/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society