DAO-CP: Data-Adaptive Online CP decomposition for tensor stream

Abstract

How can we accurately and efficiently decompose a tensor stream? Tensor decomposition is a crucial task in a wide range of applications and plays a significant role in latent feature extraction and estimation of unobserved entries of data. The problem of efficiently decomposing tensor streams has been of great interest because many real-world data dynamically change over time. However, existing methods for dynamic tensor decomposition sacrifice the accuracy too much, which limits their usages in practice. Moreover, the accuracy loss becomes even more serious when the tensor stream has an inconsistent temporal pattern since the current methods cannot adapt quickly to a sudden change in data. In this paper, we propose DAO-CP, an accurate and efficient online CP decomposition method which adapts to data changes. DAO-CP tracks local error norms of the tensor streams, detecting a change point of the error norms. It then chooses the best strategy depending on the degree of changes to balance the trade-off between speed and accuracy. Specifically, DAO-CP decides whether to (1) reuse the previous factor matrices for the fast running time or (2) discard them and restart the decomposition to increase the accuracy. Experimental results show that DAO-CP achieves the state-of-the-art accuracy without noticeable loss of speed compared to existing methods.

Fig 1. Accuracy comparison between DAO-CP (proposed) and its competitors on Airport Hall (upper) and Sample Video (lower) datasets.

DAO-CP automatically detects a change of theme (for example, an object starts moving or a scene changes) and re-decomposes the data depending on the degree of changes. Note that DAO-CP results in much more clear images than the competitors with little sacrifice in speed.

Fig 2. Visualization of OnlineCP.

In this figure, the length of time factor (with horizontal axis) becomes larger for each time step. Contrary to static decomposition methods, OnlineCP reduces computational cost using approximation with an additional constraint: it updates only the non-temporal mode, reusing the same temporal factor for all time steps. However, this leads to a substantial loss of accuracy if an incoming tensor has a different theme compared to previous tensors (e.g., theme changes A → B, B′ → C, or C → D). Thus, OnlineCP cannot achieve an accurate decomposition due to the lack of consideration on the change of themes in data.

Fig 3. Visualization of split and refinement processes of DAO-CP.

When the z-score exceeds the split threshold L_s (e.g., change from theme A to B), DAO-CP re-initializes the new tensor slice using the static CP decomposition. When the z-score is between L_r and L_s (e.g, change from theme B to B′), the refinement process determines how much information from the previous factors should be retained. Consequently, DAO-CP provides both fast and accurate decomposition for tensor streams even with inconsistent temporal patterns.

Fig 4. Reconstruction errors: Global (upper) and local (lower) fitness.

Since Full–CP is not an online method, we evaluate its fitness whenever a new slice is added. Detecting the change points of theme, DAO-CP successfully increases the accuracy of decomposition, which is even higher than that of Full–CP.

Fig 5. Time cost: Average of local running time.

Since Full–CP is not an online method, we evaluate its fitness whenever a new slice is added. Note that DAO-CP results in a promising speed comparable to DTD and OnlineCP with much more accurate decomposition, and significantly faster than Full–CP.

Fig 6. Refinement and split processes: Effects of split (solid line) and refinement (dashed line) processes in terms of local error norm (upper) and running time (lower).

Each re-decomposition process (at split point) significantly reduces the local error norm with only a modest sacrifice of running time (e.g., vertical line connecting P_prev, P_next, Q_prev, and Q_next). Note that DAO-CP runs slower than the other dynamic methods (OnlineCP and DTD) only when one of split or refinement processes is performed to increase the accuracy (horizontal line R: average running time of competitor methods).