Fast non-negative orthogonal least squares

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

An important class of sparse signals is the non-negative sparse signals. While numerous greedy techniques have been introduced for low-complexity sparse approximations, there are few non-negative versions. Among such a large class of greedy techniques, one successful method, which is called the Orthogonal Least Squares (OLS) algorithm, is based on the maximum residual energy reduction at each iteration. However, the basic implementation of the OLS is computationally slow. The OLS algorithm has a fast implementation based on the QR matrix factorisation of the dictionary. The extension of such technique to the non-negative domain is possible. In this paper, we present a fast implementation of the non-negative OLS (NNOLS). The computational complexity of the algorithm is compared with the basic implementation, where the new method is faster with two orders of magnitude. We also show that, if the basic implementation of NNOLS is not computationally feasible for moderate size problems, the proposed method is tractable. We also show that the proposed algorithm is even faster than an approximate implementation of the non-negative OLS algorithm.

Original languageEnglish
Title of host publication2015 23rd European Signal Processing Conference, EUSIPCO 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9780992862633
Publication statusPublished - 22 Dec 2015
Event23rd European Signal Processing Conference, EUSIPCO 2015 - Nice, France
Duration: 31 Aug 20154 Sept 2015


Conference23rd European Signal Processing Conference, EUSIPCO 2015

Keywords / Materials (for Non-textual outputs)

  • Efficient Implementations
  • Non-negative Orthogonal Least Squares and QR Matrix Factorization
  • Non-negative sparse approximations
  • Orthogonal Least Squares


Dive into the research topics of 'Fast non-negative orthogonal least squares'. Together they form a unique fingerprint.

Cite this