Stable recovery of sparse overcomplete representations in the presence of noise
Stable recovery of sparse overcomplete representations in the presence of noise
复制标题
DOI：
10.1109/tit.2005.860430
复制
发表时间：
2006-01-01
影响因子：
2.5
通讯作者：
Temlyakov, VN
中科院分区：
文献类型：
--
作者：
Donoho, DL;Elad, M;Temlyakov, VN
在信号处理理论中，过完备表示引起了人们的兴趣，特别是因为它们有可能产生信号的稀疏表示。然而，通常情况下，在存在噪声的情况下，寻找稀疏表示的问题必须是不稳定的。本文建立了在充分稀疏性和超完备系统的有利结构相结合的情况下稳定恢复的可能性。考虑到具有足够稀疏表示的理想基础信号，假设只能观察到它的噪声版本。进一步假设过完备系统是非相干的，证明了对有噪声数据的最优稀疏近似与对理想无噪声信号的最优稀疏分解至多不同于噪声电平的常数倍。由于这种最优稀疏性方法需要大量的(组合)计算，因此考虑了近似算法。结果表明，使用基算法和匹配追踪算法也可以获得类似的稳定性。此外，结果表明，这些方法导致了对仅包含出现在理想无噪声稀疏信号的唯一最稀疏表示中的项的有噪数据的稀疏逼近。
Overcomplete representations are attracting interest in signal processing theory, particularly due to their potential to generate sparse representations of signals. However, in general, the problem of finding sparse representations must be unstable in the presence of noise. This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system. Considering an ideal underlying signal that has a sufficiently sparse representation, it is assumed that only a noisy version of it can be observed. Assuming further that the overcomplete system is incoherent, it is shown that the optimally sparse approximation to the noisy data differs from the optimally sparse decomposition of the ideal noiseless signal by at most a constant multiple of the noise level. As this optimal-sparsity method requires heavy (combinatorial) computational effort, approximation algorithms are considered. It is shown that similar stability is also available using the basis and the matching pursuit algorithms. Furthermore, it is shown that these methods result in sparse approximation of the noisy data that contains only terms also appearing in the unique sparsest representation of the ideal noiseless sparse signal.