Outlier-Robust Greedy Pursuit Algorithms in $\ell _{p}$ -Space for Sparse Approximation
Authors:
- 7 September 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 64 (1) , 60-75
Abstract
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.Keywords
Funding Information
- CityU
This publication has 46 references indexed in Scilit:
- Reconstruction of Sparse Signals From $\ell_1$ Dimensionality-Reduced Cauchy Random ProjectionsIEEE Transactions on Signal Processing, 2012
- A note on the complexity of L p minimizationMathematical Programming, 2011
- Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching PursuitFoundations of Computational Mathematics, 2008
- A Maximum Likelihood Approach to Least Absolute Deviation RegressionEURASIP Journal on Advances in Signal Processing, 2004
- Median power and median correlation theoryIEEE Transactions on Signal Processing, 2002
- Uncertainty principles and ideal atomic decompositionIEEE Transactions on Information Theory, 2001
- Fast algorithms for weighted myriad computation by fixed-point searchIEEE Transactions on Signal Processing, 2000
- Non-Gaussian noise models in signal processing for telecommunications: new methods an results for class A and class B noise modelsIEEE Transactions on Information Theory, 1999
- Joint estimation of time delay and frequency delay in impulsive noise using fractional lower order statisticsIEEE Transactions on Signal Processing, 1996
- Matching pursuits with time-frequency dictionariesIEEE Transactions on Signal Processing, 1993