Fast OMP: Reformulating OMP via iteratively refining ℓ2-norm solutions

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 ℓ₂-norm solutions in a greedy manner. ℓ₂-norm solutions are known for being non-sparse, but we show that the ℓ₂-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.