I have discussed something along these lines with the lead author of the paper you cite and I currently think that such problems are hard, maybe intractably so in general, but sometimes feasible when you have enough structure to give you extra hints. Below are some notes on the topic which I hope will be of some use.
Consider a finite graph $G = (V,E)$, a compact group $\mathcal{G}$, and let $f: E \times \mathcal{G} \rightarrow \mathbb{R}$. The synchronization problem corresponding to $G$, $\mathcal{G}$, and $f$ is to find a potential $g: V \rightarrow \mathcal{G}$ minimizing
$$\sum_{(j,k) \in E} f((j,k), g_j g_k^{-1}).$$
An interesting variant of the synchronization problem arises upon requiring $g(V) \subseteq \mathcal{H} \subset \mathcal{G}$ for $| \mathcal{H} | \ll | V |$.
Your problem seems to be essentially of this form. More generally, such problems arise in practice when (for instance) one has multiple sensors in fixed spatial positions giving different information about a common object that must be synchronized.
As an example, let
- $G = K_N$ (i.e., the complete graph on $N$ vertices);
- $\mathcal{H} \subset \mathcal{G} = S_L$ be the set of coherent block permutations (see appendix below) of the form $\sigma^\circledcirc_{L_1,\dots,L_M}$ for some fixed $\{L_m\}_{m=1}^M$ that is completely unknown apart from the implicit constraint $L = \sum_{m=1}^M L_m$ (and perhaps $M$);
- $f((j,k), (\sigma_j)^\circledcirc_{L_1,\dots,L_M} ((\sigma_k)^\circledcirc_{L_1,\dots,L_M})^{-1}) = -\langle y_j, \rho((\sigma_j)^\circledcirc_{L_1,\dots,L_M}((\sigma_k)^\circledcirc_{L_1,\dots,L_M})^{-1})^* y_k \rangle$, where $\rho : S_L \rightarrow GL(L)$ is the natural permutation representation: $\rho(\sigma)_{ab} := \delta_{b,\sigma(a)}$.
At this point it is probably best to unpack the preceding paragraph by furnishing a somewhat more concrete point of view that leads to it. Suppose that we have a fixed set $\{x^{(m)}\}_{m=1}^M$ of vectors with $\dim x^{(m)} = L_m$. Our only piece of information about this set is the value of $L = \sum_{m=1}^M L_m$. We are given $N$ samples of the form $y_j = R_j (x^\oplus + \xi_j^\oplus)$, where $R_j := \rho((\sigma_j)^\circledcirc_{L_1,\dots,L_M})^*$, $x^\oplus := \oplus_m x^{(m)}$ and the implied $\xi_j^{(m)}$ are random variables that are IID w/r/t $j$. That is, the $x^{(m)}$ have noise added and are then shuffled. To unshuffle the $y_j$, we must find the coherent block permutations that minimize
$$-\sum_{j,k} \langle R_j^* y_j, R_k^* y_k \rangle = - \text{Tr} \left( \begin{pmatrix} R_1 \\ \vdots \\ R_N \end{pmatrix} \begin{pmatrix}R_1^* & \dots & R_N^*\end{pmatrix} \begin{pmatrix} y_1 \\ \vdots \\ y_N \end{pmatrix} \begin{pmatrix}y_1^* & \dots & y_N^*\end{pmatrix} \right ) \equiv - \text{Tr}(RY) $$
where we introduce obvious shorthands on the RHS.
This problem presents interrelated difficulties beyond those encountered in the synchronization problems studied in the literature: first, $\mathcal{G} = S_L$ is large but discrete; and second, the subset of values that a potential can take is complicated.
Appendix
Let $S_M$ denote the symmetric group on $M$ elements and write $\sigma = (\sigma(1),\dots,\sigma(M)) \in S_M$. Now for $L := \sum_{m=1}^M L_m$ and $\tau^{(m)} \in S_{L_m}$ for $m \in [M]$, define the (permutation) operad composition (cf. section 2.2.20 of Leinster's book) $\circ : S_M \times \prod_{m=1}^M S_{L_m} \rightarrow S_L$ as follows:
$$\circ : (\sigma, \tau^{(1)}, \dots, \tau^{(M)}) \mapsto \sigma \circ (\tau^{(1)}, \dots, \tau^{(M)}),$$
where
$$\sigma \circ (\tau^{(1)}, \dots, \tau^{(M)})({\textstyle \sum_{m<n} L_m} + \ell) := \sum_{m<\sigma(n)} L_{\sigma^{-1}(m)} + \tau^{(n)}(\ell).$$
For notational convenience, write $1_M := (1,\dots,M)$ for the identity of $S_M$. The block permutation $\sigma_{L_1,\dots,L_M} \in S_L$ is (cf. section 1.2 of Markl, Shnider and Stasheff)
$$\sigma_{L_1,\dots,L_M} := \sigma \circ (1_{L_1}, \dots, 1_{L_M}).$$
For example, $(4,2,1,3)_{4,3,3,2} = (4,2,1,3) \circ (1_4,1_3,1_3,1_2) = (9,10,11,12,4,5,6,1,2,3,7,8)$. We shall write $S_{L_1,\dots,L_M} \subseteq S_L$ for the set of block permutations of the form above. It is easy to show the following
Proposition. $(\sigma_{L_1,\dots,L_M})^{-1} = (\sigma^{-1})_{L_{\sigma^{-1}(1)},\dots,L_{\sigma^{-1}(M)}}$. $\Box$
Define the coherent block permutation
$$\sigma^\circledcirc_{L_1,\dots,L_M} := \sigma \circ (1_{L_{\sigma(1)}}, \dots, 1_{L_{\sigma(M)}}) = \sigma_{L_{\sigma(1)},\dots,L_{\sigma(M)}}.$$
For example, $(4,2,1,3)^\circledcirc_{4,3,3,2} = (4,2,1,3) \circ (1_2,1_3,1_4,1_3) = (11,12,5,6,7,1,2,3,4,8,9,10)$. We shall write $S^\circledcirc_{L_1,\dots,L_M} \subseteq S_L$ for the set of block permutations of the form above. The crucial property of $S^\circledcirc_{L_1,\dots,L_M}$ is that its elements permute the intervals $\{\sum_{m'<m} L_m + 1,\dots,\sum_{m' \le m} L_m\}$ of $[L]$, or more formally that the functions $m \mapsto \sum_{m'<m} L_m + 1$ and $m \mapsto \sum_{m' \le m} L_m$ are equivariant with respect to the natural action of $S_M$ on $[M]$ and the corresponding action by coherent block permutations on $[L]$. $S^\circledcirc_{L_1,\dots,L_M}$ has more complicated algebraic strcture than $S_{L_1,\dots,L_M}$: to wit, we have the following
Proposition. $\sigma^\circledcirc_{L_1,\dots,L_M} = ((\sigma^{-1})_{L_1,\dots,L_M})^{-1}$. $\Box$
