Accelerated Search for Non-Negative Greedy Sparse Decomposition via Dimensionality Reduction
| Autor: | Mehrdad Yaghoobi, Konstantinos A. Voulgaris, Michael Davies |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Signal Processing (eess.SP)
Computer science Dimensionality reduction Regular polygon 020206 networking & telecommunications 010103 numerical & computational mathematics 02 engineering and technology Sparse approximation 01 natural sciences Matching pursuit k-nearest neighbors algorithm Matrix (mathematics) Lookup table FOS: Electrical engineering electronic engineering information engineering 0202 electrical engineering electronic engineering information engineering 0101 mathematics Electrical Engineering and Systems Science - Signal Processing Algorithm Selection (genetic algorithm) |
| Zdroj: | Voulgaris, K, Davies, M & Yaghoobi Vaighan, M 2019, Accelerated Search for Non–Negative Greedy Sparse Decomposition via Dimensionality Reduction . in Sensor Signal Processing for Defence (SSPD) . Institute of Electrical and Electronics Engineers (IEEE) . https://doi.org/10.1109/SSPD.2019.8751661 |
| DOI: | 10.1109/SSPD.2019.8751661 |
| Popis: | Non-negative signals form an important class of sparse 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. One fast implementation is the FNNOMP algorithm that updates the non-negative coefficients in an iterative manner. Even though FNNOMP is a good approach when working on libraries of small size, the operational time of the algorithm grows significantly when the size of the library is large. This is mainly due to the selection step of the algorithm that relies on matrix vector multiplications. We here introduce the Embedded Nearest Neighbor (E-NN) algorithm which accelerates the search over large datasets while it is guaranteed to find the most correlated atoms. We then replace the selection step of FNNOMP by E-NN. Furthermore we introduce the Update Nearest Neighbor (U-NN) at the look up table of FNNOMP in order to assure the non-negativity criteria of FNNOMP. The results indicate that the proposed methodology can accelerate FNNOMP with a factor 4 on a real dataset of Raman Spectra and with a factor of 22 on a synthetic dataset. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|