# Minimize Frobenius norm with constraints

As a follow-up on my previous question, I would like to solve the following optimization problem:

$\min \Vert MA-B \Vert_F^2-x^HMy\;\;s.t.\;\;M^HM=I$

where $A$ and $B$ are $N\times L$ complex matrices. $M$ is $N\times N$ complex matrix and $x,y$ are $N\times 1$ complex vectors.

To my understaing this is equivalent to the problem $\max\Re\left\{tr\left(MAB^H \right)\right\}+\frac{1}{2} x^HMy\;\;s.t.\;\;M^HM=I$

I am not sure how to proceed from here.

-
It might be easier to work in the dual. Probably. – Nitish Mar 10 '14 at 17:01
Something's off about your problem formulation: $x^HMy$ is not necessarily real. – user1551 Dec 30 '15 at 9:01

We study the function $f(M)=-2trace(AB^TM)-x^TMy$ where $M\in O(n)$. Since $O(n)$ is a Lie group, the tangent space in $M$ to $O(n)$ is $TS=\{MH|H\text{ is skew-symmetric}\}$. Then $D_Mf:K\rightarrow -2trace(AB^TK)-x^TKy=-trace((2AB^T+yx^T)K)$ and we seek $M\in O(n)$ s.t., for every $K\in TS$, $D_Mf(K)=0$, that is, for every skew-symmetric $H$, $-trace((2AB^T+yx^T)MH)=0$. Let $U=2AB^T+yx^T$. Therefore $UM$ is orthogonal to $Skew-Sym$, that is $UM$ is symmetric or $UM=M^TU^T$. Generic orthogonal matrices $M$ are parametrized with the Cayley formula: $M=(I-Z)(I+Z)^{-1}$ where $Z$ is skew symmetric with no $-1$ eigenvalues. Our previous relation can be rewritten $U(I-Z)(I+Z)^{-1}=(I-Z)^{-1}(I+Z)U^T$. Finally, it remains to find the skew-symmetric matrices $Z$ s.t. $(I-Z)U(I-Z)$ is symmetric ; then we have $n(n-1)/2$ equations of degree $2$ in $n(n-1)/2$ unknowns.
To use a standard Lagrangian approach, and still assuming that everything is real, since in the contrary case, $x^HMy$ is complex and can not be maximized, and if it is replaced by $Re(x^HMy)$, then one may forget the complex structure and double the dimension from complex to real,...
... the Lagrange function is \begin{align} L(M,\Lambda)&=∥MA−B∥^2_F−x^TMy-tr(Λ(M^TM-I))\\ &=∥A∥^2_F+∥B∥^2_F-2tr(MAB^T)−tr(yx^TM)-tr(Λ(M^TM-I)) %tr(ΛM^TX+ΛX^TM) \end{align} with derivative $$0=\frac{∂L}{∂M}=-2AB^T-yx^T-(Λ+Λ^T)M^T$$ or $$M(Λ+Λ^T)=-2BA^T-xy^T$$ There is no unique solution to this problem, one special solution can be found by noting that if $(Λ+ΛT)$ is positive definite, then the left side is the polar decomposition of the right side. Which again can be computed using the SVD of the right side.
Lutzl, you obtain $2AB^T+yx^T=-(\Lambda+\lambda^T)M^{-1}$, that is $(2AB^T+yx^T)M$ is symmetric (because you know nothing about $\Lambda$), that is my first result. On the other hand, a priori, you must calculate all the solutions in order to find the extremum. According to my final result, there are at least $2$ candidates (the max and the min) and at most $2^{n(n-1)/2}$ candidates according to the Bezout theorem. – loup blanc Mar 11 '14 at 4:08