Overview
How can we decompose a streaming tensor accurately and efficiently? Many real-world tensors are dynamic, that is, their size and value evolve. CP decomposition, one of the most popular tools for analyzing tensors, is not readily applicable to dynamic tensors. This is because it performs many iterations until convergence whenever a new tensor comes in, leading to an intractable amount of computation. Thus, existing methods for dynamic tensor decomposition have focused on reducing the running time of an algorithm; however, this in turn results in a substantial loss of accuracy.
In this work, we propose DAO-CP, a novel approach for accurate and efficient decomposition that is adaptive to data changes in higher-order streaming tensors. DAO-CP detects each data slice's theme and performs accuracy optimization by choosing whether to (1) split the tensor or (2) refine its factors with re-decomposition. The split process enables memory-efficient management to avoid excessive computations due to the time-incremental factor, while the refinement process achieves much more accurate decomposition. DAO-CP tracks every local error norm of each data slice to detect a change point and determines which process to be executed. The overall decision-making module in an updatable tensor stream framework improves DAO-CP to have better efficiency and scalability. By maintaining time and memory complexity comparable to state-of-the-art online methods, DAO-CP shows higher fitness up to 91.2%, whereas Full-CP exhibits fitness of 83.9%.
Paper
-
DAO-CP: Data-Adaptive Online CP decomposition for tensor stream
Sangjun Son*, Yong-chan Park*, Minyong Cho, and U Kang
The paper is submitted to PLOS ONE journal.
[Paper] [Bibtex]
* Both authors contributed equally to this work.
Code
-
The code and datasets used in the paper are available in GitHub.
You can also download them as [zip] or [tar.gz] format.
Datasets
| Name | Order | Dimensions | Description | Source |
|---|---|---|---|---|
| Synthetic Data | 4 | (1K, 10, 20, 30) | Synthetic tensor of various themes. consists of (timestamp, custom mode1, custom mode2, custom mode3) |
Link |
| Sample Video | 4 | (205, 240, 320, 3) | Sample video on YouTube. consists of (frame, width, height, RGB colors) |
Link |
| Stock Price | 3 | (3K, 140, 5) | Korea stock price. consists of (timestamp in date, stock, price type) |
Link |
| Airport Hall | 3 | (200, 144, 176) | Airport hall video. consists of (frame, width, height) |
Link |
| Korea Air Quality | 3 | (10K, 323, 6) | Measurements of pollutants in Korea. consists of (timestamp in hour, location, atmospheric pollutants, measurement) |
Link |
People
- Sangjun Son (Seoul National University)
- Yong-chan Park (Seoul National University)
- Minyong Cho (Seoul National University)
- U Kang (Seoul National University)