Minimizing quadratic objective under orthogonality constraints

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.

• I should disappoint you somewhat: even when $d=1$, i.e., we are talking about minimizing the absolute value of the sum $\sum_k r_k\omega_k$ with real given $\omega_k$ and $r_k=\pm 1$, there is no much better option than to consider all choices of signs, so no "closed form" is really in sight and I doubt that your minimization procedure really converges to anything like the true minimizer unless $n$ is really small (2 or 3). Just test it in the following way: take any $\Omega$ for which the value $0$ can be attained and see how close you can come to it. :-) Dec 26, 2021 at 20:49
• @fedja Thanks for the reply. It does seem that a closed form solution may not be possible. Your discussion for the case of $d=1$ (and suppose $m=1$) reminds me of the balanced partition problem which can probably be solved by a deterministic algorithm. However, the case of $d=1$ and $m>1$ seems difficult. You're right, my minimization procedure is greedy and it surely does not converge to the true minimizer. Dec 26, 2021 at 21:31
• What are the typical values of $d,m,n$ you are considering? The only really easy case is $n=2$ and you can use it to do something but I would prefer to test it myself before recommending anything to avoid being similar to that rabbi from the sick cow story :-) Dec 26, 2021 at 22:12
• $n=2$ is not enough. Typical values are $d=2$ or $3$, $n=100$ and $m=10^4$. Dec 26, 2021 at 22:16
• "$n>2$ seems challenging." Exactly. As you noticed yourself, $m$ is not of great importance because we just need to minimize the sum of traces in which all matrices are $d\times d$. But $n=100$ is really a headache: I hoped for $n\approx 10$ :-(. Can you describe your current algorithm to use it as a benchmark to compare any alternatives to? Dec 27, 2021 at 1:24