Solving for X in a Kronecker Product Matrix Equation

Question

I'm looking to solve this equation:

$$I = (A \otimes (XB)) + E $$

for $X$ with matrices $A,B$, error matrix $E$, and identity $I$, such that $\lVert E \rVert_F$, the frobenous norm of $E$ is minimized (if needed, another matrix norm is fine). But I'm not sure how to handle the Kronecker product.

Answer 1

The solution is $$X=\frac{{\rm tr}(A)}{\|A\|_F^2}\,B^+$$ here's how I derived it.$$ $$ The objective function is $$\eqalign{ \phi &= \frac{1}{2}\|E\|_F^2 = \frac{1}{2}(A\otimes XB-I):(A\otimes XB-I) \cr d\phi &= (A\otimes XB-I):(A\otimes dX\,B) \cr &= (A:A)(XB:dX\,B) - (I:A)(I:dX\,B) \cr &= \Big((A:A)XBB^T - (I:A)B^T\Big):dX \cr &= \Big(\|A\|_F^2XBB^T - {\rm tr}(A)B^T\Big):dX \cr \frac{\partial\phi}{\partial X} &= \|A\|_F^2XBB^T - {\rm tr}(A)B^T \cr }$$ Set the gradient to zero and solve for $X$ $$\eqalign{ \|A\|_F^2XBB^T &= {\rm tr}(A)B^T \cr X &= \frac{{\rm tr}(A)}{\|A\|_F^2} B^T(BB^T)^{-1} \cr }$$ In the above steps, a colon (:) is simply a product notation for the trace, i.e. $$A:B={\rm tr}(A^TB)$$ and $M^+$ is the pseudoinverse of $M$.

Answer 2

Lynn's solution assumes that $A$ is square. When it is rectangular, the term $$I:(A\otimes dX\,B)$$ must be handled more carefully.

In particular, you must find a Kronecker decomposition of the identity matrix $$I = \sum_{k=1}^r Y_k\otimes Z_k$$ where the $(Y_k, Z_k)$ matrices are shaped like $(A, XB)$ respectively.
Note that in the case that $A$ is square, $r=1$ and the decomposition is simply $I = I_A\otimes I_{XB}$.

Look for the classic paper by van Loan & Pitsianis, or Pitsianis' PhD thesis, which contains Matlab code.

Using this decomposition yields $$\eqalign{ I:(A\otimes dX\,B) &= \sum_{k=1}^r Y_k\otimes Z_k :(A\otimes dX\,B) \cr &= \sum_{k=1}^r (Y_k:A)\,(Z_k:dX\,B) \cr &= \bigg(\sum_{k=1}^r {\rm tr}(Y_k^TA)\,Z_kB^T\bigg):dX \cr }$$ Substituting into Lynn's differential $$\eqalign{ d\phi &= \Big(\|A\|_F^2XBB^T - \sum_k {\rm tr}(AY_k^T)\,Z_kB^T\Big):dX \cr \frac{\partial\phi}{\partial X} &= \|A\|_F^2XBB^T - \sum_k {\rm tr}(AY_k^T)\,Z_kB^T = 0 \cr \|A\|_F^2XBB^T &= \sum_k {\rm tr}(AY_k^T)\,Z_kB^T \cr X &= \sum_k \frac{{\rm tr}(AY_k^T)Z_k}{\|A\|_F^2}\,\,B^+ \cr }$$