Detection in Multi-Frequency synchronization (problems 7-8)

In the study of average-case complexity, one is often interested in the critical threshold of the signal-to-noise ratio at which a problem becomes tractable. In this post, we will consider a multi-frequency synchronization problem, where one obtains noisy measurements of the relative alignments of the signal elements through multiple frequency channels. We are interested whether it becomes possible to detect the signal using a time-efficient algorithm at a lower signal-to-noise ratio compared to the single-frequency model.

Let us define the synchronization problem more formally. In a general synchronization problem over a group $G$, one aims to recover a group-valued signal $g = (g_{1}, \dots, g_{n})\in G^n$ from its noisy pairwise information on $g_{k}g_{j}^{-1}$. One way to model such observations is through receiving a function of $g_{k}g_{j}^{-1}$ corrupted with additive Gaussian noise \(Y_{kj}= f(g_{k}g_{j}^{-1})+W_{kj}, \quad W_{kj}\sim\mathcal{N}(0, 1).\) In this post, we will focus on a setting where measurements are available for all pairs $(j,k)$.

Motivated by the Fourier decomposition of a non-linear objective of the non-unique games problem (Bandeira et al., 2020), we consider the model as receiving measurements through several frequency channels. For example, for $G = U(1) = \{e^{i\varphi}, \varphi \in [0, 2\pi)\}$, we consider measurements of the following form: \(\\ \begin{align} \begin{cases} Y_1 & =\frac{\lambda}{n} x x^*+\frac{1}{\sqrt{n}} W^{(1)}, \\ Y_2 & =\frac{\lambda}{n} x^{(2)}\left(x^{(2)}\right)^*+\frac{1}{\sqrt{n}} W^{(2)}, \\ & \vdots \\ Y_L & =\frac{\lambda}{n} x^{(L)}\left(x^{(L)}\right)^*+\frac{1}{\sqrt{n}} W^{(L)}, \end{cases}. \end{align} \\\)

where $W^{(1)},\dots,W^{(L)}$ are independent matrices, and $x^{(k)} = (x_1^k, \dots, x_n^k)$ denotes entrywise power. This case corresponds to the angular synchronization, where the objective is to determine phases $\varphi_1, \dots, \varphi_n \in [0, 2\pi)$ from their noisy relative observation $\varphi_k - \varphi_j \mod 2 \pi$, and equivalent to the synchronization over $SO(2)$, as $SO(2) \cong U(1)$.

In the general case of compact groups, we consider the Peter-Weyl decomposition instead. Informally, in this case, the Fourier modes correspond to irreducible representations, and each pairwise measurement corresponding to an irreducible representation $\rho$ is a block matrix with blocks given by \begin{equation} Y_{k j}^\rho=\frac{\lambda}{n} \rho\left(g_k\right) \rho\left(g_j^{-1}\right)+\frac{1}{\sqrt{n}} W_{k j}^{(\rho)} \text { for each } \rho \in \Psi, \end{equation}

The single-frequency model (i.e., when $L=1$) reduces to the Wigner spiked matrix model. In this model, the celebrated BBP transition (Baik et al., 2005) postulates that above a critical value $\lambda \ge \lambda^* = 1$, detection is possible based on the top eigenvalue, while below this threshold, the top eigenvalue does not provide reliable information on the presence of the signal as $n$ grows to infinity. Moreover, for a variety of dense priors on signal $x$, this procedure is optimal in the sense that no algorithm can detect the signal reliably below the spectral threshold, $\lambda^*=1$, including algorithms with no constraints on the runtime (Perry et al., 2016).

Does the situation change for the multi-frequency model? For simplicity, let us assume that the signal $x$ is sampled uniformly from $L$-th roots of unity, $x \sim Unif(\{e^{2\pi i k / L}\}_{k=0}^{L-1})$. This corresponds to synchronization over the cyclic group $\mathbb Z / L \mathbb Z$. In this case, (Perry et al., 2016) showed that the statistical threshold is $\lambda_{stat}=\Theta(\log L / L)$, i.e., below this threshold it is impossible to detect the signal, while above the threshold, there exists an inefficient algorithm for this task. The authors give upper and lower bounds on $\lambda_{\text{stat}}$ with exact constants, and the upper bound is lower than the spectral threshold for a sufficiently large number of frequencies, namely, $L\ge 11$.

From the computational point of view, in (Kireeva et al., 2024), it was shown that assuming the low-degree conjecture, no polynomial-time algorithm can detect the signal below the spectral threshold regardless of receiving additional information through additional channels. This result applies to the setting when the number of frequencies is constant compared to the dimension $n$ and when the signal is sampled uniformly from $SO(2)$ or any finite group of constant size. Combining this result with the optimality of PCA for the single-frequency model suggests that receiving only a constant number of additional frequencies does not give sufficient information to lower the computational threshold. This opens up an intriguing question: how many additional frequencies are required to make detection possible below the spectral threshold using an efficient algorithm? We can formulate the following open problem.

Open Problem 7 (Diverging number of frequencies in the multi-frequency model)

Consider synchronization model over $SO(2)$ or synchronization model over a finite group, where the signal $x$ is sampled uniformly over group elements. Find a scaling $L= L_n$ of number of frequencies such that there exists a polynomial-time algorithm that can detect the signal reliably for all $\lambda>\lambda_{\text{comp}, L}$ for some $\lambda_{\text{comp}, L}<1$ as $n\to\infty$.

There is empirical evidence supporting the conjecture that, as $L$ diverges, the computational threshold becomes lower than the spectral threshold: numerical simulations in (Gao & Zhao, 2019) provide evidence that the variant of AMP with a carefully performed initialization can surpass the threshold when the dimension $n$ and the number of frequencies $L$ are comparable.

In the computationally hard regime, we may also hope that there exists a sub-exponential algorithm whose runtime possibly depends on the signal strength. Such a tradeoff was observed in the sparse PCA problem (Ding et al., 2023). For the synchronization model over finite groups, (Perry et al., 2016) proposed an algorithm for detecting the signal that works in the entire computationally hard regime. This algorithm involves maximizing a certain test function over all possible solutions $g \in G^n$ and thus has an exponential runtime.

Open Problem 8 (Sub-exponential algorithm in the hard regime)

Consider synchronization model over $SO(2)$ or synchronization model over a finite group, where the signal $x$ is sampled uniformly over group elements. Fix number of frequencies $L$ that does not depend on $n$. In the computationally hard regime, i.e., when $\lambda \in (\lambda_{\text{stat}}, 1)$, does there exist a sub-exponential algorithm, i.e., an algorithm running in time $\exp{n^\delta}$ for some $\delta < 1$, that can detect the signal reliably as $n\to\infty$?

References

1. Bandeira, A. S., Chen, Y., Lederman, R. R., & Singer, A. (2020). Non-unique games over compact groups and orientation estimation in cryo-EM. Inverse Problems, 36(6), 064002.
2. Baik, J., Arous, G. B., & Péché, S. (2005). Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices. The Annals of Probability, 33(5), 1643–1697.
3. Perry, A., Wein, A. S., Bandeira, A. S., & Moitra, A. (2016). Optimality and sub-optimality of PCA for spiked random matrices and synchronization. ArXiv Preprint ArXiv:1609.05573.
4. Kireeva, A., Bandeira, A. S., & Kunisky, D. (2024). Computational lower bounds for multi-frequency group synchronization. ArXiv Preprint ArXiv:2406.03424.
5. Gao, T., & Zhao, Z. (2019). Multi-Frequency Phase Synchronization. International Conference on Machine Learning.
6. Ding, Y., Kunisky, D., Wein, A. S., & Bandeira, A. S. (2023). Subexponential-time algorithms for sparse PCA. Foundations of Computational Mathematics, 1–50.