OnlineBTD: Streaming Algorithms to Track the Block Term Decomposition of Large Tensors
Ekta Gujral, Evangelos E. Papalexakis
Abstract
In data mining, block term tensor decomposition (BTD) is a relatively under-explored but very powerful multilayer factor analysis method that is ideally suited for modeling for batch processing of data which is either low or multi-linear rank, e.g., EEG/ECG signals, that extract "rich" structures (> rank – 1) from tensor data while still maintaining a lot of the desirable properties of popular tensor decompositions methods such as the interpretability, uniqueness, and etc. These days data, however, is constantly changing which hinders its use for large data. The tracking of the BTD decomposition for the dynamic tensors is a very pivotal and challenging task due to the variability of incoming data and lack of efficient online algorithms in terms of accuracy, time and space.In this paper, we fill this gap by proposing an efficient method OnlineBTD to compute the BTD decomposition of streaming tensor datasets containing millions of entries. In terms of effectiveness, our proposed method shows comparable results with the prior work, BTD, while being computationally much more efficient. We evaluate OnlineBTD on six synthetic and three diverse real datasets, indicatively, our proposed method shows 10 – 60% speedup and saves 40 – 70% memory usage over the traditional baseline methods and is capable of handling larger tensor streams for which the classic BTD fails to run. To the best of our knowledge, OnlineBTD is the first approach to track streaming block term decomposition while not only being able to provide stable decompositions but also provides better performance in terms of efficiency and scalability.