# Bounds of Procrustes problem

We denote $\|\cdot\|_F$ as the Frobenius norm of some matrix. We define $f: \mathbb{R}^{d\times r}\times\mathbb{R}^{d\times r} \rightarrow \mathbb{R}^{d\times r}$ as the following: \begin{align} f(A,B) = AR_{A,B}-B,\text{where }R_{A,B} = \arg\min_{R\in \mathbb{R}^{r\times r}, RR^\top = I}\|AR - B\|_F^2. \end{align} Now we have three matrices $X,Y$ and $Z$, where $\|X\|_F, \|Y\|_F$ and $\|Z\|_F$ can be bounded by some constant $C$. We want to find the relation between $\|f(X,Y)\|_F$ and $\|f(X,Z) - f(Y,Z)\|_F$. It is easy to see that \begin{align} \|f(X,Z) - f(Y,Z)\|_F \geq \|f(X,Y)\|_F, \end{align} because \begin{align} \|f(X,Z) - f(Y,Z)\|_F &= \|XR_{X,Z} - Z - (YR_{Y,Z} - Z)\|_F \\ & = \|XR_{X,Z}-YR_{Y,Z} \|_F \\ & = \|XR_{X,Z}R_{Y,Z}^\top - Y\|_F\\ & \geq \|XR_{X,Y} - Y\|_F\\ & = \|f(X,Y)\|_F. \end{align} The question is, is it possible to find some constant $C'$ which may related to $C$, and \begin{align} \|f(X,Z) - f(Y,Z)\|_F \leq C'\|f(X,Y)\|_F. \end{align}

PS: this problem is highly related to Orthogonal Procrustes problem. https://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem

• I added the [oc.optimization-and-control] tag, to try to have a top-level arXiv area tag. If this is incorrect, please edit. – David Roberts Aug 27 '18 at 0:02
• $R$ might not be defined for some degenerate cases, e.g. if $A=B=0$. Even if it is defined we might encounter arbitrarily large $C'$ even if the matrices are bounded, consider for example $X=[1;\epsilon], Y=[1;-\epsilon], Z=[0;1]$. – Markus Sprecher Aug 27 '18 at 11:25
• We have $f(A,B)=AA'B(B'AA'B)^{-1/2}-B$ (use the fact that R is the projection P of $A'B$ onto $O(r)$, P can be written as $P(X)=X(X'X)^{-1/2}$). However I doubt that the formula is useful here. – Markus Sprecher Aug 27 '18 at 20:00
• To Markus Sprecher: Thanks for your reply! I think by the formula $f(A,B)$ you give, it is possible to find such a $C'$ if we add some regularity conditions on $X^\top Z$ and $Y^\top Z$. – FFFenor94 Aug 27 '18 at 20:36