Suppose we are given $A\in\mathbb{R}^{mn\times mn}$, with $A$ symmetric positive definite.

We wish to find $B\in\mathbb{R}^{m\times m}$, $C\in\mathbb{R}^{n\times n}$ and $D\in\mathbb{R}^{mn\times mn}$, with $B$, $C$ and $D$ all symmetric positive semi-definite, such that $A=B\otimes C+D$ and such that $\| D \|_F$ is as small as possible.

Without the constraint that $D$ is positive semi-definite (henceforth p.s.d.), this would be a standard "Nearest Kronecker Product" problem, whose solution is discussed by Van Loan and Pitsianis (1993) https://doi.org/10.1007/978-94-015-8196-7_17. (See also this question: Method to reverse a Kronecker product .)

However, with the constraint that $D$ is p.s.d., it appears that this problem is much harder. Is there an alternative to numerical optimisation to solve it?

I had two ideas for avenues of attack though neither seems to have amounted to much.

  1. Using the fact that positive definite matrices may be simultaneously diagonalized on $A$ and $\hat{B}\otimes\hat{C}$ where $\hat{B}$ and $\hat{C}$ are the solutions to the problem without the p.s.d. constraint on $D$. The problem is that the matrix which simultaneously diagonalizes these will not have the required Kronecker structure.

  2. Using the connection to the generalized eigenvalue problem: if the constraint that $D$ is p.s.d. binds, then there must exist some $v\in\mathbb{R}^{mn}$ and some $\lambda\in\mathbb{R}$ s.t. $(A-\lambda (B\otimes C))v=0$. This has helped simplify numerical optimisation, as it means we can directly impose the constraint, but I haven't been able to get further analytical results out of it.

  • $\begingroup$ Start with the Cholesky decomposition $A=LL^T$, then find the nearest Kronecker approximation $L=Y\otimes Z$. This yields $B=YY^T$ and $C=ZZ^T$. While this solution satisfies the PSD constraints, I'm not sure it minimizes $\|D\|_F,\,$ but it might be good enough for whatever purpose you have in mind. $\endgroup$ – greg Jun 21 '18 at 11:56
  • $\begingroup$ Why would this satisfy the p.s.d. constraint on $D$? What you describe should give exactly the same solution as the original nearest Kronecker solution, as Kronecker products of Cholesky factors are Cholesky factors. $\endgroup$ – cfp Jun 22 '18 at 12:49
  • $\begingroup$ They are not the same. The Kronecker approximation $A\approx(B_A\otimes C_A)$ via the vanLoan-Pitsianis algorithm is NOT s.p.d. and neither is the Kronecker approximation $L\approx(B_L\otimes C_L)$. However $$A=LL^T\approx(B_L\otimes C_L)(B_L\otimes C_L)^T$$ is s.p.d. (Do some sample calculations in Matlab to convince yourself of this) $\endgroup$ – greg Jun 22 '18 at 15:38
  • $\begingroup$ I cannot numerically replicate your claim that there are p.d. $A$ for which the Van Loan and Pitsianis algorithm produces non-definite $B$, $C$. Occasionally, both $B$ and $C$ have negative diagonals but fixing this is just a question of flipping both their signs. My implementation is here: gist.github.com/tholden/58dd9a8991daa750ae36a633fe7060a4 and there's code to test your claim in the comments. $\endgroup$ – cfp Jun 22 '18 at 21:10
  • $\begingroup$ You're right of course that in general taking Cholesky decompositions first would give a different answer as the effective minimand is different. I meant that they'd give the same answer in the exact case, where there's a zero $D$ solution, though I stupidly didn't state this. The second comment on the above gist tests this weaker claim numerically. $\endgroup$ – cfp Jun 22 '18 at 21:37

Your Answer

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

Browse other questions tagged or ask your own question.