# Near-optimal sample complexity for convex tensor completion

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

## Key facts

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

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

- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [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)
- [Near-Efficient and Non-Asymptotic Multiway Inference](https://mlsanity.com/paper/2511.05368/) (2025)
- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)

## Abstract (arXiv)

We analyze low rank tensor completion (TC) using noisy measurements of a subset of the tensor. Assuming a rank-r, order-d, N × N × cdots × N tensor where r=O(1), the best sampling complexity that was achieved is O(N^fracd2), which is obtained by solving a tensor nuclear-norm minimization problem. However, this bound is significantly larger than the number of free variables in a low rank tensor which is O(dN). In this paper, we show that by using an atomic-norm whose atoms are rank-1 sign tensors, one can obtain a sample complexity of O(dN). Moreover, we generalize the matrix max-norm definition to tensors, which results in a max-quasi-norm (max-qnorm) whose unit ball has small Rademacher complexity. We prove that solving a constrained least squares estimation using either the convex atomic-norm or the nonconvex max-qnorm results in optimal sample complexity for the problem of low-rank tensor completion. Furthermore, we show that these bounds are nearly minimax rate-optimal. We also provide promising numerical results for max-qnorm constrained tensor completion, showing improved recovery results compared to matricization and alternating least squares.