Fast and Accurate Element-Level Streaming CP Decomposition for Higher-Order Tensors

How can we efficiently and accurately analyze a tensor when only partial observations arrive over time? In an element-level streaming setting, only a subset of entries within the newest slice of a tensor is revealed at each update, either individually or in small groups. This formulation naturally arises when seasonal multivariate time-series are folded into higherorder tensors to separate periodic components (e.g., day-of-week) from longer trends, and new data appear as elements rather than full slices. Existing streaming tensor decomposition methods, designed for slice-level updates, become inefficient or inaccurate when applied to element-level streams. In this paper, we propose ENTP (Element-Level Streaming CP Decomposition), a fast and accurate online tensor decomposition method specifically designed for element-level tensor streams. ENTP partitions observations into structured subtensors and reformulates the optimization to include only the newly revealed entries, enabling accurate updates that affect only the relevant factors while avoiding redundant computation. Extensive experiments on real-world datasets show that ENTP achieves up to $28 \times$ speed-up over state-of-the-art baselines for streaming tensor decomposition, while maintaining comparable or higher accuracy. We further demonstrate that ENTP delivers strong predictive performance and scalability, confirming its effectiveness for realtime applications.