Matching Pursuit LASSO for Sparse Recovery over Big Dictionary
Introduction:
Large-scale sparse recovery (SR) by solving $\ell_1$-norm relaxations over Big Dictionary is a very challenging task. Plenty of greedy methods have therefore been proposed to address big SR problems, but most of them require restricted conditions for the convergence. Moreover, it is non-trivial for them to incorporate the $\ell_1$-norm regularization that is required for robust signal recovery. We address these issues in this paper by proposing a Matching Pursuit LASSO (MPL) algorithm, based on a novel quadratically constrained linear program (QCLP) formulation, which has several advantages over existing methods. Firstly, it is guaranteed to converge to a global solution. Secondly, it greatly reduces the computation cost of the
$\ell_1$-norm methods over Big Dictionaries. Finally, the exact sparse recovery condition of MPL is also investigated.
Large-scale sparse recovery (SR) by solving $\ell_1$-norm relaxations over Big Dictionary is a very challenging task. Plenty of greedy methods have therefore been proposed to address big SR problems, but most of them require restricted conditions for the convergence. Moreover, it is non-trivial for them to incorporate the $\ell_1$-norm regularization that is required for robust signal recovery. We address these issues in this paper by proposing a Matching Pursuit LASSO (MPL) algorithm, based on a novel quadratically constrained linear program (QCLP) formulation, which has several advantages over existing methods. Firstly, it is guaranteed to converge to a global solution. Secondly, it greatly reduces the computation cost of the
$\ell_1$-norm methods over Big Dictionaries. Finally, the exact sparse recovery condition of MPL is also investigated.
The C++ source codes of MPL are available HERE
Please cite the following papers if you find the codes are useful:
Mingkui Tan, Ivor W. Tsang, Li Wang. "Matching Pursuit LASSO Part I: Sparse Recovery over Big Dictionary", IEEE Transactions on Signal Processing, 63(3), 2015.
Mingkui Tan, Ivor W. Tsang, Li Wang. ``Sparse Recovery over Big Dictionary Part II: Batch Mode Matching Pursuit LASSO and Applications", IEEE Transactions on Signal Processing, 63(3), 2015.
Mingkui Tan, Ivor W. Tsang, Li Wang. "Matching Pursuit LASSO Part I: Sparse Recovery over Big Dictionary", IEEE Transactions on Signal Processing, 63(3), 2015.
Mingkui Tan, Ivor W. Tsang, Li Wang. ``Sparse Recovery over Big Dictionary Part II: Batch Mode Matching Pursuit LASSO and Applications", IEEE Transactions on Signal Processing, 63(3), 2015.
