mlsanityData to 7 Oct 2026

On Polynomial Time Methods for Exact Low Rank Tensor Completion

arXiv 1702.06980 ↗First posted 22 Feb 2017stat.ML cs.IT cs.LGcited by 27

Not on the map. Why?

Abstract (arXiv)

In this paper, we investigate the sample size requirement for exact recovery of a high order tensor of low rank from a subset of its entries. We show that a gradient descent algorithm with initial value obtained from a spectral method can, in particular, reconstruct a d× d× d tensor of multilinear ranks (r,r,r) with high probability from as few as O(r7/2d3/2log7/2d+r7dlog6d) entries. In the case when the ranks r=O(1), our sample size requirement matches those for nuclear norm minimization (Yuan and Zhang, 2016a), or alternating least squares assuming orthogonal decomposability (Jain and Oh, 2014). Unlike these earlier approaches, however, our method is efficient to compute, easy to implement, and does not impose extra structures on the tensor. Numerical results are presented to further demonstrate the merits of the proposed approach.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Feb 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

27 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. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  4. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  5. 2022Subspace Recovery from Heterogeneous Data with Non-isotropic Noisecited by 14
  6. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  7. 2021Latent Space Model for Higher-order Networks and Generalized Tensor Decompositioncited by 13
  8. 2022Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descentcited by 11
  9. 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
  10. 2021Tensor Principal Component Analysis in High Dimensional CP Modelscited by 7
  11. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  12. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
15 more
  1. 2021Covariate-assisted Sparse Tensor Completioncited by 4
  2. 2023Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networkscited by 4
  3. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  4. 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
  5. 2022Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Modelcited by 3
  6. 2024Sharp Analysis of Power Iteration for Tensor PCAcited by 2
  7. 2024Causal Customer Churn Analysis with Low-rank Tensor Block Hazard Modelcited by 2
  8. 2026Low-Rank Adaptation Redux for Large Modelscited 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. 2026Structured Adaptive Tensor Prediction for Streaming Datacited by 0
  14. 2026Tensor Completion using Subspace Informationcited by 0
  15. 2026Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descentcited by 0