3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is $A \otimes (X\cdot B ) + E$ or $(A \otimes X)\cdot B + E$ ? $\endgroup$ – Elias Costa Nov 28 '17 at 20:49
  • $\begingroup$ So sorry that was ambiguous -- I've clarified it now $\endgroup$ – Robert Nov 28 '17 at 20:50
3
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ This is super clear! Thank you so much! $\endgroup$ – Robert Nov 29 '17 at 1:21
3
$\begingroup$

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 }$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.