Dictionary Preconditioning for Greedy Algorithms
Dictionary Preconditioning for Greedy Algorithms
复制标题
DOI：
10.1109/tsp.2007.911494
复制
发表时间：
2008-05
影响因子：
5.4
通讯作者：
Karin Schnass;P. Vandergheynst
中科院分区：
文献类型：
--
作者：
Karin Schnass;P. Vandergheynst
本文介绍了感知词典的概念。它提出了一种改变贪婪算法，如阈值或（正交）匹配追求，提高了他们的性能，在冗余字典中找到稀疏信号表示，同时保持相同的复杂性。这些算法可以分为一个传感和重建步骤，前者将无法识别正确的原子，如果字典的累积相干性太高。因此，我们通过引入特殊的感测字典来修改感测步骤。然后，通过交叉累积相干性来确定分量的正确选择，交叉累积相干性可以显著低于累积相干性。最后，我们比较了阈值法和OMP算法在原始算法和改进算法下的性能。
This paper introduces the concept of sensing dictionaries. It presents an alteration of greedy algorithms like thresholding or (orthogonal) matching pursuit which improves their performance in finding sparse signal representations in redundant dictionaries while maintaining the same complexity. These algorithms can be split into a sensing and a reconstruction step, and the former will fail to identify correct atoms if the cumulative coherence of the dictionary is too high. We thus modify the sensing step by introducing a special sensing dictionary. The correct selection of components is then determined by the cross cumulative coherence which can be considerably lower than the cumulative coherence. We characterize the optimal sensing matrix and develop a constructive method to approximate it. Finally, we compare the performance of thresholding and OMP using the original and modified algorithms.