A null space analysis of the l(1)-synthesis method in dictionary-based compressed sensing

作者：Chen Xuemei^*; Wang Haichao; Wang Rongrong

来源：Applied and Computational Harmonic Analysis, 2014, 37(3): 492-515.

DOI：10.1016/j.acha.2014.01.006

• Compressed sensing
• Sparse representation
• Null space property
• Frame
• Redundant dictionary

An interesting topic in compressed sensing aims to recover signals with sparse representations in a dictionary. Recently the performance of the l(1)-analysis method has been a focus, while some fundamental problems for the l(1)-synthesis method are still unsolved. For example, what are the conditions for it to stably recover compressible signals under noise? Do coherent dictionaries allow the existence of sensing matrices that guarantee good performances of the l(1)-synthesis method? To answer these questions, we build up a framework for the l(1)-synthesis method. In particular, we propose a dictionary-based null space property (D-NSP) which, to the best of our knowledge, is the first sufficient and necessary condition for the success of l(1)-synthesis without measurement noise. With this new property, we show that when the dictionary D is full spark, it cannot be too coherent otherwise the l(1)-synthesis method fails for all sensing matrices. We also prove that in the real case, D-NSP is equivalent to the stability of l(1)-synthesis under noise. Published by Elsevier Inc.

• 出版日期2014-11