Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.20522
curl -X POST /api/v1/records/arxiv/2601.20522/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.20522/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'