Provable Tensor Factorization with Missing Data

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\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.

26 pages 2 figures

References in corpus (4)

• Scalable Tensor Factorizations for Incomplete Data
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Convex Tensor Decomposition via Structured Schatten Norm Regularization

Cited by in corpus (41)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• A Geometric Analysis of Phase Retrieval
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Adaptive Sampling of RF Fingerprints for Fine-grained Indoor Localization
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Low-tubal-rank Tensor Completion using Alternating Minimization
• Brain-Computer Interface with Corrupted EEG Data: A Tensor Completion Approach
• Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVD
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• A New Sampling Technique for Tensors
• Tensor Completion Algorithms in Big Data Analytics
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Exact tensor completion using t-SVD
• Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition
• Sparse random tensors: Concentration, regularization and applications
• Robust Tensor Completion Using Transformed Tensor SVD
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Variational Bayesian Inference for Robust Streaming Tensor Factorization and Completion
• Partially Observed Dynamic Tensor Response Regression
• Deterministic tensor completion with hypergraph expanders
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Tensor Graphical Model: Non-convex Optimization and Statistical Inference
• A Random Matrix Perspective on Random Tensors
• Model based Multi-agent Reinforcement Learning with Tensor Decompositions
• Implicit Regularization in Tensor Factorization
• Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Robust Low-tubal-rank Tensor Completion based on Tensor Factorization and Maximum Correntopy Criterion
• A Super-Resolution Framework for Tensor Decomposition
• Tensor Completion via Tensor Networks with a Tucker Wrapper
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• TenIPS: Inverse Propensity Sampling for Tensor Completion
• HOSVD-Based Algorithm for Weighted Tensor Completion
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering
• Efficient Tensor Decomposition with Boolean Factors
• Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
• Regularized Orthogonal Tensor Decompositions for Multi-Relational Learning
• Riemannian Conjugate Gradient Descent Method for Third-Order Tensor Completion