# Nonconvex Low-Rank Tensor Completion from Noisy Data

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

## Key facts

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

## Built on by (most cited first, 30 of 35)

- [Initialization and Regularization of Factorized Neural Layers](https://mlsanity.com/paper/2105.01029/) (2021)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [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)
- [On Speeding Up Language Model Evaluation](https://mlsanity.com/paper/2407.06172/) (2024)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [Tensor Principal Component Analysis in High Dimensional CP Models](https://mlsanity.com/paper/2108.04428/) (2021)
- [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)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)
- [Multilinear Kernel Regression and Imputation via Manifold Learning](https://mlsanity.com/paper/2402.03648/) (2024)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)
- [Causal Customer Churn Analysis with Low-rank Tensor Block Hazard Model](https://mlsanity.com/paper/2405.11377/) (2024)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Jointly Modeling and Clustering Tensors in High Dimensions](https://mlsanity.com/paper/2104.07773/) (2021)
- [A generalizable framework for low-rank tensor completion with numerical priors](https://mlsanity.com/paper/2302.05881/) (2023)
- [Multi-dimensional Signal Recovery using Low-rank Deconvolution](https://mlsanity.com/paper/2305.02264/) (2023)
- [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 Leveraging Graph Information: A Dynamic Regularization Approach with Statistical Guarantees](https://mlsanity.com/paper/2310.02543/) (2023)
- [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)

## Abstract (arXiv)

We study a noisy tensor completion problem of broad practical interest, namely, the reconstruction of a low-rank tensor from highly incomplete and randomly corrupted observations of its entries. While a variety of prior work has been dedicated to this problem, prior algorithms either are computationally too expensive for large-scale applications, or come with sub-optimal statistical guarantees. Focusing on "incoherent" and well-conditioned tensors of a constant CP rank, we propose a two-stage nonconvex algorithm -- (vanilla) gradient descent following a rough initialization -- that achieves the best of both worlds. Specifically, the proposed nonconvex algorithm faithfully completes the tensor and retrieves all individual tensor factors within nearly linear time, while at the same time enjoying near-optimal statistical guarantees (i.e. minimal sample complexity and optimal estimation accuracy). The estimation errors are evenly spread out across all entries, thus achieving optimal ℓ∞ statistical accuracy. We have also discussed how to extend our approach to accommodate asymmetric tensors. The insight conveyed through our analysis of nonconvex optimization might have implications for other tensor estimation problems.