  Tensors are widely used to represent multiway arrays of data. The recovery of
missing entries in a tensor has been extensively studied, generally under the
assumption that entries are missing completely at random (MCAR). However, in
most practical settings, observations are missing not at random (MNAR): the
probability that a given entry is observed (also called the propensity) may
depend on other entries in the tensor or even on the value of the missing
entry. In this paper, we study the problem of completing a partially observed
tensor with MNAR observations, without prior information about the
propensities. To complete the tensor, we assume that both the original tensor
and the tensor of propensities have low multilinear rank. The algorithm first
estimates the propensities using a convex relaxation and then predicts missing
values using a higher-order SVD approach, reweighting the observed tensor by
the inverse propensities. We provide finite-sample error bounds on the
resulting complete tensor. Numerical experiments demonstrate the effectiveness
of our approach.
