2
$\begingroup$

The orthogonal Procrustes problem finds an orthogonal matrix $\Omega$ minimizing the Procrustes objective:

$$ \min_\Omega ||\Omega A - B||_F, \quad \Omega^\top \Omega = I $$

It is well known that the solution is $\Omega^* = U V^\top$, where $U, V$ come from the SVD of $BA^\top$ (ie $U \Sigma V^\top = B A^\top$).

I think I understand why this is the solution, but what is unclear to me is why computing an unconstrained minimizer and then projecting it onto the Stiefel manifold (ie the space of orthogonal matrices) does not work. In other words, what about the geometry of the Stiefel manifold makes it incorrect to compute the least-squares solution $M = B A^\top (A A^\top)^{-1}$ then choose $\Omega = \tilde{U} \tilde{V}^\top$, where $\tilde{U} \tilde{\Sigma} \tilde{V}^\top = M$?

$\endgroup$
4
  • $\begingroup$ When you say "project" onto the Stiefel manifold, what exactly do you mean? Are you just talking about finding $\arg\min_{\Omega:\Omega^T\Omega = I}\|\Omega - M\|_F$? In that case, it might help you to know that $UV^\top$ is the projection of $BA^\top$ onto the Stiefel manifold $\endgroup$ Commented Oct 17, 2023 at 20:14
  • 2
    $\begingroup$ Also, in the typical case where $A$ has more rows than columns, there are infinitely many solutions to $MA = B$; if $A$ has full row rank and $L$ is a matrix whose rows form a basis for $\text{null}(A^T)$, then every solution will be of the form $M = BA^\top (AA^\top)^{-1} + PL$ for a suitably shaped matrix $P$. Why should the specific solution $BA^\top (AA^\top)^{-1}$ be the best one to project onto $SO(m)$? $\endgroup$ Commented Oct 17, 2023 at 20:22
  • 1
    $\begingroup$ Please do note for future reference: It's Stiefel, not Steifel. :) $\endgroup$ Commented Oct 17, 2023 at 20:31
  • $\begingroup$ @BenGrossmann I would've expected to see the solution come from projecting the linear regression (ie unconstrained) solution onto the Stiefel manifold, rather than projecting BA^T onto the Stiefel manifold. Your answer resolves my confusion! $\endgroup$
    – calmcc
    Commented Oct 17, 2023 at 21:40

1 Answer 1

2
$\begingroup$

First of all, there is no guarantee that an "alternating projections" type of approach will give you an optimal solution in general. For a given subset $S \subset D$ and objective function $f$, there is no guarantee that there will be a nice relationship between the minimizer of $f(x)$ subject to $x \in S$ and the minimizer of $f(x)$ subject to $x \in D$. So, it is unclear why you think that this approach should work here.

On the other hand, you might find the following formulation of the Procrustes problem to be satisfying. Let $m\times n$ be the shape of $A$ and $B$. Note that we can rewrite the (squared) objective function in the form $$ \begin{align*} \|\Omega A - B\|_F^2 &= \operatorname{tr}[(\Omega A - B)^T(\Omega A- B)] \\ & = \operatorname{tr}[A^TA + B^TB - [(B^T\Omega A) + (B^T\Omega A)^T]] \\ & = \operatorname{tr}[A^TA] + \operatorname{tr}[B^TB] - \operatorname{tr}[B^T\Omega A] - \operatorname{tr}[(B^T\Omega A)^T] \\ & = \|A\|_F^2 + \|B\|_F^2 - 2\operatorname{tr}[B^T\Omega A] \\ & = \|A\|_F^2 + \|B\|_F^2 - 2\operatorname{tr}[\Omega AB^T], \end{align*} $$ which means that this minimization is equivalent to maximizing $\operatorname{tr}[\Omega AB^T]$. On the other hand, this maximization is equivalent to minimizing the quantity $$ \begin{align*} \|BA^T\|_F^2 + m - 2\operatorname{tr}[\Omega AB^T] &= \operatorname{tr}[(BA^T)^T(BA^T)] + \operatorname{tr}(\Omega^T\Omega) - 2\operatorname{tr}(\Omega AB^T) \\ & = \operatorname{tr}[(BA^T - \Omega)^T(BA^T - \Omega)] \\ & = \|BA^T - \Omega\|_F^2. \end{align*} $$ So, our original minimization is equivalent to the minimization of $\|BA^T - \Omega\|_F$, with the following relationship holding for all orthogonal matrices $\Omega$: $$ \|\Omega A - B\|_F^2 - \|BA^T - \Omega\|_F^2 = \|A\|_F^2 + \|B\|_F^2 - \|BA^T\|_F^2 - m. $$ So, you can think about this problem as a sort of projection onto the Stiefel manifold in the end.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .