Answers to follow-up
Thank you again for your additional questions which we hope to clarify in the following.
Let's start by recalling the two problems (GGA) and (PW). In both cases, we consider two point clouds written into matrices, namely $X = (x_1 | x_2 | .... | x_n)$ and $Y = (y_1 | y_2 | .... | y_n)$ with $x_i, y_i \in \mathbb{R}^d$. In this setting, (GGA) amounts to solving the minimization problem
$
P^*_{GGA} \in \mathrm{argmin}_{P \in \mathcal{S}_n} \Vert X^\top X P - P Y^\top Y \Vert_F^2
$
while (PW) amounts to solving
$
(P^*_{PW}, Q^*_{PW}) \in \mathrm{argmin}_{(P,Q) \in \mathcal{S}_n \times \mathcal{O}_d} \Vert QX - YP \Vert_F^2
$
Lemma 3 tells us that in (PW), it suffices to retrieve either $P^*_{PW}$ or $Q^*_{PW}$ to retrieve a very good guess of its respective counterpart.
If we understand you correctly, the key to both of your questions lies in the following "soft reformulation" of the optimization problem which was performed by (Grave, Joulin, Berthet, 2018) in their subsection **Convex relaxation**. The idea is to consider the following problem which is equivalent to (PW):
$
\text{max}_{P \in \mathcal{S}_n} \max_Q \text{tr}(Q X P^T Y^T)
$
One has
$
\max_Q \text{tr}(Q X P^T Y^T) = \Vert X P^T Y^T \Vert_\star
$
where
$\Vert A \Vert_\star$
denotes the trace norm (or nuclear norm) of a matrix
$A$.
If we put the singular values
$\sigma_1, ..., \sigma_m$
of
$A$
into a vector
$v := (\sigma_1, ..., \sigma_m)$,
then
$\Vert A \Vert_\star= \sum_i \sigma_i = \Vert v \Vert_1$.
Since
$\Vert A \Vert_F = \sqrt{\sum_i \sigma_i^2} = \Vert v \Vert_2$,
one can argue, using norm equivalence in
$ \mathbb{R}^m$,
that the problems
$ \max_P \Vert X P^T Y^T \Vert_\star $
and
$ \max_P \Vert X P^T Y^T \Vert_F^2 $
are very similar. [Note: We don't know a result to quantify how similar the solutions are, this is why this whole "soft reformulation" is more about giving intuition than providing rigorous results.]
Developing the square in $ \max_P \Vert X P^T Y^T \Vert_F^2 $ and omiting constant terms, this problem is further equivalent to
$ \max_P \mathrm{tr}( Y P X^T X P^T Y^T ) = \text{max}_P \mathrm{tr}( X^T X P^T Y^T Y P) $
Rewriting this as the minimum of the squared norm of a matrix distance, one obtains exactly (GGA). This whole reformulation process can also be reversed to move back, from (GGA) to (PW).
Now, let's move to answering your concrete questions:
**(1) about Lemma 1**
It is true that in order to infer $Q^*$, one needs a good estimate of $P^*$. To obtain this estimate, we use the above "soft reformulation" and first solve (GGA) which is agnostic to $Q^*$. This is done via convex relaxation of $\mathcal{S}_n$ to the set of doubly stochastic matrices, followed by Frank-Wolve optimisation. This procedure is what Grave et al. call the initialisation to their algorithm; it is also the initialisation to our Ping-Pong steps. The doubly stochastic matrix obtained at convergence of Frank-Wolfe if our initial guess of $P^*$. Our one-step analysis of the algorithm lets us hope that this is indeed a good guess in general.
**(2) about GGA**
You are right that there is no retrieval of $Q^*$ in GGA. Our hope is that the "soft reformulation" can give a good idea where this $Q^*$ is hidden in the process. Since the geometric graph in GGA only depends on the scalar products between the vectors in $X$ and $Y$, our proof of lemma 1 explains in detail how an orthogonal transformation between the point clouds emerges when doing the problem reformulation (GGA) $\to$ (PW).