A critical number of frequencies for weak recovery in multi-frequency synchronization
In multi-frequency synchronization over $SO(2) \cong U(1)$, a signal $x \in U(1)^n$, uniform over the group, 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. A Hermitian estimator $X = X(Y_1, \dots, Y_L)$ achieves weak recovery if $\mathbb{E}\, \langle X, xx^* \rangle / (\|X\|_F \, \|xx^*\|_F) \ge c$ for a constant $c > 0$. For $L = 1$ the top eigenvector achieves weak recovery above the spectral (BBP) threshold $\lambda = 1$, and nothing does below it. Detecting the signal against pure noise is easy once $L \to \infty$: the Frobenius norms of the $Y_k$ do so for every constant $\lambda > 0$. For weak recovery, assuming the low-degree conjecture, any algorithm needs time $\exp(n^{\Omega(1)})$ when $\lambda < 1$ and $L = n^{o(1)}$ (Li). Simulations of Gao and Zhao for $n = 100$ and $L = 32$ suggest that an approximate message passing algorithm beats $\lambda = 1$.
Problem. Is there a critical scaling $\mathscr{L}_n$ such that polynomial-time algorithms can achieve weak recovery for some $\lambda < 1$ if and only if $L \gg \mathscr{L}_n$? If so, determine it.
Source: Li, Remark 1.7 of “Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization” (arXiv:2601.20522, 2026).
Imported from arxiv.org/abs/2601.20522.
Classification
- Primary
- ST — Statistics Theory
- Secondary
- PR
- Keywords
- group synchronization, low-degree polynomials, spiked random matrices, statistical-to-computational gaps
- Literature checked
- Oct. 4, 2026 by clemens-admin
References
@misc{li2026multifrequency,
author = {Li, Zhangsong},
title = {Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization},
year = {2026},
eprint = {2601.20522},
archivePrefix = {arXiv}
}
@misc{li2026contiguity,
author = {Li, Zhangsong},
title = {Algorithmic Contiguity from Low-Degree Heuristic {II}: Predicting Detection-Recovery Gaps},
year = {2026},
eprint = {2604.17410},
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}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00065, "A critical number of frequencies for weak recovery in multi-frequency synchronization", clopen.solutions.