  Higher-order tensor datasets arise commonly in recommendation systems,
neuroimaging, and social networks. Here we develop probable methods for
estimating a possibly high rank signal tensor from noisy observations. We
consider a generative latent variable tensor model that incorporates both high
rank and low rank models, including but not limited to, simple hypergraphon
models, single index models, low-rank CP models, and low-rank Tucker models.
Comprehensive results are developed on both the statistical and computational
limits for the signal tensor estimation. We find that high-dimensional latent
variable tensors are of log-rank; the fact explains the pervasiveness of
low-rank tensors in applications. Furthermore, we propose a polynomial-time
spectral algorithm that achieves the computationally optimal rate. We show that
the statistical-computational gap emerges only for latent variable tensors of
order 3 or higher. Numerical experiments and two real data applications are
presented to demonstrate the practical merits of our methods.
