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.

somethingbut I would prefer to test it myself before recommending anything to avoid being similar to that rabbi from the sick cow story :-) $\endgroup$2more comments