  We consider the problem of factorizing a structured 3-way tensor into its
constituent Canonical Polyadic (CP) factors. This decomposition, which can be
viewed as a generalization of singular value decomposition (SVD) for tensors,
reveals how the tensor dimensions (features) interact with each other. However,
since the factors are a priori unknown, the corresponding optimization problems
are inherently non-convex. The existing guaranteed algorithms which handle this
non-convexity incur an irreducible error (bias), and only apply to cases where
all factors have the same structure. To this end, we develop a provable
algorithm for online structured tensor factorization, wherein one of the
factors obeys some incoherence conditions, and the others are sparse.
Specifically we show that, under some relatively mild conditions on
initialization, rank, and sparsity, our algorithm recovers the factors exactly
(up to scaling and permutation) at a linear rate. Complementary to our
theoretical results, our synthetic and real-world data evaluations showcase
superior performance compared to related techniques. Moreover, its scalability
and ability to learn on-the-fly makes it suitable for real-world tasks.
