# Statistical and computational rates in high rank tensor estimation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 8 Apr 2023.

## Builds on (most cited first, 24 of 24)

- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Generalized Canonical Polyadic Tensor Decomposition](https://mlsanity.com/paper/1808.07452/) (2018)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Multilinear tensor regression for longitudinal relational data](https://mlsanity.com/paper/1412.0048/) (2014)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [Multiway clustering via tensor block models](https://mlsanity.com/paper/1906.03807/) (2019)
- [Provable Sparse Tensor Decomposition](https://mlsanity.com/paper/1502.01425/) (2015)
- [Multilayer tensor factorization with applications to recommender systems](https://mlsanity.com/paper/1711.01598/) (2017)
- [Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality](https://mlsanity.com/paper/1811.05076/) (2018)
- [Isotonic regression with unknown permutations: Statistics, computation, and adaptation](https://mlsanity.com/paper/2009.02609/) (2020)
- [Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection](https://mlsanity.com/paper/2009.05870/) (2020)
- [On Learning High Dimensional Structured Single Index Models](https://mlsanity.com/paper/1603.03980/) (2016)
- [Supervised tensor decomposition with features on multiple modes](https://mlsanity.com/paper/1910.09499/) (2019)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations](https://mlsanity.com/paper/2111.04681/) (2021)

## Abstract (arXiv)

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.