# Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion

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

## Key facts

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

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

- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Tensor train completion: local recovery guarantees via Riemannian optimization](https://mlsanity.com/paper/2110.03975/) (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)
- [Accelerated Nonnegative Tensor Completion via Integer Programming](https://mlsanity.com/paper/2211.15770/) (2022)
- [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)
- [Sharp spectral norm concentration of sparse random tensors](https://mlsanity.com/paper/2609.20520/) (2026)

## Abstract (arXiv)

In this paper, we investigate the sample size requirement for a general class of nuclear norm minimization methods for higher order tensor completion. We introduce a class of tensor norms by allowing for different levels of coherence, which allows us to leverage the incoherence of a tensor. In particular, we show that a kth order tensor of rank r and dimension d×cdots× d can be recovered perfectly from as few as O((r(k-1)/2d3/2+rk-1d)(log(d))2) uniformly sampled entries through an appropriate incoherent nuclear norm minimization. Our results demonstrate some key differences between completing a matrix and a higher order tensor: They not only point to potential room for improvement over the usual nuclear norm minimization but also highlight the importance of explicitly accounting for incoherence, when dealing with higher order tensors.