# Tensor Completion Made Practical

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2020.

## Built on by (most cited first, 15 of 15)

- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (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)
- [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)
- [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)
- [Provable Adaptation across Multiway Domains via Representation Learning](https://mlsanity.com/paper/2106.06657/) (2021)
- [Tensor completion using geodesics on Segre manifolds](https://mlsanity.com/paper/2108.00735/) (2021)
- [Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity](https://mlsanity.com/paper/2308.01677/) (2023)
- [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)

## Abstract (arXiv)

Tensor completion is a natural higher-order generalization of matrix completion where the goal is to recover a low-rank tensor from sparse observations of its entries. Existing algorithms are either heuristic without provable guarantees, based on solving large semidefinite programs which are impractical to run, or make strong assumptions such as requiring the factors to be nearly orthogonal. In this paper we introduce a new variant of alternating minimization, which in turn is inspired by understanding how the progress measures that guide convergence of alternating minimization in the matrix setting need to be adapted to the tensor setting. We show strong provable guarantees, including showing that our algorithm converges linearly to the true tensors even when the factors are highly correlated and can be implemented in nearly linear time. Moreover our algorithm is also highly practical and we show that we can complete third order tensors with a thousand dimensions from observing a tiny fraction of its entries. In contrast, and somewhat surprisingly, we show that the standard version of alternating minimization, without our new twist, can converge at a drastically slower rate in practice.