  Greedy algorithms for minimizing L0-norm of sparse decomposition have
profound application impact on many signal processing problems. In the sparse
coding setup, given the observations $\mathrm{y}$ and the redundant dictionary
$\mathbf{\Phi}$, one would seek the most sparse coefficient (signal)
$\mathrm{x}$ with a constraint on approximation fidelity. In this work, we
propose a greedy algorithm based on the classic orthogonal matching pursuit
(OMP) with improved sparsity on $\mathrm{x}$ and better recovery rate, which we
name as eOMP. The key ingredient of the eOMP is recursively performing one-step
orthonormalization on the remaining atoms, and evaluating correlations between
residual and orthonormalized atoms. We show a proof that the proposed eOMP
guarantees to maximize the residual reduction at each iteration. Through
extensive simulations, we show the proposed algorithm has better exact recovery
rate on i.i.d. Gaussian ensembles with Gaussian signals, and more importantly
yields smaller L0-norm under the same approximation fidelity compared to the
original OMP, for both synthetic and practical scenarios. The complexity
analysis and real running time result also show a manageable complexity
increase over the original OMP. We claim that the proposed algorithm has better
practical perspective for finding more sparse representations than existing
greedy algorithms.
