# Provable Tensor Factorization with Missing Data

arXiv: https://arxiv.org/abs/1406.2784 · HTML: https://mlsanity.com/paper/1406.2784/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2014.

## Built on by (most cited first, 30 of 31)

- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00136/) (2021)
- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [A Random Matrix Perspective on Random Tensors](https://mlsanity.com/paper/2108.00774/) (2021)
- [TenIPS: Inverse Propensity Sampling for Tensor Completion](https://mlsanity.com/paper/2101.00323/) (2021)
- [Model based Multi-agent Reinforcement Learning with Tensor Decompositions](https://mlsanity.com/paper/2110.14524/) (2021)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling](https://mlsanity.com/paper/2107.10654/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [On High-dimensional and Low-rank Tensor Bandits](https://mlsanity.com/paper/2305.03884/) (2023)
- [Non-Neighbors Also Matter to Kriging: A New Contrastive-Prototypical Learning](https://mlsanity.com/paper/2401.12681/) (2024)
- [New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition](https://mlsanity.com/paper/2101.11108/) (2021)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Covariate-assisted Sparse Tensor Completion](https://mlsanity.com/paper/2103.06428/) (2021)
- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)
- [Patch Tracking-based Streaming Tensor Ring Completion for Visual Data Recovery](https://mlsanity.com/paper/2105.14620/) (2021)
- [Spectral gap-based deterministic tensor completion](https://mlsanity.com/paper/2306.06262/) (2023)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Fourier Low-rank and Sparse Tensor for Efficient Tensor Completion](https://mlsanity.com/paper/2505.11261/) (2025)
- [Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan](https://mlsanity.com/paper/2408.05431/) (2024)
- [Fast Tensor Completion via Approximate Richardson Iteration](https://mlsanity.com/paper/2502.09534/) (2025)
- [Completion of the DrugMatrix Toxicogenomics Database using 3-Dimensional Tensors](https://mlsanity.com/paper/2507.03024/) (2025)
- [ACT-Tensor: Tensor Completion Framework for Financial Dataset Imputation](https://mlsanity.com/paper/2508.01861/) (2025)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)
- [Sharp spectral norm concentration of sparse random tensors](https://mlsanity.com/paper/2609.20520/) (2026)
- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)

## Abstract (arXiv)

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/2 r5 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'edie 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.