A diverging number of frequencies in multi-frequency synchronization
In multi-frequency synchronization over $SO(2) \cong U(1)$, a signal $x \in U(1)^n$ is observed through $L$ frequencies, $$Y_k = \frac{\lambda}{n}\, x^{(k)}\bigl(x^{(k)}\bigr)^* + \frac{1}{\sqrt n}\, W^{(k)}, \qquad k = 1, \dots, L,$$ where $x^{(k)}$ is the entrywise $k$-th power of $x$ and $W^{(1)}, \dots, W^{(L)}$ are independent GUE noise matrices; over a finite group the frequencies are its irreducible representations (Perry, Wein, Bandeira and Moitra). The signal is uniform over the group. For $L = 1$ this is the spiked Wigner model: the top eigenvalue detects the signal above $\lambda = 1$, and for many dense priors nothing detects it below. Assuming the low-degree conjecture, Kireeva, Bandeira and Kunisky showed that for a constant number of frequencies no polynomial-time algorithm detects the signal below $\lambda = 1$, over $SO(2)$ or a finite group of constant size. Simulations of Gao and Zhao suggest that an approximate message passing algorithm beats $\lambda = 1$ when $n$ and $L$ are comparable.
Problem. Find a scaling $L = L_n$ for which some polynomial-time algorithm detects the signal reliably as $n \to \infty$ for all $\lambda > \lambda_{\mathrm{comp},L}$, for some $\lambda_{\mathrm{comp},L} < 1$.
Source: Kireeva, Open Problem 7 of Randomstrasse101, in “Detection in Multi-Frequency synchronization” (2024); Entry 4 of arXiv:2504.20539.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- ST — Statistics Theory
- Secondary
- PR
- Keywords
- group synchronization, Randomstrasse101, spiked random matrices, statistical-to-computational gaps
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2024,
author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2024},
year = {2025},
eprint = {2504.20539},
archivePrefix = {arXiv}
}
@misc{kireeva2024multifrequency,
author = {Kireeva, Anastasia and Bandeira, Afonso S. and Kunisky, Dmitriy},
title = {Computational lower bounds for multi-frequency group synchronization},
year = {2024},
eprint = {2406.03424},
archivePrefix = {arXiv}
}
@misc{perry2016pca,
author = {Perry, Amelia and Wein, Alexander S. and Bandeira, Afonso S. and Moitra, Ankur},
title = {Optimality and sub-optimality of {PCA} for spiked random matrices and synchronization},
year = {2016},
eprint = {1609.05573},
archivePrefix = {arXiv}
}
@inproceedings{gao2019multifrequency,
author = {Gao, Tingran and Zhao, Zhizhen},
title = {Multi-frequency phase synchronization},
booktitle = {International Conference on Machine Learning (ICML 2019)},
year = {2019}
}
Resolution claims
We study the computational phase transition in a multi-frequency group synchronization problem, where pairwise relative measurements of group elements are observed across multiple frequency channels and corrupted by Gaussian noise. Using the framework of \emph{low-degree polynomial algorithms}, we analyze the task of estimating the structured signal in such observations. We show that, assuming the low-degree heuristic, in synchronization models over …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-04 | Open → Solution claimed | The registry's curators | Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization v1 recorded from arXiv:2601.20522v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00063, "A diverging number of frequencies in multi-frequency synchronization", clopen.solutions.