Outlier-Robust Greedy Pursuit Algorithms in \ell p-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 \ell p-space with p>0, called \ell p-correlation, and introduce the concept of orthogonality in \ell p-space. Based on the \ell p-correlation and \ell p-orthogonality, which are generalizations of the absolute inner product and orthogonality of inner product space, respectively, we develop three greedy pursuit algorithms, namely, \ell p-MP, \ell p-OMP, and weak \ell p-MP, for robust sparse approximation in the presence of outliers. The convergence of the three algorithms is proved. In particular, the \ell p-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 \ell p-correlation of the residual and the dictionary. Numerical examples on sparse signal recovery and harmonic retrieval in impulsive noise demonstrate that the \ell p-greedy pursuit algorithms with 0< p< 2 are more outlier-resistant than their counterparts in inner product space. [ABSTRACT FROM PUBLISHER]