论文标题
加速搜索通过降低维度的非负贪婪稀疏分解
Accelerated Search for Non-Negative Greedy Sparse Decomposition via Dimensionality Reduction
论文作者
论文摘要
非阴性信号构成了重要的一类稀疏信号。许多算法已经被普遍恢复这种非阴性表示形式，在这种情况下，贪婪和凸出的放松算法是最受欢迎的方法之一。一个快速的实现是FNNOMP算法，该算法以迭代方式更新非负系数。即使FNNOMP在小尺寸的库时是一种很好的方法，但是当库大小较大时，算法的运行时间显着增长。这主要是由于依赖于矩阵向量乘法的算法的选择步骤。我们在这里介绍了嵌入式最近的邻居（E-NN）算法，该算法在大型数据集上加速搜索，同时保证找到最相关的原子。然后，我们用E-NN替换FNNOMP的选择步骤。此外，我们在FNNOMP的查找表中介绍了最近的邻居（U-NN），以确保FNNOMP的非阴性标准。结果表明，所提出的方法可以在拉曼光谱的真实数据集中使用因子4加速FNNOMP，在合成数据集上具有22倍。
Non-negative signals form an important class of sparse signals. Many algorithms have already beenproposed 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.
