  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.
