Matching pursuit LASSO part I: Sparse recovery over big dictionary

Publication Type:
Journal Article
IEEE Transactions on Signal Processing, 2015, 63 (3), pp. 727 - 741
Issue Date:
Filename Description Size
06994869.pdfPublished Version3.57 MB
Adobe PDF
Full metadata record
© 2015 IEEE. Large-scale sparse recovery (SR) by solving ℓ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 ℓ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 ℓ1-norm methods over Big Dictionaries. Lastly, the exact sparse recovery condition of MPL is also investigated.
Please use this identifier to cite or link to this item: