Fast Non-Negative Orthogonal Matching Pursuit

Research output: Contribution to journalArticlepeer-review

Abstract

One of the important classes of sparse signals is the non-negative signals. Many algorithms have already been proposed to recover such non-negative representations, where greedy and convex relaxed algorithms are among the most popular methods. The greedy techniques have been modified to incorporate the non-negativity of the representations. One such modification has been proposed for Orthogonal Matching Pursuit (OMP), which first chooses positive coefficients and uses a non-negative optimisation technique as a replacement for the orthogonal projection onto the selected support. Beside the extra computational costs of the optimisation program, it does not benefit from the fast implementation techniques of OMP. These fast implementations are based on the matrix factorisations. We here first investigate the problem of positive representation, using pursuit algorithms. We will then describe a new implementation, which can fully incorporate the positivity constraint of the coefficients, throughout the selection stage of the algorithm. As a result, we present a novel fast implementation of the Non-Negative OMP, which is based on the QR decomposition and an iterative coefficients update. We will empirically show that such a modification can easily accelerate the implementation by a factor of ten in a reasonable size problem.

Original languageEnglish
Pages (from-to)1229-1233
Number of pages5
JournalIEEE Signal Processing Letters
Volume22
Issue number9
Early online date16 Jan 2015
DOIs
Publication statusPublished - 30 Sep 2015

Keywords

  • Matching Pursuit
  • non-negative least square and spectral decomposition
  • non-negative sparse approximations
  • orthogonal matching pursuit
  • QR matrix factorisation
  • LEAST-SQUARES

Cite this