Randomized LU decomposition: An Algorithm for Dictionaries Construction
This work addresses the need for efficient dictionary construction in data processing, particularly for content-based file detection in computer security, though it appears incremental as it builds on existing low-rank factorization methods.
The authors tackled the problem of dictionary construction for signal classification by introducing a randomized LU decomposition algorithm that is fast, scalable, and memory-efficient, outperforming SVD in these aspects. They demonstrated its effectiveness in file type identification, showing that only a few file fragments are needed for successful classification, such as identifying execution code in PDF files.
In recent years, distinctive-dictionary construction has gained importance due to his usefulness in data processing. Usually, one or more dictionaries are constructed from a training data and then they are used to classify signals that did not participate in the training process. A new dictionary construction algorithm is introduced. It is based on a low-rank matrix factorization being achieved by the application of the randomized LU decomposition to a training data. This method is fast, scalable, parallelizable, consumes low memory, outperforms SVD in these categories and works also extremely well on large sparse matrices. In contrast to existing methods, the randomized LU decomposition constructs an under-complete dictionary, which simplifies both the construction and the classification processes of newly arrived signals. The dictionary construction is generic and general that fits different applications. We demonstrate the capabilities of this algorithm for file type identification, which is a fundamental task in digital security arena, performed nowadays for example by sandboxing mechanism, deep packet inspection, firewalls and anti-virus systems. We propose a content-based method that detects file types that neither depend on file extension nor on metadata. Such approach is harder to deceive and we show that only a few file fragments from a whole file are needed for a successful classification. Based on the constructed dictionaries, we show that the proposed method can effectively identify execution code fragments in PDF files. $\textbf{Keywords.}$ Dictionary construction, classification, LU decomposition, randomized LU decomposition, content-based file detection, computer security.