5
$\begingroup$

Can anyone see a way to solve this equation efficiently?

$$AXB + X\odot C = D$$

I tried a straightforward solution that involved vectorizing $X$ but that turned out too expensive for my application -- my matrices are all $d\times d$ with $d=1000$ so I'm seeing if there's a way to solve it at a cost comparable to $d\times d$ SVD.

$A$,$B$ are positive-semi-definite and $C$ may have a few zeros.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Have you tried solving the vectorized equation with an iterative method, such as GMRES? You can use the non-vectorized form to compute the matrix-vector product in $O(d^3), so your total cost would be comparable to SVD if the number of iterations is small. You might need a preconditioner though. $\endgroup$
    – Amit Hochman
    Sep 28 '19 at 14:25
  • 2
    $\begingroup$ @YaroslavBulatov I added "matrix-equations", correct me if I am wrong. $\endgroup$
    – Anton Menshov ♦
    Sep 29 '19 at 19:37
  • 1
    $\begingroup$ Cross-posted on MO. $\endgroup$
    – Federico Poloni
    Sep 30 '19 at 11:24
  • 1
    $\begingroup$ Where it appears to have an answer. Please post on one site at a time only. $\endgroup$
    – Richard
    Sep 30 '19 at 23:46
  • 1
    $\begingroup$ I'm starting to think that this problem is not solvable in O(d^3). It comes from approximating T=E[xi,xj,xk,xl] in terms of lower order moments, then trying to solve TX=G. I found that even computing ||T||^2 needs more than O(d^3) operations $\endgroup$
    – Yaroslav Bulatov
    Oct 2 '19 at 17:52

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.