Fast OMP: Reformulating OMP via iteratively refining ℓ 2-norm solutions
Journal
2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP
Pages
189-192
Date Issued
2012-03
Author(s)
Abstract
Orthogonal matching pursuit (OMP) is a powerful greedy algorithm in compressed sensing for recovering sparse signals despite its high computational cost for solving large scale problems. Moreover, its theoretic performance analysis based on mutual incoherence property (MIP) is still not accurate enough. To overcome these difficulties, this paper proposes a fast OMP (FOMP) algorithm by reformulating OMP in terms of refining ℓ 2 -norm solutions in a greedy manner. ℓ 2 -norm solutions are known for being non-sparse, but we show that the ℓ 2 -norm solution associated with a greedy structure actually solves the sparse signal reconstruction problem well. We analyze exact recovery of FOMP via an order statistics probabilistic model and provide practical performance bounds.
Type
conference paper