Fast non-negative orthogonal least squares
| Autor: | Michael Davies, Mehrdad Yaghoobi |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Efficient Implementations
Signal processing Class (set theory) Mathematical optimization Computational complexity theory Approximation algorithm Extension (predicate logic) Domain (mathematical analysis) Reduction (complexity) Non-negative Orthogonal Least Squares and QR Matrix Factorization Non-negative sparse approximations Signal Processing Media Technology Orthogonal Least Squares Computer Vision and Pattern Recognition Order of magnitude Mathematics |
| Zdroj: | EUSIPCO Yaghoobi Vaighan, M & Davies, M 2015, Fast non-negative orthogonal least squares . in 2015 23rd European Signal Processing Conference, EUSIPCO 2015 ., 7362429, Institute of Electrical and Electronics Engineers Inc., pp. 479-483, 23rd European Signal Processing Conference, EUSIPCO 2015, Nice, France, 31/08/15 . https://doi.org/10.1109/EUSIPCO.2015.7362429 |
| DOI: | 10.1109/eusipco.2015.7362429 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|