Asymptotic mutual information in quadratic estimation problems over compact groups

Abstract

Motivated by applications to group synchronization and quadratic assignment on random data, we study a general problem of Bayesian inference of an unknown ``signal'' belonging to a high-dimensional compact group, given noisy pairwise observations of a featurization of this signal. We establish a quantitative comparison between the signal-observation mutual information in any such problem with that in a simpler model with linear observations, using interpolation methods. For group synchronization, our result proves a replica formula for the asymptotic mutual information and Bayes-optimal mean-squared-error. Via analyses of this replica formula, we show that the conjectural phase transition threshold for computationally-efficient weak recovery of the signal is determined by a classification of the real-irreducible components of the observed group representation(s), and we fully characterize the information-theoretic limits of estimation in the example of angular/phase synchronization over $SO(2)$/$U(1)$. For quadratic assignment, we study observations given by a kernel matrix of pairwise similarities and a randomly permutated and noisy counterpart, and we show in a bounded signal-to-noise regime that the asymptotic mutual information coincides with that in a Bayesian spiked model with i.i.d. signal prior.

References in corpus (22)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Phase diagram of glassy systems in an external field
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• General maximum likelihood empirical Bayes estimation of normal means
• Nonconvex phase synchronization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Phase Transitions in Semidefinite Relaxations
• Near-optimal bounds for phase synchronization
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Message-passing algorithms for synchronization problems over compact groups
• A note on classical ground state energies
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Estimation in the spiked Wigner model: A short proof of the replica formula
• Minimax rates in permutation estimation for feature matching
• A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models
• Statistical limits of correlation detection in trees
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• Sharp regret bounds for empirical Bayes and compound decision problems
• Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks
• The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
• Exact Minimax Optimality of Spectral Methods in Phase Synchronization and Orthogonal Group Synchronization