# Spectral algorithms for tensor completion

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2016.

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

- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (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)
- [PerSim: Data-Efficient Offline Reinforcement Learning with Heterogeneous Agents via Personalized Simulators](https://mlsanity.com/paper/2102.06961/) (2021)
- [Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approach](https://mlsanity.com/paper/2203.00126/) (2022)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [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)
- [Nonnegative Tensor Completion via Integer Optimization](https://mlsanity.com/paper/2111.04580/) (2021)
- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)
- [One-sided Matrix Completion from Two Observations Per Row](https://mlsanity.com/paper/2306.04049/) (2023)
- [Multi-dimensional domain generalization with low-rank structures](https://mlsanity.com/paper/2309.09555/) (2023)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)
- [Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networks](https://mlsanity.com/paper/2510.18435/) (2025)
- [Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps](https://mlsanity.com/paper/2104.03298/) (2021)
- [Accelerated Nonnegative Tensor Completion via Integer Programming](https://mlsanity.com/paper/2211.15770/) (2022)
- [Under-Counted Tensor Completion with Neural Incorporation of Attributes](https://mlsanity.com/paper/2306.03273/) (2023)
- [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)
- [Tensor Completion via Integer Optimization](https://mlsanity.com/paper/2402.05141/) (2024)
- [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)
- [ACT-Tensor: Tensor Completion Framework for Financial Dataset Imputation](https://mlsanity.com/paper/2508.01861/) (2025)
- [Near-Efficient and Non-Asymptotic Multiway Inference](https://mlsanity.com/paper/2511.05368/) (2025)

## Abstract (arXiv)

In the tensor completion problem, one seeks to estimate a low-rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial-time algorithms. Among the latter, the best statistical guarantees have been proved, for third-order tensors, using the sixth level of the sum-of-squares (SOS) semidefinite programming hierarchy (Barak and Moitra, 2014). However, the SOS approach does not scale well to large problem instances. By contrast, spectral methods --- based on unfolding or matricizing the tensor --- are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new unfolding-based method, which outperforms naive ones for symmetric k-th order tensors of rank r. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third-order tensors, our algorithm matches the SOS method in terms of sample size (requiring about rd3/2 revealed entries), subject to a worse rank condition (rll d3/4 rather than rll d3/2). We complement this result with a different spectral algorithm for third-order tensors in the overcomplete (r≥ d) regime. Under a random model, this second approach succeeds in estimating tensors of rank d≤ r ll d3/2 from about rd3/2 revealed entries.