High-Dimensional Procrustes Matching via Tree Counts

What the math gives to ML

The paper introduces a polynomial-time permutation-recovery method based on weighted counts of wide rooted trees, succeeding in a high-dimensional Gaussian matching regime where pairwise distances or Procrustes scores are insufficient. The transferable asset is a structured high-order similarity feature: tree contractions aggregate many weak coordinate-level correlations while remaining insensitive to an unknown global orthogonal transformation. This suggests a permutation-equivariant alignment layer for matching two sets of embeddings, especially cross-modal or cross-domain representations, with tree depth and width controlling the bias-variance tradeoff. The main engineering risk is computational cost, so the first implementation should use a small family of shallow trees and randomized tensor contractions rather than enumerate all trees.