# Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 8 Nov 2021.

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

- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [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)
- [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)
- [Optimal Estimation and Completion of Matrices with Biclustering Structures](https://mlsanity.com/paper/1512.00150/) (2015)
- [Optimal Rates of Statistical Seriation](https://mlsanity.com/paper/1607.02435/) (2016)
- [Estimation of Monge Matrices](https://mlsanity.com/paper/1904.03136/) (2019)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Nonparametric, tuning-free estimation of S-shaped functions](https://mlsanity.com/paper/2107.07257/) (2021)
- [Low Permutation-rank Matrices: Structural Properties and Noisy Completion](https://mlsanity.com/paper/1709.00127/) (2017)

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

- [Statistical and computational rates in high rank tensor estimation](https://mlsanity.com/paper/2304.04043/) (2023)
- [Finite-Sample Inference for Sparsely Permuted Linear Regression](https://mlsanity.com/paper/2601.14872/) (2026)

## Abstract (arXiv)

We consider the problem of structured tensor denoising in the presence of unknown permutations. Such data problems arise commonly in recommendation system, neuroimaging, community detection, and multiway comparison applications. Here, we develop a general family of smooth tensor models up to arbitrary index permutations; the model incorporates the popular tensor block models and Lipschitz hypergraphon models as special cases. We show that a constrained least-squares estimator in the block-wise polynomial family achieves the minimax error bound. A phase transition phenomenon is revealed with respect to the smoothness threshold needed for optimal recovery. In particular, we find that a polynomial of degree up to (m-2)(m+1)/2 is sufficient for accurate recovery of order-m tensors, whereas higher degree exhibits no further benefits. This phenomenon reveals the intrinsic distinction for smooth tensor estimation problems with and without unknown permutations. Furthermore, we provide an efficient polynomial-time Borda count algorithm that provably achieves optimal rate under monotonicity assumptions. The efficacy of our procedure is demonstrated through both simulations and Chicago crime data analysis.