Simplify ${\rm trace}((A_1⊗A_2+B_1⊗B_2)^{-1})$

Question

This equation is take a long time in simulation due to Kronecker product ($⊗$).

Simplify $${\rm tr}((A_1⊗A_2+B_1⊗B_2)^{-1})$$ where tr is trace operator (sum of diagonal elements).
Also, $A_1,A_2,B_1,B_2$ are orthonormal matrix.
Is there a way to simplify (make it without $⊗$) ?

---

We have these properties:

• $\mathrm{tr}(A \otimes B) = \mathrm{tr}(A)\mathrm{tr}(B)$
• $\mathrm{tr}(A+B) = \mathrm{tr}(A) + \mathrm{tr}(B)$
• $\mathrm{tr}(AB) = \mathrm{tr}(BA)$
• $(A \otimes B)^{-1} = (A^{-1} \otimes B^{-1})$
• $||A||^2 = \mathrm{tr}(A^{\dagger}A)$
• $\mathrm{tr}(A^{\dagger}A) = \sum\limits_{i=1}^{\min(m,n)}\sigma_i^2$, where $\sigma$ is the singular value of $A$
• $\mathrm{tr}(A) = \sum\limits_{i=1}^n\lambda_i$, where $\lambda$ is the eigenvalue of $A$
• $\mathrm{tr}(A^{-1}) = \sum\limits_{i=1}^n\dfrac{1}{\lambda_i}$
• $\mathrm{tr}\left((I+A)^{-1}\right) = \sum\limits_{i=1}^n\dfrac{1}{\lambda_i+1}$, where $I$ is the identity matrix
• $\mathrm{tr}\left((I+A \otimes B)^{-1}\right) = \sum\limits_{i=1}^{\min(m,n)}\dfrac{1}{\lambda_i^{AB} +1}$, where $I$ is the identity matrix, $\lambda^{AB}=\lambda^A \otimes \lambda^B$ and $\lambda^A$,$\lambda^B$ are eigenvalue vectors for A, B respectively
• $(A \otimes B)(C \otimes D) = AC \otimes BD$

---

This equation is used to calculate the performance of telecommunication system with Intelligent Reflector Surface (IRS)

The simplification will reduce the computational complexity.

Answer 1

I assume that when you say that $A_1,A_2,B_1,B_2$ are "orthonormal", you mean that they are square, orthogonal matrices. I also assume that $A_1,B_1$ have the same shape, and $A_2,B_2$ have the same shape. I also assume that $A_1,A_2,B_1,B_2$ happen to be such that $A_1 \otimes A_2 + B_1 \otimes B_2$ is invertible.

If that is the case, then instead of directly computing the inverse of one large matrix, we can use the diagaonlization of two small matrices. Note that we can rewrite $$ (A_1 \otimes A_2 + B_1 \otimes B_2)^{-1} = (I + (A_1^TB_1) \otimes (A_2^TB_2))^{-1}(A_1 \otimes A_2)^T. $$ From there, we can use the spectral theorem for normal matrices to write $$ A_j^TB_j = U_jD_jU_j^*, \quad j = 1,2 $$ where each $U_j$ is a (typically complex) unitary matrix, $D_j$ is a (typically complex) diagonal matrix (whose diagonal entries have magnitude $1$), and $U^*$ denotes the conjugate-transpose of $U$. Here, we are using the fact that $A_j^TB_j$ is orthogonal, therefore normal, therefore unitarily diagonalizable.

We then compute $$ (I + (A_1^TB_1) \otimes (A_2^TB_2))^{-1} = \\ (I + (U_1D_1U_1^*) \otimes (U_2D_2U_2^*))^{-1} = \\ ([U_1 \otimes U_2][I + D_1 \otimes D_2][U_1 \otimes U_2]^*)^{-1} = \\ (U_1 \otimes U_2)(I + D_1 \otimes D_2)^{-1}(U_1 \otimes U_2)^*. $$ Because $I + D_1 \otimes D_2$ is diagonal, its inverse is easily computed. Putting everything together, we have $$ (A_1 \otimes A_2 + B_1 \otimes B_2)^{-1} = (U_1 \otimes U_2)(I + D_1 \otimes D_2)^{-1}(U_1 \otimes U_2)^*(A_1 \otimes A_2)^T, $$ and from here we can compute the trace.

Alternatively, if there is a nice way to express $(I + D_1 \otimes D_2)^{-1}$ in the form $$ (I + D_1 \otimes D_2)^{-1} = \sum_{k=1}^p P_k \otimes Q_k $$ with $P_k,Q_k$ having the same shape as $A_1,A_2$ respectively, then we can truly remove any Kronecker products from the computation.

---

Decomposing $(I + D_1 \otimes D_2)^{-1}$: Let $m,n$ denote the sizes of $A_1,A_2$ respectively. We note that $(I + D_1 \otimes D_2)^{-1}$ is diagonal with $$ [(I + D_1 \otimes D_2)^{-1}]_{n(j-1) + k, n(j-1)+k} = \frac{1}{1 + [D_1]_{jj}[D_2]_{kk}}. $$ Let $E_{j,k}$ denote the $m \times m$ matrix whose $j,k$ entry is $1$ and whose other entries are zero. Let $M_j$ denote the $n\times n$ diagonal matrix whose diagonal entries are equal to $\frac{1}{1 + [D_1]_{jj}[D_2]_{kk}}$ for $k = 1,\dots,n$. We find that $$ (I + D_1 \otimes D_2)^{-1} = \sum_{j=1}^m E_{jj} \otimes M_j. $$ It follows that \begin{align} (A_1 \otimes A_2 + B_1 \otimes B_2)^{-1} &= (U_1 \otimes U_2)(I + D_1 \otimes D_2)^{-1}(U_1 \otimes U_2)^*(A_1 \otimes A_2)^T \\ & = (U_1 \otimes U_2)\left(\sum_{j=1}^m E_{jj} \otimes M_j\right)(U_1 \otimes U_2)^*(A_1 \otimes A_2)^T \\ & = \sum_{j=1}^n (U_1 E_{jj}U_1^* A_1^T) \otimes (U_2 M_j U_2^* A_2^T), \end{align} So that \begin{align} \operatorname{Tr}[(A_1 \otimes A_2 + B_1 \otimes B_2)^{-1}] &= \operatorname{Tr}\left[\sum_{j=1}^n (U_1 E_{jj}U_1^* A_1^T) \otimes (U_2 M_j U_2^* A_2^T) \right] \\ & = \sum_{j=1}^n \operatorname{Tr}(U_1 E_{jj}U_1^* A_1^T) \operatorname{Tr} (U_2 M_j U_2^* A_2^T). \end{align} Moreover, the first trace in the product can be simplified dramatically: $$ \operatorname{Tr}(U_1 E_{jj}U_1^* A_1^T) = \operatorname{Tr}(E_{jj}U_1^* A_1^TU_1) = [U_1^*A_1^TU_1]_{jj}. $$ The computation of the second trace in the product can be made more efficient by rewriting $$ \operatorname{Tr} (U_2 M_j U_2^* A_2^T) = \operatorname{Tr} (M_j [U_2^* A_2^TU_2]), $$ so that the product $U_2^* A_2^TU_2$ can be computed once and reused for the successive computations of $\operatorname{Tr} (M_j [U_2^* A_2^TU_2])$.