# Multi-Domain Communication Systems and Networks: A Tensor-Based Approach
## 3 Simultaneous Signal Processing Across Domains
### Tensor-Based Receiver Designs
#### 3.2.1 Complexity of Tensor Multi-Linear MMSE Receiver  
The process of finding the multi-linear MMSE operator \(\mathcal{G}\) using (18) involves performing the Einstein product and tensor inversion. We now assess the computational complexity of finding \(\mathcal{G}\). We refer to a single floating point operation (addition, subtraction, multiplication, or division) as a flop. For simplicity of explanation, we assume the channel to be a square tensor, i.e., \(N=M\) and \(J_{1}=I_{1},\cdots,J_{M}=I_{N}\). The Einstein product \((*_{N})\) between two tensors of size \(I_{1}\times\cdots\times I_{N}\times I_{1}\times\cdots\times I_{N}\) each requires \(\mathcal{O}((\prod_{n=1}^{N}I_{n})^{3})\) flops [19]. Note that if the number of flops required for any step is polynomial in variable \(n\), we state the complexity as \(\mathcal{O}(n^{p})\) where \(p\) is the degree of the polynomial. The process of calculating \(\mathcal{G}\) can be broken down into sequential steps which are listed in Table 3 along with the computational cost of each step.  
The first step in Table 3 is calculating two [PERSON] products; hence, its complexity is \(\mathcal{O}((\prod_{n=1}^{N}I_{n})^{3})\). The next step performs an element-wise addition of two tensors with \((\prod_{n=1}^{N}I_{n})^{2}\) elements in each; hence, it requires \(\mathcal{O}((\prod_{n=1}^{N}I_{n})^{2})\) operations. Note that in several cases where the noise tensor contains uncorrelated elements, the noise covariance will be a pseudo-diagonal tensor. In such a case, the number of non-zero elements in the noise covariance tensor would be \(\prod_{n=1}^{N}I_{n}\); hence, the cost of this step would become \(\mathcal{O}(\prod_{n=1}^{N}I_{n})\). Further, the next step calculates the inverse of an order \(2N\) tensor. Tensor inverse can be calculated using the [PERSON]'s method which solves an iterative equation involving the [PERSON] product with a complexity of \(\mathcal{O}((\prod_{n=1}^{N}I_{n})^{3})\) as described in [10]. The final step again requires two [PERSON] products, and therefore has a complexity of \(\mathcal{O}((\prod_{n=1}^{N}I_{n})^{3})\). If we add all the complexities in Table 3, we see that finding \(\mathcal{G}\) requires an overall \(\mathcal{O}((\prod_{n=1}^{N}I_{n})^{3})\) operations, which is cubic in the number of input/output tensor elements, \(\prod_{n=1}^{N}I_{n}\). It is to be noted that many of these operations can be computed  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Step** & **Complexity** \\ \hline Find \(\mathcal{H}*_{N}\mathcal{C}_{\mathcal{X}}*_{N}\mathcal{H}^{H}\) & \(\mathcal{O}((\prod_{n=1}^{N}I_{n})^{3})\). \\ Find \((\mathcal{H}*_{N}\mathcal{C}_{\mathcal{X}}*_{N}\mathcal{H}^{H}+\mathcal{C}_{ \mathcal{N}})\) & \(\mathcal{O}((\prod_{n=1}^{N}I_{n})^{2})\). \\ Find \((\mathcal{H}*_{N}\mathcal{C}_{\mathcal{X}}*_{N}\mathcal{H}^{H}+\mathcal{C}_{ \mathcal{N}})^{-1}\using parallel processors to significantly reduce the time complexity of executing them. A detailed description of parallel and faster implementation of the [PERSON] product and the tensor inversion using [PERSON]'s method can be found in ([10], Appendix D). Several other algorithms to compute tensor inverse, without any need of tensor transformation to matrix or vector, have been considered in literature [15; 16] which rely on the [PERSON] product. For instance, [15] presents a higher order bi-conjugate gradient method, and [16] presents an elimination method using tensor triangular decompositions.