The following problem is motivated from Generalized Procrustes Analysis. I am wondering if it is possible to obtain a closed form minimizer (which may involve SVD or some other decomposition of a known matrix).
Given a matrix $\Omega \in \Bbb R^{nd \times m}$,
$$\begin{array}{ll} \underset{R_1, \dots, R_n \in \mathbb{R}^{d \times d}}{\text{minimize}} & \left\| \begin{bmatrix} R_1 & R_2 & \cdots & R_n \end{bmatrix} \Omega \, \right\|_{\text{F}}^2\\ \text{subject to} & R_i^T R_i = I_d, \quad \forall i \in [n]\end{array}$$
In words, $R_i$ is a $d \times d$ real orthogonal matrix for all $i$.
It seems that a closed form solution may not be possible. I would really appreciate pointers to approximation algorithms with guarantees.
Case of $n=1$. The problem is reduced to $$\begin{array}{ll} \underset{R_1\in \mathbb{R}^{d \times d}}{\text{minimize}} & \left\| R_1 \Omega \, \right\|_{\text{F}}^2\\ \text{subject to} & R_1^T R_1 = I_d\end{array}$$
In this case, $\left\| R_1 \Omega \, \right\|_{\text{F}}^2 = \text{tr}(R_1\Omega\Omega^TR_1^T) = \text{tr}(R_1^TR_1\Omega\Omega^T) = \text{tr}(\Omega\Omega^T)$. So, any orthogonal $R_1$ would minimize the objective.
Case of $n=2$. The problem is reduced to $$\begin{array}{ll} \underset{R_1, R_2 \in \mathbb{R}^{d \times d}}{\text{minimize}} & \left\| \begin{bmatrix} R_1 & R_2 \end{bmatrix} \Omega \, \right\|_{\text{F}}^2\\ \text{subject to} & R_i^T R_i = I_d, \quad \forall i \in [2]\end{array}$$
Write $\Omega$ as $\begin{bmatrix} \Omega_1\\ \Omega_2 \end{bmatrix}$ where $\Omega_i \in \mathbb{R}^{d \times m}$. Then the objective is
$$\begin{align} &\left\|R_1\Omega_1 + R_2\Omega_2\right\|_F^2\\ &= \text{tr}((R_1\Omega_1 + R_2\Omega_2)(R_1\Omega_1 + R_2\Omega_2)^T)\\ &= \text{tr}(R_1\Omega_1\Omega_1^TR_1^T + 2R_1\Omega_1\Omega_2^TR_2^T + R_2\Omega_2\Omega_2^TR_2^T)\\ &= \text{tr}(\Omega_1\Omega_1^T) + 2\text{tr}(R_1\Omega_1\Omega_2^TR_2^T) + \text{tr}(\Omega_2\Omega_2^T) \end{align}$$
Using the SVD $\Omega_1\Omega_2^T = U\Sigma V^T$, the objective is reduced to
$$\begin{align} &= \text{tr}(\Omega_1\Omega_1^T) + \text{tr}(\Omega_2\Omega_2^T) + 2\text{tr}(R_1U\Sigma V^TR_2^T) \\ &= \text{tr}(\Omega_1\Omega_1^T) + \text{tr}(\Omega_2\Omega_2^T) + 2\text{tr}(V^TR_2^TR_1U\Sigma) \end{align}$$
This is minimized when $V^TR_2^TR_1U = -I$ i.e. $R_1U = -R_2V$. So, the optimal solution is, choose any orthogonal $R_1$ and then $R_2 = -R_1UV^T$.
Idea for general $n$.
As in the case of $n=2$ we write $\Omega$ as $\begin{bmatrix} \Omega_1\\ \vdots\\ \Omega_n \end{bmatrix}$ where $\Omega_i \in \mathbb{R}^{d \times m}$. Then the objective is reduced to
$$\begin{align} \sum_{i=1}^{n}\text{tr}(\Omega_i\Omega_i^T) + 2\sum_{i=1}^{n}\sum_{j=i+1}^{n}\text{tr}(R_i\Omega_i\Omega_j^TR_j^T) \end{align}$$
Then, using SVD, $\Omega_i\Omega_j^T = U_{ij}\Sigma_{ij}V_{ij}^T$. As in the case of $n=2$, the objective is then reduced to,
$$\begin{align} \sum_{i=1}^{n}\text{tr}(\Omega_i\Omega_i^T) + 2\sum_{i=1}^{n}\sum_{j=i+1}^{n}\text{tr}(V_{ij}^TR_j^TR_iU_{ij}\Sigma_{ij}) \end{align}$$
It is minimized when $V_{ij}^TR_j^TR_iU_{ij} = -I$ i.e. $R_iU_{ij} +R_jV_{ij} = 0$ for all $i,j \in [n], i \neq j$. So one would like to solve this system of equations for $R_i$'s. However, in general, it may have no solution.
