Fast non-negative orthogonal least squares. Yaghoobi, M. & Davies, M. E. In 2015 23rd European Signal Processing Conference (EUSIPCO), pages 479-483, Aug, 2015.
![Fast non-negative orthogonal least squares [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper doi abstract bibtex
Paper doi abstract bibtex 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.
@InProceedings{7362429,
author = {M. Yaghoobi and M. E. Davies},
booktitle = {2015 23rd European Signal Processing Conference (EUSIPCO)},
title = {Fast non-negative orthogonal least squares},
year = {2015},
pages = {479-483},
abstract = {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.},
keywords = {computational complexity;greedy algorithms;least squares approximations;matrix decomposition;signal processing;nonnegative orthogonal least square algorithm;nonnegative sparse signal;sparse signals;greedy technique;low-complexity sparse approximation;nonnegative OLS algorithm;residual energy reduction;QR matrix factorisation;NNOLS;computational complexity;Signal processing algorithms;Least squares approximations;Dictionaries;Signal processing;Approximation algorithms;Europe;Non-negative sparse approximations;Orthogonal Least Squares;Efficient Implementations;Non-negative Orthogonal Least Squares and QR Matrix Factorization},
doi = {10.1109/EUSIPCO.2015.7362429},
issn = {2076-1465},
month = {Aug},
url = {https://www.eurasip.org/proceedings/eusipco/eusipco2015/papers/1570104893.pdf},
}Downloads: 0
{"_id":"jFJ58GDP8qLdNimEc","bibbaseid":"yaghoobi-davies-fastnonnegativeorthogonalleastsquares-2015","authorIDs":[],"author_short":["Yaghoobi, M.","Davies, M. E."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["M."],"propositions":[],"lastnames":["Yaghoobi"],"suffixes":[]},{"firstnames":["M.","E."],"propositions":[],"lastnames":["Davies"],"suffixes":[]}],"booktitle":"2015 23rd European Signal Processing Conference (EUSIPCO)","title":"Fast non-negative orthogonal least squares","year":"2015","pages":"479-483","abstract":"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.","keywords":"computational complexity;greedy algorithms;least squares approximations;matrix decomposition;signal processing;nonnegative orthogonal least square algorithm;nonnegative sparse signal;sparse signals;greedy technique;low-complexity sparse approximation;nonnegative OLS algorithm;residual energy reduction;QR matrix factorisation;NNOLS;computational complexity;Signal processing algorithms;Least squares approximations;Dictionaries;Signal processing;Approximation algorithms;Europe;Non-negative sparse approximations;Orthogonal Least Squares;Efficient Implementations;Non-negative Orthogonal Least Squares and QR Matrix Factorization","doi":"10.1109/EUSIPCO.2015.7362429","issn":"2076-1465","month":"Aug","url":"https://www.eurasip.org/proceedings/eusipco/eusipco2015/papers/1570104893.pdf","bibtex":"@InProceedings{7362429,\n author = {M. Yaghoobi and M. E. Davies},\n booktitle = {2015 23rd European Signal Processing Conference (EUSIPCO)},\n title = {Fast non-negative orthogonal least squares},\n year = {2015},\n pages = {479-483},\n abstract = {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.},\n keywords = {computational complexity;greedy algorithms;least squares approximations;matrix decomposition;signal processing;nonnegative orthogonal least square algorithm;nonnegative sparse signal;sparse signals;greedy technique;low-complexity sparse approximation;nonnegative OLS algorithm;residual energy reduction;QR matrix factorisation;NNOLS;computational complexity;Signal processing algorithms;Least squares approximations;Dictionaries;Signal processing;Approximation algorithms;Europe;Non-negative sparse approximations;Orthogonal Least Squares;Efficient Implementations;Non-negative Orthogonal Least Squares and QR Matrix Factorization},\n doi = {10.1109/EUSIPCO.2015.7362429},\n issn = {2076-1465},\n month = {Aug},\n url = {https://www.eurasip.org/proceedings/eusipco/eusipco2015/papers/1570104893.pdf},\n}\n\n","author_short":["Yaghoobi, M.","Davies, M. E."],"key":"7362429","id":"7362429","bibbaseid":"yaghoobi-davies-fastnonnegativeorthogonalleastsquares-2015","role":"author","urls":{"Paper":"https://www.eurasip.org/proceedings/eusipco/eusipco2015/papers/1570104893.pdf"},"keyword":["computational complexity;greedy algorithms;least squares approximations;matrix decomposition;signal processing;nonnegative orthogonal least square algorithm;nonnegative sparse signal;sparse signals;greedy technique;low-complexity sparse approximation;nonnegative OLS algorithm;residual energy reduction;QR matrix factorisation;NNOLS;computational complexity;Signal processing algorithms;Least squares approximations;Dictionaries;Signal processing;Approximation algorithms;Europe;Non-negative sparse approximations;Orthogonal Least Squares;Efficient Implementations;Non-negative Orthogonal Least Squares and QR Matrix Factorization"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"inproceedings","biburl":"https://raw.githubusercontent.com/Roznn/EUSIPCO/main/eusipco2015url.bib","creationDate":"2021-02-13T17:31:52.307Z","downloads":0,"keywords":["computational complexity;greedy algorithms;least squares approximations;matrix decomposition;signal processing;nonnegative orthogonal least square algorithm;nonnegative sparse signal;sparse signals;greedy technique;low-complexity sparse approximation;nonnegative ols algorithm;residual energy reduction;qr matrix factorisation;nnols;computational complexity;signal processing algorithms;least squares approximations;dictionaries;signal processing;approximation algorithms;europe;non-negative sparse approximations;orthogonal least squares;efficient implementations;non-negative orthogonal least squares and qr matrix factorization"],"search_terms":["fast","non","negative","orthogonal","squares","yaghoobi","davies"],"title":"Fast non-negative orthogonal least squares","year":2015,"dataSources":["eov4vbT6mnAiTpKji","knrZsDjSNHWtA9WNT"]}