mlsanityData to 7 Oct 2026

Provable Tensor Factorization with Missing Data

arXiv 1406.2784 ↗First posted 11 Jun 2014stat.MLcited by 31

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 3; 2023: 2; 2024: 4; 2025: 5; 2026: 3.

31 papers.

Sort:

  1. 2021Implicit Regularization in Tensor Factorizationcited by 43
  2. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  3. 2021Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learningcited by 25
  4. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  5. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  6. 2021A Random Matrix Perspective on Random Tensorscited by 12
  7. 2021TenIPS: Inverse Propensity Sampling for Tensor Completioncited by 7
  8. 2021Model based Multi-agent Reinforcement Learning with Tensor Decompositionscited by 7
  9. 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Modelcited by 7
  10. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  11. 2022Subquadratic Kronecker Regression with Applications to Tensor Decompositioncited by 6
  12. 2021Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Samplingcited by 5
19 more
  1. 2022Sparse random hypergraphs: Non-backtracking spectra and community detectioncited by 5
  2. 2023On High-dimensional and Low-rank Tensor Banditscited by 5
  3. 2024Non-Neighbors Also Matter to Kriging: A New Contrastive-Prototypical Learningcited by 5
  4. 2021New Riemannian preconditioned algorithms for tensor completion via polyadic decompositioncited by 4
  5. 2021Beyond the Signs: Nonparametric Tensor Completion via Sign Seriescited by 4
  6. 2021Covariate-assisted Sparse Tensor Completioncited by 4
  7. 2022Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeroscited by 3
  8. 2021Patch Tracking-based Streaming Tensor Ring Completion for Visual Data Recoverycited by 2
  9. 2023Spectral gap-based deterministic tensor completioncited by 1
  10. 2024Tensor Methods in High Dimensional Data Analysis: Opportunities and Challengescited by 1
  11. 2025Fourier Low-rank and Sparse Tensor for Efficient Tensor Completioncited by 1
  12. 2024Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordancited by 0
  13. 2025Fast Tensor Completion via Approximate Richardson Iterationcited by 0
  14. 2025Completion of the DrugMatrix Toxicogenomics Database using 3-Dimensional Tensorscited by 0
  15. 2025ACT-Tensor: Tensor Completion Framework for Financial Dataset Imputationcited by 0
  16. 2025An Interdisciplinary and Cross-Task Review on Missing Data Imputationcited by 0
  17. 2026Sharp spectral norm concentration of sparse random tensorscited by 0
  18. 2026Tensor Completion using Subspace Informationcited by 0
  19. 2026Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descentcited by 0