# Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries

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

## Key facts

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

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

- [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)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption](https://mlsanity.com/paper/2305.04080/) (2023)
- [TenIPS: Inverse Propensity Sampling for Tensor Completion](https://mlsanity.com/paper/2101.00323/) (2021)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures](https://mlsanity.com/paper/2201.09040/) (2022)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [On High-dimensional and Low-rank Tensor Bandits](https://mlsanity.com/paper/2305.03884/) (2023)
- [Covariate-assisted Sparse Tensor Completion](https://mlsanity.com/paper/2103.06428/) (2021)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [Self-Supervised Metric Learning in Multi-View Data: A Downstream Task Perspective](https://mlsanity.com/paper/2106.07138/) (2021)
- [Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Model](https://mlsanity.com/paper/2209.13762/) (2022)
- [A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression](https://mlsanity.com/paper/2504.08178/) (2025)
- [Multi-dimensional domain generalization with low-rank structures](https://mlsanity.com/paper/2309.09555/) (2023)
- [Causal Customer Churn Analysis with Low-rank Tensor Block Hazard Model](https://mlsanity.com/paper/2405.11377/) (2024)
- [Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps](https://mlsanity.com/paper/2104.03298/) (2021)
- [Jointly Modeling and Clustering Tensors in High Dimensions](https://mlsanity.com/paper/2104.07773/) (2021)
- [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)
- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)
- [Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descent](https://mlsanity.com/paper/2609.24679/) (2026)

## Abstract (arXiv)

In this article, we develop methods for estimating a low rank tensor from noisy observations on a subset of its entries to achieve both statistical and computational efficiencies. There have been a lot of recent interests in this problem of noisy tensor completion. Much of the attention has been focused on the fundamental computational challenges often associated with problems involving higher order tensors, yet very little is known about their statistical performance. To fill in this void, in this article, we characterize the fundamental statistical limits of noisy tensor completion by establishing minimax optimal rates of convergence for estimating a kth order low rank tensor under the general ℓp (1≤ p≤ 2) norm which suggest significant room for improvement over the existing approaches. Furthermore, we propose a polynomial-time computable estimating procedure based upon power iteration and a second-order spectral initialization that achieves the optimal rates of convergence. Our method is fairly easy to implement and numerical experiments are presented to further demonstrate the practical merits of our estimator.