Abstract
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.
Introduction
Sparse decomposition is a fundamental task in signal processing, aiming to represent a signal using a minimal number of "atoms" from a large dictionary. In fields like Raman spectroscopy and hyperspectral imaging, these representations must be non-negative to reflect physical realities like intensity or concentration. The Fast Non-Negative Orthogonal Matching Pursuit (FNNOMP) is a standard algorithm for this task. However, its computational cost scales linearly with the dictionary size due to the exhaustive search required at each iteration to select the most correlated atom. This bottleneck limits its applicability to massive datasets or real-time scenarios.
Methodology
To address the scalability of FNNOMP, this research proposes a dimensionality reduction framework. The core idea is to perform the atom selection in a lower-dimensional subspace while maintaining the exactness of the original high-dimensional search.
Embedded Nearest Neighbor (E-NN)
The E-NN algorithm projects both the signal and the dictionary into a subspace of dimension $K \ll M$. To compensate for the distortion introduced by projection, a distance buffer $\delta$ is calculated based on the Johnson-Lindenstrauss lemma. This buffer defines a search radius in the low-dimensional space that is guaranteed to contain the true nearest neighbor from the original space.
Embedding Techniques
The researchers evaluated three linear embedding methods: Principal Component Analysis (PCA), Random Projections, and NuMax. NuMax is a deterministic framework designed to minimize distance distortion. As shown in Figure 1, NuMax consistently outperformed PCA and Random Projections in preserving point representations across different distance thresholds, particularly for the Raman dataset.
Update Nearest Neighbor (U-NN)
In non-negative decomposition, the primary candidate atom might be rejected if it leads to negative coefficients. U-NN efficiently identifies the next-best candidates within the reduced search space to satisfy the non-negativity constraint without re-executing the full search.
Experimental Results
The E-NN FNNOMP approach was tested on a real-world Raman Spectra dataset ($M=1507, N=4041$) and a synthetic Swiss Roll dataset. The Swiss Roll dataset, despite its high ambient dimensionality, has a low intrinsic dimensionality (2D manifold), making it an ideal test case for dimensionality reduction.
The results demonstrate significant computational gains without any loss in decomposition accuracy. For the Swiss Roll dataset, the algorithm achieved a 22x speedup. For the more complex Raman dataset, a 4x speedup was observed.
As illustrated in Figure 6, the time required for E-NN FNNOMP grows much more slowly with the number of iterations ($j$) compared to the standard FNNOMP. The acceleration factor remains relatively stable, particularly for the Swiss Roll dataset, where the low intrinsic dimensionality allows for highly efficient search in the embedded space.
Conclusion
The integration of E-NN and U-NN into the FNNOMP framework provides a robust method for accelerating non-negative sparse decomposition. By leveraging the low intrinsic dimensionality of many physical signals, the proposed method achieves order-of-magnitude speedups while guaranteeing the same optimal selection as a brute-force search. Future work may explore non-linear embeddings to further enhance performance on datasets with complex manifold structures that are not perfectly captured by linear projections.
Summary updated