2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. :-) $\endgroup$
    – fedja
    Dec 26, 2021 at 20:49
  • $\begingroup$ @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. $\endgroup$
    – no-one
    Dec 26, 2021 at 21:31
  • $\begingroup$ 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 :-) $\endgroup$
    – fedja
    Dec 26, 2021 at 22:12
  • $\begingroup$ $n=2$ is not enough. Typical values are $d=2$ or $3$, $n=100$ and $m=10^4$. $\endgroup$
    – no-one
    Dec 26, 2021 at 22:16
  • 1
    $\begingroup$ "$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? $\endgroup$
    – fedja
    Dec 27, 2021 at 1:24

1 Answer 1

0
$\begingroup$

This is a special case of the little Grothendieck problem.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.