Paper Info
Title
eOMP: Finding Sparser Representation by Recursively Orthonormalizing the Remaining Atoms.
Abstract
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.
Year
Venue
Field
2015
CoRR
Matching pursuit,Signal processing,Residual,Discrete mathematics,Mathematical optimization,Neural coding,Sparse approximation,Algorithm,Greedy algorithm,Gaussian,Recursion,Mathematics
DocType
Volume
Citations 
Journal
abs/1502.03805
0
PageRank 
References 
Authors
0.34
2
2
Name
Order
Citations
PageRank
Yuanyi Xue1555.37
Wang Yao28511.45