Let $B$ be a $d \times d$ psd matrix and let $W$ be a $N \times d$ matrix. For any $N \times d$ matrix $A$, define $F(A) := \|B-A^\top W - W^\top A\|_F^2$ and $G(A) := \|A^\top W\|^2_F + \|W A^\top\|_F^2$. Let $\mathcal Q \subseteq \mathbb R^{N \times d}$ be the set of all $A$ which minimize $F$.
Question. How to compute $u := \inf_{A \in \mathcal Q} G(A)$ and $v := \sup_{A \in \mathcal Q} G(A)$ as a function of $B$ and $W$ ?
Notes
- In case analytical formulae are not available, I'm fine with general nontrivial upper-bounds (resp. lower-bounds) for $v$ (resp. for $u$).
- I'm particularly interested in the case $N < d$.
Partial result for the case $N \ge d$
For example, in the case $N \ge d$, we can construct $A \in \mathcal Q$ such that $A^\top W =B/2$. To see this, let $W=V^\top S U$ be a singular-value decomposition and choose $A \in \mathbb R^{N \times d}$ such that $2SV^\top A=U^\top B$, from which $W^T A =B/2 = A^\top W$ and so $F(A) = 0$. Further, one gets $$ v \ge G(A) = \|A^\top W\|_F^2 + \|WA^\top\|_F^2 \ge \|WA^\top\|_F^2 \ge \frac{\|B\|_F^2}{4}. $$
This doesn't really solve the problem even in the case $N \ge d$, but maybe the core idea might be useful for obtaining a more satisfying answer / bounds.