Provable Tensor Factorization with Missing Data
This addresses the challenge of efficiently recovering tensors from incomplete data, which is incremental as it builds on existing factorization techniques with provable guarantees.
The paper tackles the problem of low-rank tensor factorization with missing data by proposing an alternating minimization method, achieving exact reconstruction of a three-mode n×n×n rank-r tensor from O(n^{3/2} r^5 log^4 n) randomly sampled entries under standard assumptions.
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. First, in the process of analyzing the initialization step, we prove a generalization of a celebrated result by Szemerédie et al. on the spectrum of random graphs. Next, we prove global convergence of alternating minimization with a good initialization. Simulations suggest that the dependence of the sample size on dimensionality $n$ is indeed tight.