Exact reconstruction of sparse signals via generalized orthogonal matching pursuit

As a greedy algorithm recovering sparse signal from compressed measurements, orthogonal matching pursuit (OMP) algorithm have received much attention in recent years. The OMP selects at each step one index corresponding to the column that is most correlated with the current residual. In this paper, we present an extension of OMP for pursuing efficiency of the index selection. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple (N ∈ ℕ) columns are identified per step. We derive rigorous condition demonstrating that exact reconstruction of K-sparse (K > 1) signals is guaranteed for the gOMP algorithm if the sensing matrix satisfies the restricted isometric property (RIP) of order NK with isometric constant δ _NK < √N/√K + 2 √N. In addition, empirical results demonstrate that the gOMP algorithm has very competitive reconstruction performance that is comparable to the ℓ ₁-minimization technique.