  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.
