Random tensor isomorphism under orthogonal and unitary actions

We study the problem of testing whether two tensors in ${\mathbb{R}}^{\mathrm{\ell }}\otimes {\mathbb{R}}^m\otimes {\mathbb{R}}^n$ are isomorphic under the natural action of orthogonal groups $\mathbf{\text{O}}(\mathrm{\ell },\mathbb{R})\times \mathbf{\text{O}}(m,\mathbb{R})\times \mathbf{\text{O}}(n,\mathbb{R})$, as well as the corresponding question over $\mathbb{C}$ and unitary groups. These problems naturally arise in several areas, including graph and tensor isomorphism (Grochow–Qiao, SIAM J. Comp. '21), scaling algorithms for orbit closure intersections (Allen-Zhu–Garg–Li–Oliveira–Wigderson, STOC '18), and quantum information (Liu–Li–Li–Qiao, Phys. Rev. Lett. '12). We study average-case algorithms for orthogonal and unitary tensor isomorphism, with one random tensor where each entry is sampled uniformly independently from a sub-Gaussian distribution, and the other arbitrary. For the algorithm design, we develop algorithmic ideas from the higher-order singular value approach into polynomial-time exact (algebraic) and approximate (numerical) algorithms with rigorous average-case analyses. Following (Allen-Zhu–Garg–Li–Oliveira–Wigderson, STOC '18), we present an algorithm for a gapped version of the orbit distance approximation problem. For the average-case analysis, we work from recent progress in random matrix theory on eigenvalue repulsion of sub-Gaussian Wishart matrices (Christoffersen–Luh–O’Rourke–Shearer and Han, arXiv '25) by extending their results from side lengths of Wishart matrices linearly related to polynomially related.