Solving a matrix least squares problem with a fixed Frobenius norm constraint

Question

I am trying to solve for X an equation of the form :

Min ||AXB-CXD|| s.t. ||X||_F=1,

where , A, C are m-by-m matrices, and B, D are n-by-b matrices. Is there any effective algorithms?

Any hint is greatly appreciated :-)

Answer 1

Your problem is equivalent to

$\min \| AXB - CXD \|_{F}^{2} $

subject to

$\| X \|_{F}^{2} = 1$.

Here, squaring the norms simplifies the calculations below without changing the optimal solutions.

The key idea is that this problem is really a linear least squares problem in the entries of the matrix $X$. If you let the vector $u$ be defined by

$u=\mbox{vec}(X)=\left[ \begin{array}{c} X_{1,1} \\ X_{2,1} \\ \vdots \\ X_{m,1} \\ X_{1,2} \\ X_{2,2} \\ \vdots \\ \vdots \\ X_{m,n} \end{array} \right]$

Then $\mbox{vec}(AXB-CXD)$ can be written as

$\mbox{vec}(AXB-CXD)=Gu$

where the entries of G can be computed by a tedious calculation. In terms of $G$ and $u$, your problem is now

$\min \| Gu \|_{2}^{2}$

subject to

$\| u \|_{2}^{2}=1$.

This can be written as

$\min u^{T}G^{T}Gu$

subject to

$u^{T}u=1$.

This is simply the problem of finding a normalized eigenvector of $G^{T}G$ corresponding to the smallest eigenvalue of $G^{T}G$.