Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915758874820608 |
|---|---|
| author | Li, Zhangsong |
| author_facet | Li, Zhangsong |
| contents | 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 the circle group $\mathsf{SO}(2)$, a simple spectral method is computationally optimal among all polynomial-time estimators when the number of frequencies satisfies $L=n^{o(1)}$. This significantly extends prior work \cite{KBK24+}, which only applied to a fixed constant number of frequencies. Together with known upper bounds on the statistical threshold \cite{PWBM18a}, our results establish the existence of a \emph{statistical-to-computational gap} in this model when the number of frequencies is sufficiently large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20522 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization Li, Zhangsong Statistics Theory Data Structures and Algorithms Probability 68Q87, 68Q17 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 the circle group $\mathsf{SO}(2)$, a simple spectral method is computationally optimal among all polynomial-time estimators when the number of frequencies satisfies $L=n^{o(1)}$. This significantly extends prior work \cite{KBK24+}, which only applied to a fixed constant number of frequencies. Together with known upper bounds on the statistical threshold \cite{PWBM18a}, our results establish the existence of a \emph{statistical-to-computational gap} in this model when the number of frequencies is sufficiently large. |
| title | Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization |
| topic | Statistics Theory Data Structures and Algorithms Probability 68Q87, 68Q17 |
| url | https://arxiv.org/abs/2601.20522 |