Procrustes Problems on Random Matrices

This paper explores the intersection of geometry, optimization, and statistics to solve a classic problem: how do we best align two sets of noisy data points? Specifically, the authors investigate Procrustes problems—the task of finding the optimal rotation to match one matrix to another—when the data comes from random sources like social networks.

TL;DR

The researchers compare how different matrix norms (Frobenius, Spectral, and Robust) affect the alignment of random matrices and the power of subsequent statistical tests. Their most surprising finding is a "computational shortcut": the simple, closed-form Frobenius-norm solution often serves as an excellent proxy for much more complex, non-smooth optimization problems without sacrificing statistical accuracy.

What Problem Does This Paper Address?

In fields ranging from computer vision to neuroscience, researchers often need to compare two datasets that are "the same" but oriented differently. This is the Procrustes problem. Traditionally, we use the Frobenius norm because it has a beautiful, closed-form solution using Singular Value Decomposition (SVD).

However, the Frobenius norm is a "square-everything-and-sum" approach, making it highly sensitive to outliers. If your data has a few "bad" points (salt-and-pepper noise) or a specific structural shift (low-rank perturbation), the Frobenius alignment might be skewed. While Spectral and Robust norms are theoretically better at handling these specific types of noise, they are "non-smooth"—meaning they don't have simple formulas and require intense iterative optimization on the manifold of orthogonal matrices. This paper asks: is the extra math actually worth the effort for statistical inference?

Methods

The authors evaluate three primary alignment objectives:

1. Orthogonal Procrustes (Frobenius): The standard SVD-based approach.
2. Spectral Procrustes: Minimizes the largest singular value of the difference.
3. Robust Procrustes: Uses an $L_{2,1}$ norm (the sum of Euclidean lengths of column differences) to ignore outliers.

Because the Spectral and Robust versions are non-smooth and non-convex, the authors employ Riemannian optimization—specifically a mesh-adaptive direct search (LTMADS) via the Manopt.jl Julia package. They then apply these alignments to Random Dot Product Graphs (RDPGs), a popular model for social networks, using Adjacency Spectral Embedding (ASE) to turn graphs into matrices of coordinates.

Datasets

The study relies on carefully constructed synthetic benchmarks and simulations:

• 2D Point Sets: Toy examples with 10 points used to visualize how specific outliers "pull" the different alignment methods.
• Simulated Networks: Stochastic Block Models (SBMs) with $n=1000$ nodes and 3 communities.
• Noise Models: They introduced three distinct types of "errors" to test the limits of each norm:
• Diffuse: Standard Gaussian noise across all entries.
• Rank-one: A structural shift affecting the "angle" of the data.
• Salt-and-pepper: Replacing a subset of data points with entirely different values (outliers).

Key Insights and Ideas

• The Frobenius Shortcut: The most significant "aha moment" is that you can often use the rotation matrix found by the Frobenius method and simply plug it into the Spectral or Robust objective functions. This "approximate" test statistic performs nearly identically to the one found through grueling iterative optimization.
• Norm-Noise Matching: As expected, the Robust norm is the clear winner for salt-and-pepper noise. However, for diffuse (Gaussian) noise, the Frobenius norm remains the gold standard for statistical power.
• Spectral Norm Weakness: Surprisingly, the Spectral norm performed poorly in several network hypothesis tests. Because it only looks at the single direction of maximum variation, it can miss subtle differences spread across multiple dimensions that the Frobenius norm captures.

Key Results

• Robustness to Outliers: In 2D tests with heavy outliers, the Robust Procrustes recovered the true rotation angle with an error of $10^{-11}$, while the Frobenius method was off by $10^{-2}$.
• Statistical Power: In network hypothesis testing, the Robust norm showed significantly higher power (the ability to correctly reject a false null hypothesis) when "salt-and-pepper" noise was present.
• Computational Efficiency: Using the Frobenius "shortcut" to approximate Spectral or Robust statistics was roughly 15% faster than full Riemannian optimization for a single test. In large-scale bootstrapping scenarios involving tens of thousands of alignments, this difference becomes substantial.

Limitations and Future Work

The authors acknowledge that they used local solvers. Because these optimization problems are non-convex, there is no absolute guarantee they found the "global" best alignment, though their results suggest the local solutions are quite effective.

Future research directions include:

• Global Optimality: Developing solvers (perhaps based on Semidefinite Programming) that can certify they've found the absolute best alignment.
• High-Dimensional Scaling: Testing how these methods hold up as the number of features ($d$) and nodes ($n$) grow to "big data" scales.
• Theoretical Power Analysis: Moving beyond simulations to provide formal proofs for why the Frobenius shortcut works so well in random matrix settings.

@misc{jasa2025procrustes,
  author = {Hajg Jasa and Ronny Bergmann and Christian Kümmerle and Avanti Athreya and Zachary Lubberts},
  title = {{Procrustes Problems on Random Matrices}},
  year = {2025},
  eprint = {2510.05182},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.05182},
  howpublished = {arXiv},
}