Provable Tensor Factorization with Missing Data

We study the problem of low-rank tensor factorization in the presence of missing data. We ask the following question: how many sampled entries do we need, to efficiently and exactly reconstruct a tensor with a low-rank orthogonal decomposition? We propose a novel alternating minimization based method which iteratively refines estimates of the singular vectors. We show that under certain standard assumptions, our method can recover a three-mode $n\times n\times n$ dimensional rank-$r$ tensor exactly from $O(n {3/2} r 5 \log 4 n)$ randomly sampled entries. In the process of proving this result, we solve two challenging sub-problems for tensors with missing data.