Efficient Tensor Completion with Provable Guarantees

• Activity Number: 111
• Type: Invited
• Date/Time: Monday, August 10, 2015 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Sewoong Oh*
• Companies: University of Illinois at Urbana-Champaign
• Keywords: tensor decomposition ; matrix completion ; random matrix

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(n^(3/2)r^5(log n)^4) 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 Szemeredie 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.