Dictionary Preconditioning for Greedy Algorithms
- 15 April 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 56 (5) , 1994-2002
- https://doi.org/10.1109/tsp.2007.911494
Abstract
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.Keywords
This publication has 11 references indexed in Scilit:
- On the conditioning of random subdictionariesApplied and Computational Harmonic Analysis, 2008
- Average Performance Analysis for ThresholdingIEEE Signal Processing Letters, 2007
- MoTIF: An Efficient Algorithm for Learning Translation Invariant DictionariesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Designing structured tight frames via an alternating projection methodIEEE Transactions on Information Theory, 2005
- Greed is Good: Algorithmic Results for Sparse ApproximationIEEE Transactions on Information Theory, 2004
- Grassmannian frames with applications to coding and communicationApplied and Computational Harmonic Analysis, 2003
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimizationProceedings of the National Academy of Sciences, 2003
- Detection and estimation of superimposed signalsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Adaptive greedy approximationsConstructive Approximation, 1997
- Extension of the Pisarenko method to sparse linear arraysIEEE Transactions on Signal Processing, 1997