Outlier-Robust Greedy Pursuit Algorithms in <formula formulatype="inline"><tex Notation="TeX">ₚ</tex> </formula>-Space for Sparse Approximation

Greedy pursuit, which includes matching pursuit (MP) and orthogonal matching pursuit (OMP), is an efficient approach for sparse approximation. However, conventional greedy pursuit algorithms designed for inner product space are not robust against outliers. In this paper, we devise a new definition of correlation in lp-space with p > 0, called lp-correlation, and introduce the concept of orthogonality in lp-space. Based on the lp-correlation and lp-orthogonality, which are generalizations of the absolute inner product and orthogonality of inner product space, respectively, we develop three greedy pursuit algorithms, namely, lp-MP, lp-OMP, and weak lp-MP, for robust sparse approximation in the presence of outliers. The convergence of the three algorithms is proved. In particular, the lp-norm of the residual of each algorithm decays exponentially. It is revealed that the exponential decay factor in the worst case is related to the minimal lp-correlation of the residual and the dictionary. Numerical examples on sparse signal recovery and harmonic retrieval in impulsive noise demonstrate that the lp-greedy pursuit algorithms with are more outlier-resistant than their counterparts in inner product space.