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, 2019 at 14:25
  • 2
    $\begingroup$ @YaroslavBulatov I added "matrix-equations", correct me if I am wrong. $\endgroup$
    – Anton Menshov ♦
    Sep 29, 2019 at 19:37
  • 1
    $\begingroup$ Cross-posted on MO. $\endgroup$
    – Federico Poloni
    Sep 30, 2019 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, 2019 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, 2019 at 17:52

0

Reset to default

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.