FAST OMP: REFORMULATING OMP VIA ITERATIVELY REFINING ℓ2-NORM SOLUTIONS

Orthogonal matching pursuit (OMP) is a powerful greedy al-gorithm 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 actu-ally solves the sparse signal reconstruction problem well. We analyze exact recovery of FOMP via an order statistics prob-abilistic model and provide practical performance bounds