Is anything known about computational complexity of finding $X$ which satisfies the following matrix equation?
$$\sum_i^n A_i X B_i = C$$
With $A_i,B_i,C$ dense $d\times d$ matrices. Any literature pointers are appreciated!
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Should be $O(d^3)$ I feel... $\endgroup$– SuvritCommented Nov 18, 2020 at 1:17
-
1$\begingroup$ If $n \geq d^2$ then you can't possibly do better than $O(d^{2\omega})$, since this is just an arbitrary dense $d^2 \times d^2$ linear system in that case. $\endgroup$– Nathaniel JohnstonCommented Nov 18, 2020 at 2:31
-
2$\begingroup$ @1 - yes it is. Every linear transformation between $d \times d$ matrices can be written as a sum of the form described in the original question with $n = d^2$. In fact, you can even choose the $A_i$ matrices to be standard basis matrices (i.e., matrices with all $0$ entries, except for a single $1$ entry). This follows from standard facts about vectorizations and Kronecker products (see here, for example). $\endgroup$– Nathaniel JohnstonCommented Nov 18, 2020 at 13:30
-
$\begingroup$ @NathanielJohnston I should have said $\max(d^2n,d^{2\omega})$. The problem makes sense at $n=O(d^{\alpha})$ at $\alpha\in(0,2)$. It appears difficult. $\endgroup$– TurboCommented Nov 18, 2020 at 17:09
-
$\begingroup$ The interesting sub-question is whether complexity of finding the solution has the same dependence on $n$ and $d$ as checking the solution for correctness which is $O(d^{2\omega} n)$ $\endgroup$– Yaroslav BulatovCommented Nov 18, 2020 at 17:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
This is exactly equivalent to asking the complexity of solving $\Phi(X) = C$, where $\Phi$ is a linear transformation acting on the vector space of $d \times d$ matrices. Since that vector space is $d^2$-dimensional, this has complexity $O((d^2)^3) = O(d^6)$ (or more precisely, $O((d^2)^\omega) = O(d^{2\omega})$, where $\omega$ is the exponent of matrix multiplication).
If $n$ is significantly smaller than $d^2$ though, you can do better. For example, if $n = 1$ then this is $O(d^3)$ via pseudoinverses of $A$ and $B$. If $n = 2$ then this is a generalized Sylvester equation, which is also $O(d^3)$.
answered Nov 18, 2020 at 1:37
-
$\begingroup$ I see...curious for which
nit switches fromO(d^3)toO(d^6)$\endgroup$ Commented Nov 18, 2020 at 3:44 -
$\begingroup$ Yeah, hopefully someone knows what the dependence on $n$ is and can provide a more thorough answer in the future. Maybe something like $O(n^{3/2}d^3)$ (or $O(n^{\omega/2}d^\omega)$). $\endgroup$ Commented Nov 18, 2020 at 13:35
-
1$\begingroup$ If $n\le d^2$, you can still solve linear systems on the space of $d'\times d'$ matrices where $d'=\lfloor\sqrt n\rfloor$. Thus, you get a $\Omega(n^\omega)$ lower bound. $\endgroup$ Commented Nov 18, 2020 at 13:53
-
$\begingroup$ @Emil - how? That would imply that you can solve the $n = 1$ case in constant time (constant with respect to $d$, the size of the matrices). There has to be some dependence on $d$. $\endgroup$ Commented Nov 18, 2020 at 15:09
-
$\begingroup$ It’s a lower bound, not an upper bound. It only says something nontrivial when $n$ is at least moderately large with respect to $d$. $\endgroup$ Commented Nov 18, 2020 at 15:42