Abstract
Streaming tensor factorization is a powerful tool for processing high-volume and multi-way temporal data in Internet networks, recommender systems and image/video data analysis. In many applications the full tensor is not known, but instead received in a slice-by-slice manner over time. Streaming factorizations aim to take advantage of inherent temporal relationships in data analytics. Existing streaming tensor factorization algorithms rely on least-squares data fitting and they do not possess a mechanism for tensor rank determination. This leaves them susceptible to outliers and vulnerable to over-fitting. This paper presents the first Bayesian robust streaming tensor factorization model. Our model successfully identifies sparse outliers, automatically determines the underlying tensor rank and accurately fits low-rank structure. We implement our model in Matlab and compare it to existing algorithms. Our algorithm is applied to factorize and complete various streaming tensors including synthetic data, dynamic MRI, video sequences, and Internet traffic data.
Introduction: The Challenge of Streaming Multi-way Data
Tensors—multi-way data arrays—serve as the standard format for complex datasets such as video sequences, medical imaging (MRI), and network traffic. In many real-world scenarios, this data arrives as a "stream," slice-by-slice over time. Processing such data requires algorithms that can update their models incrementally without re-processing the entire history.
Existing streaming factorization methods, such as Online-CP or OLSTEC, face two significant hurdles. First, they typically require a pre-defined "rank" or complexity level. An incorrect guess leads to either over-fitting or under-fitting. Second, they are highly sensitive to outliers. Relying on least-squares fitting means a single anomalous data point can significantly distort the entire model.
Methodology: A Robust Bayesian Framework
To address these limitations, this paper introduces a robust model that decomposes each incoming tensor slice ($X_t$) into three distinct components:
- Low-Rank ($\tilde{X}_t$): The underlying core structure, modeled via CP decomposition.
- Sparse Outliers ($S_t$): A component designed to capture sudden spikes or anomalies.
- Noise ($E_t$): Standard dense Gaussian noise.
The core innovation lies in the use of Variational Bayesian (VB) Inference. Unlike traditional optimization, VB approximates the probability distributions of hidden factors, providing a principled way to handle uncertainty and missing data. Furthermore, the model employs "sparsity-inducing" Gamma priors to automatically determine the optimal tensor rank during the streaming process. To account for temporal drift, an exponentially weighted forgetting factor ($\mu$) is integrated, ensuring the model prioritizes recent observations.
Key Results and Performance
The proposed method was evaluated against several benchmarks, including synthetic data, surveillance video, dynamic cardiac MRI, and Abilene network traffic.
As shown in the performance plots, the proposed algorithm (purple dashed line) consistently maintains a low relative error (approximately 0.1) even when data is sparsely sampled (15%) or corrupted by outliers. In contrast, competing methods like OLSTEC and Online-SGD exhibit significantly higher errors and greater instability.
In practical applications:
- Video Completion: The model successfully reconstructed video frames with 85% missing entries, effectively separating static backgrounds from moving foreground objects.
- Medical Imaging: In 3D cardiac MRI reconstruction, the method handled 50% missing data more effectively than standard techniques, preserving sharp edges in moving tissues.
- Anomaly Detection: The model's low residual error in network traffic tests made it significantly easier to distinguish normal flow from malicious spikes like DDoS attacks.
Conclusion and Future Directions
This work presents the first Bayesian framework for robust streaming tensor factorization. By treating outliers as a structural component and automating rank determination, the algorithm provides a robust and adaptive solution for real-time data analysis. While the current implementation focuses on CP decomposition, future work could extend this framework to Tucker or Tensor-Train formats to further enhance efficiency for specific multi-way data types.
Summary updated