@inproceedings{jain2014provable,
author = {Jain, Prateek and Oh, S.},
title = {Provable Tensor Factorization with Missing Data},
booktitle = {Advances in Neural Information Processing Systems (NIPS), 2014},
year = {2014},
month = {November},
abstract = {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×n×n dimensional rank-r tensor exactly from O(n3/2r5 log4 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/provable-tensor-factorization-with-missing-data/},
}