Robust Factorization of Real-world Tensor Streams with Patterns, Missing Values, and Outliers

Abstract

Consider multiple seasonal time series being collected in real-time, in the form of a tensor stream. Real-world tensor streams often include missing entries (e.g., due to network disconnection) and at the same time unexpected outliers (e.g., due to system errors). Given such a real-world tensor stream, how can we estimate missing entries and predict future evolution accurately in real-time? In this work, we answer this question by introducing SOFIA, a robust factorization method for real-world tensor streams. In a nutshell, SOFIA smoothly and tightly integrates tensor factorization, outlier removal, and temporal-pattern detection, which naturally reinforce each other. Moreover, SOFIA integrates them in linear time, in an online manner, despite the presence of missing entries. We experimentally show that SOFIA is (a) robust and accurate: yielding up to 76% lower imputation error and 71% lower forecasting error; (b) fast: up to 935X faster than the second-most accurate competitor; and (c) scalable: scaling linearly with the number of new entries per time step.

arXiv commentPublished at ICDE 2021

References in corpus (10)

• Tensor Decomposition for Signal Processing and Machine Learning
• Scalable Tensor Factorizations for Incomplete Data
• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Robust Low-rank Tensor Recovery: Models and Algorithms
• Smooth PARAFAC Decomposition for Tensor Completion
• Bayesian Robust Tensor Factorization for Incomplete Multiway Data
• Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
• Online Low-Rank Tensor Subspace Tracking from Incomplete Data by CP Decomposition using Recursive Least Squares
• Discovering and Characterizing Mobility Patterns in Urban Spaces: A Study of Manhattan Taxi Data
• Variational Bayesian Inference for Robust Streaming Tensor Factorization and Completion