## Achievable Degrees of Freedom for Closed-form Solution to Interference Alignment and Cancellation in Gaussian Interference Multiple Access Channel

Qu Xin  and Chung G. Kang  

 UNISOC, Shanghai, China; email: xin.qu@unisoc.com

 School of Electrical Engineering, Korea University, Seoul, Korea; email: ccgkang@korea.ac.kr

Abstract -A combined technique of interference alignment (IA) and interference cancellation (IC), known as interference alignment and cancellation (IAC) scheme, has been proposed to improve the total achievable degrees of freedom (DoFs) over IA. Since it is NP-hard to solve the transceiver under a given tuple of DoFs  or  to  maximize  the  total  achievable  DoFs  in  the  general system  configuration  by  IA  (or  IAC),  the  optimal  transceiver cannot be obtained in polynomial time. Meanwhile, it has been known  that  a  closed-form  yet  suboptimal  transceiver  can  be designed for IAC  by  employing a symbol-to-symbol (STS) alignment structure. As its performance has not been known yet, we  aim  to  derive  the  total  DoFs  that  can  be  achieved  by  such suboptimal but closed-form IAC  transceivers for Gaussian interference  multiple  access  channels  with K receivers  and J users (transmitters), each with M antennas. Our analysis shows that  the  closed-form  IAC  transceivers  under  consideration  can achieve a maximum total achievable DoFs of 2 M ,  which  turns out to be larger than  those achieved  in classical IA, e.g.,   2 1 MK K  DoFs  by  a  specific  configuration  where  each  link

To determine the total achievable DoFs, one needs to address the feasibility of IAC  first. IAC  is feasible when  the interferences are properly reduced so that enough interference-free  space  can  be  saved  for  the  desired  signals. Both IA and IC operations contribute to eliminating interferences. With IC operation at receive side, the decoded signal packets at one receiver are sent to other receivers over backhaul link, and therefore, the interferences caused by such known signals can be immediately extracted and do not burden on the interference subspace. Consequently, the feasibility of IAC  only depends on the feasibility of IA under the IAC-specific interference scenario.

has the same target DoFs. Moreover, considering the NP-hardness of deriving the maximum total achievable DoFs with the optimal IAC transceiver, its upper bound has been derived for comparison with the results  of  our  closed-form  IAC  transceiver.  Numerical results illustrate  that  its  performance can  be  guaranteed within 20%  of  the  upper  bound  when  the  number  of  multiple  access channels are relatively small, e.g., 4 K  .

Index Terms - Interference alignment and cancellation, MIMO, closed-form solution, degrees of freedom, multiple access channel

## I. INTRODUCTION

HE total  degrees  of  freedom  (DoFs)  achieved  by  vector space interference alignment (IA) depends on two aspects: the maximum number of interference signals caused by single interfering source and the aligned level for interference signals from all interfering sources. With the limited number of Tx/Rx antennas, in order to improve the achievable total DoFs over IA, a vector space interference alignment and cancellation (IAC) technique has been proposed, which combines vector space IA with  interference cancellation (IC). As  IC  operation  can immediately eliminate interferences at a receive side, it T

makes more signal subspace than IA under the same number of Tx/Rx antennas. Therefore, IAC is expected to gain more DoFs over IA.

With limited spatial dimension, IAC is not always feasible.

There are several works that have studied the feasibility of IA for K -user interference channel with M transmit antennas and N receiver  antennas  [1-3].  In  general,  they  related  the feasibility issue to the problem of determining the solvability of a set of quadratic multivariate polynomial equations which can be summarized as follows:

$$\mathbf U _ { k } ^ { \, H } \mathbf H _ { k j } \mathbf V _ { j } = \mathbf 0, \ \forall k \neq j$$

$$\tilde { \Psi } _ { k } \tilde { \Psi } _ { k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k } \tilde { \Psi } _ { k } ^ { \Psi } \tilde { \Psi } _ { k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \ tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \that { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l k } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \ tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \that { \Psi } _ { k l } ^ { \Psi } \that { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l k } ^ { \Psi } \tilde { \Psi } _ { k k } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \ tilde { \Psi } _ { k l } ^ { \Psi } \that { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { kl } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tilde { \Psi } _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { kl } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ {\Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi }\tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _{ k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \taut _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k k } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau _ { k l } ^ { \Psi } \tau$$

where j V denotes  a  precoding  matrix  at  transmitter j , k U denotes a zero-forcing matrix at receiver k , and kj H denotes a channel  matrix  from  transmitter j to  receiver k , and k d denotes the target DoFs  to obtain at receiver k . The transceivers { j V } and { k U },   , 1, j k K  , are the unknowns to be solved from (1) and (2).

In the existing works [2, 3], (1) and (2) can be solved only for symmetric system configurations where each Tx/Rx pair has the  same  target  DoF k d d  and  the  same  number  of  Tx/Rx antennas,  i.e., / M N ,  which  is  divisible  by d .  For  general system configurations with a given tuple of DoFs   1 2 , , , K d d d  , it has been shown that solving (1) and (2) is  NP-hard, as long as each node is equipped with at least 3 antennas [4]. Therefore, a few heuristic algorithms have been proposed to solve IA transceivers in an iterative manner [5][6]. However,  these  algorithms  cannot  determine  whether  the solutions exist, nor is there any guarantee for converging to the optimal solutions even when they exist. Subsequently, the total

DoFs achieved by these heuristic algorithms is not guaranteed. Furthermore, it has been also shown that finding the maximum total  DoFs  achieved  by  IA  is  also  NP-hard  for  the  general system configuration [4].

Considering  that  it  is  impossible  to  derive  the  optimal transceivers or the maximum total achievable DoFs until now, we aim to derive some suboptimal yet definite results which do not depend on the performance of iterative algorithms. In our earlier work [7], a symbol-to-symbol alignment (STS) structure has  been  proposed  to  IAC  in  a  Gaussian  interference  MAC channel. Based on the proposed STS structure, a closed-form IAC solution can be obtained, allowing us to determine the total achievable  DoFs  definitely.  Furthermore,  the  necessary  and sufficient  conditions  for  the  existence  of  closed-form  IAC solutions  have  also  been  derived.  In  this  paper,  we  aim  to investigate  the  total  DoFs  that  can  be  achieved  by  such closed-form solutions. Since it is NP-hard to find the maximum total achievable DoFs for optimal IAC solutions, our derived result has been compared with the upper bound on achievable DoFs of IAC, which can be obtained from the infeasibility IAC conditions.

Section  II  presents  the  system  model  and  the  concepts  of IAC. Section III reviews the proposed IAC with STS alignment scheme as well as its closed-form solutions in [7]. Section IV derives  the  total  DoFs  for  the  Gaussian  interference  MAC system  achieved  by  the  IAC  with  STS  alignment  scheme. Furthermore, the related analytical results, including the upper bound on achievable DoF of IAC, are presented along with the solid proofs. Finally, Section  V  provides  the  concluding remarks.

## II.PRELIMINARIES

## A. System Model

Fig.  1  illustrates  a  general  configuration  of  a   , , K M J Gaussian  interference  MAC  system.  There  are K interfering MACs, in each of which a receiver of the -k th MAC system is associated with a group of k N users ( 1 k N  and 1 K k k N J K     ),  assuming that each receiver and user are equipped  with M antennas.  For  notational  convenience,  we denote the j -th user in the k -th MAC by user [j, k] . Each user [j, k] desires to send   , j k d independent concurrent signal packets to its  target  receiver k (   ) .  We  can  further  define  the , j k d M  total DoFs in the system as   1 1 , k K N j k k j DoF d      .

Let   , j k x denote the transmitted signal vector of dimension   1 , j k d  from the user [j,k] ( 1, 2, , = k j N  ; 1, 2, , = k K  ),  in  which  each  element  of  the vector corresponds to one independent signal packet, denoted by {     1 } , , j k j k d x    .  Furthermore, the M M  channel matrix from user [j',  k'] to  receiver k is  given  by   ' , j k k  H ,  with  each  entry drawn  independently  from  a  continuous  distribution,  while allowing no channel extension. Let [ , ] [ ] [ , ] [ , ] [ , ] 1 2 , j k j k j k j k j k d      V v v v  represent an   , j k M d  transmit precoding matrix at user [j, k] , where each column vector is applied to each signal packet, and k U denote an     1 , k N j k j M d    zero-forcing matrix at receiver k . Subsequently, the output signal vector of dimension     1 1 at receiver , k N j k j d    k can be represented as

$$\iota _ { 1 } \sqrt { - 2 } \cdot \\ \iota _ { 2 } \sqrt { y } _ { k } = & \underset { j = 1 } { U } _ { k } ^ { H } \sum _ { j = 1 } ^ { N _ { k } } \mathbf H _ { k } ^ { [ j, k ] } \sum _ { \ell = 1 } ^ { d [ j, k ] } \mathbf x _ { \ell } ^ { [ j, k ] } \\ & \underset { \substack { \text{single} \\ 1 } } { + } \underset { \text{single} \\ 2 } } { \overbrace { + } \underset { \text{$U_{k}^{H} \sum_{k}^{K} \sum_{j^{\prime}=1}^{N_{k}^{K}} \mathbf H_{j^{\prime}},k^{\prime}] } { \sum_{j^{\prime}=1}^{N_{k}^{K}} \mathbf x _ { \ell ^ { \prime } } } \underset { \text{interferences} \\ 1 } { \overbrace { 1 } } \sum _ { k } \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \\ \cdot \end{matrix} } \,, \quad \,, \quad \,, \quad \,, \quad \,, \quad \,, \quad \,.$$

where k n is a zero-mean additive white Gaussian noise vector ,   2 ~ , CN k  n 0 I .  Throughout  this  paper, H A denotes  the conjugate transpose operator for a matrix A .

Fig. 1.   , , K M J Gaussian interference MAC system model

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00248v1-figure-87d8e608-4b3c-4b28-9f78-996d5eccaef5.jpg)

## B. Interference alignment and cancellation (IAC)

In  the  sequel,  we  briefly  introduce  how  IAC  works  in  the MAC channel.  At  the  transmit  side,  IA  operation  works  to precode the signals jointly, so that the interferences caused at the receive side can be effectively aligned. At the receive side, IC operation performs successively, i.e., the  decoded  signals

$$\left \{ \hat { \mathbf x } ^ { [ j, k ] } \Big | \, j \in \left [ 1, N _ { k } \, \right ] \right \} \, \text{at receiver $k$ are sent over a backhaul link} \quad \text{Moreov} \quad \\ \tilde { T }. \, = \tilde { T }. ^ { \tilde { A } }$$

to other  receivers  which  have  not  been  decoded  yet  for cancellation. Therefore, a decoding operation is supposed to be performed in one receiver at a time. Without loss of generality, we assume that the decoding order follows from receiver 1 to K . When the receiver k decodes k y , it has already obtained

$$& \Lambda \,. \, w \, \text{en} \, \text{receiver} \, \kappa \, \text{acocutes} \, y _ { k } \,, \, \text{t} \, \text{has an array of animate} \quad z _ { k } \, - \, \{ \, \cdot \\ & \left \{ \hat { x } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \right | j ^ { \prime } \in \left [ 1, N _ { k ^ { \prime } } \, ], k ^ { \prime } \in \left [ 1, k - 1 \right ] \right \} \, \text{from earlier decoding, so} \quad \text{denotes} \quad \text{onario} \}$$

that  the  corresponding  interferences       1 1 ˆ , , , k j k j k j k k k          H V x can be immediately subtracted from k y . As a result, such part of interferences is not necessarily to be handled by IA operation. In other words, at each k -th MAC, IA operation takes charge of  only  the  part  of  interferences  caused  by  the   1 k  -th  to K -th MACs.

Additionally, note that the total number of received packets decreases as successive cancellation is performed. In particular, there exist a total of   , 1 1 k K N j k k j d        packets initially at the receiver k , which  has  only  a  total  of   , 1 k K N j k k k j d        remaining packets by the time it gets its turn to decode k y . If   , 1 k K N j k k k j d M         , the desired signals and interferences are separable with M antennas, indicating that the interferences incurred by the k -th MAC are not required to be aligned. This further works at the   1 k  -st to K -th MACs, since the total number of remaining packets at each of them is no more than the one at the k -th MAC. In order to identify the receivers in which the interferences are not necessarily to be aligned, we allocate a new label IAC k to   1 k  -st MAC if the k -th MAC is the first one which holds   , 1 k K N j k k k j d M         . In other  words,  IA  operation  is applied only to align the interferences incurred at the 1 st to the IAC k -th MACs.  Furthermore,   IAC , 1 1 k K N j k k k j d M          also indicates that the interferences caused by         IAC 1, 1, 1 , , -j k k j N k k K         x do  not  require  to  be cancelled. Therefore, only the decoded signals at the 1 st to the IAC k -th MACs are required to be sent through the backhaul link for a cancellation purpose.

According to the system model, the signal subspace k S  at k -th MAC  is spanned by a set of signal vectors,           , 1, , 1, , , S j k j k j k k k k d j N        H v   , while the interference  subspace k I  is  spanned  by  a  set  of  interference vectors,

$$& \text{vectors,} \\ & \mathcal { I } _ { k } = \left \{ \mathbf H _ { k } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \mathbf v _ { \ell ^ { \prime } } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \Big | \ell ^ { \prime } \in \Big [ 1, d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \Big ], \forall j ^ { \prime } \in [ 1, N _ { k ^ { \prime } } ], k ^ { \prime } \in [ 1, K ], k ^ { \prime } \neq k \right \} \, \underset { \text{beam aligned.} } { \text{dimension} }.$$

Moreover, I k can be also written in the union of two sets, i.e., IA IC   , where

I I I k k k             , IA 1, , 1, , 1, , , I j k j k j k k k k d j N k k K                      H v   denotes the set of interferences aligned by IA operation and             , IC 1, , 1, , 1, 1 , , I j k j k j k k k k d j N k k                      H v   denotes  the  set  of  interferences  that  are  eliminated  by  IC operation. Inspired by (1) and (2), the zero-forcing constraints on IAC can be given as

$$\mathbf U _ { k } ^ { \ H } \mathbf H _ { k } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \mathbf V ^ { [ j ^ { \prime }, k ^ { \prime } ] } = \mathbf 0$$

$$\begin{smallmatrix} \kappa & \kappa \\ \text{rank} \left ( \mathbf U _ { k } ^ { H } \mathbf S _ { k } \right ) = \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \end{smallmatrix} \begin{smallmatrix} \theta & \theta \\ \text{rank} \left ( 5 \end{smallmatrix}$$

for   IAC 1, k k   ,   1, k k K     ,  and   1, k j N     ,  where         1 1 , , , , k k N k k N k k k k k      S H V H V  .  (4)  guarantees  that  at each k -th MAC,  all  interferences     IA , , I j k j k k k      H V are aligned onto the subspace that is orthogonal to k U , while (5) ensures  that the signal subspace  at  the k -th MAC  has dimension   , 1 k N j k j d   and is linearly independent  of  the interference subspace.

## III. INTERFERENCE ALIGNMENT AND CANCELLATION: CLOSED-FORM SOLUTIONS

In  this  section,  we  review  the  proposed  IAC  with  an  STS alignment scheme, which was originally introduced in [7] as a specific alignment scheme. The main works have been summarized, including the proposed IAC graph, which allows for obtaining the closed-form solutions, along with the necessary and sufficient conditions for the existence of closed-form IAC solutions.

## A. IAC with STS alignment structure

Since  solving  the  transceivers,     , j k V and   k U jointly from  the  set  of  quadratic  equations  in  (4)  is  NP-hard,  we consider designing the transmitters     , j k V first and then the receivers   k U in our earlier work. In order to satisfy both (4) and (5),     , j k V can be found by aligning interferences in I k , such that the interference subspace k I  is complimentary to the signal subspace k S  . And then, the receivers   k U can always be found in the left null space of k I  .  As the interferences in IC I k can  be  cancelled  and  thus,  they  do  not  burden  the dimension of k I  , only the interferences in IA I k are required to be aligned.

The above discussion motivates us to seek for an approach that can align the interferences in IA I k , such that k I  is linearly independent of k S  while satisfying the following condition:

$$\dim ( \tilde { S } _ { k } ) + \dim ( \tilde { I } _ { k } ) \leq M \quad \ \ ( 6 ) \quad ^ { \Psi \, \underline { \underline { e } } }$$

where  dim   A corresponds to the cardinality of a basis for a vector space A .

Suppose   SIA 1 , , , , , , , I = i i i k k M Z k k n k Z k      denote  a  set of  basis  vectors  that  span k I  with SIA dim( ) . I = -k k k Z M S   Therefore,           IA , , , , I j k j k j k j k k k k                       H v H v   should be aligned onto SIA I k , resulting in the following set of alignment equations at receiver k :

$$\Pi _ { k } ^ { [ j ^ { * }, k ^ { * } ] } \mathbf v _ { \ell ^ { * } } ^ { [ j ^ { * }, k ^ { * } ] } & = \alpha _ { ( \ell ^ { * } - 1 ) \cdot Z _ { k } + 1, k } ^ { [ j ^ { * }, k ^ { * } ] } \bar { i } _ { 1, k } + \cdots & \quad \text{if there;} \\ & + \alpha _ { ( \ell ^ { * } - 1 ) \cdot Z _ { k } + n, k } ^ { [ j ^ { * }, k ^ { * } ] } \bar { i } _ { n, k } + \cdots + \alpha _ { \ell ^ { * } \cdot Z _ { k }, k } ^ { [ j ^ { * }, k ^ { * } ] } \bar { i } _ { Z _ { k }, k } & \quad \text{(7)} \quad \text{align} \\ & \mathbf v _ { \ell } ^ { [ j, k ] }$$

where        -1 , , k j k Z n k          are  the  coefficients  that  represent  the relative magnitude of vectors.

Concerning  the  form  of        -1 , , k j k Z n k          and   , i n k in  (7), there are two cases to be addressed: 1) both        -1 , , k j k Z n k          and   , i n k are  unknowns;  2)        -1 , , k j k Z n k          are  assumed  as  the arbitrary coefficients and   , i n k are unknowns. In [7], however, we have shown that both cases cannot guarantee the independency of k I  and k S  .  Furthermore, we have proposed the STS  alignment structure in (7), which ensures the independency  of k I  and k S  while  satisfying  (6).  The  STS structure  includes  two  parts:  first, SIA I k is constructed  by selecting the interference vectors in IA I k , i.e., SIA IA I I k k  , and then, IA IA SIA IA 1, , , , , , I -, I -I = i i i I k k k k k f k k Z k          ; second, each IA SIA , i I -I f k k k  is uniquely aligned on to one , i n k , giving only  one  coefficient      -1 , , k j k Z n k          to  be  non-zero  in  (7),  i.e.,  .          , -1 , , , , i k j k j k j k n k k Z n k                    H v   . Replacing , i n k with the detailed expression, a set of linear alignment equations that are formed at receiver k can be equivalently rewritten as

$$\Phi _ { k } & \overset { \triangle } { = } \left \{ \text{span} \left ( \mathbf H _ { k } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \mathbf v _ { \ell ^ { \prime } } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \right ) = \text{span} \left ( \mathbf H _ { k } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \mathbf v _ { \ell ^ { \prime } } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \right ) \right | \quad \text{ of close} \\ & \mathbf H _ { k } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \mathbf v _ { \ell ^ { \prime } } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \in \mathcal { I } _ { k } ^ { \text{SIA} }, \mathbf H _ { k } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \mathbf v _ { \ell ^ { \prime } } ^ { [ j ^ { \prime }, k ^ { \prime } ] } \in \mathcal { I } _ { k } ^ { \text{I} _ { k } } \dashv ^ { \text{SIA} } \right \} \quad \text{ the} \, \text{a}$$

where   1, k K  and k k     assures  that  the  interferences from the same transmitter are not aligned. Then, a complete set of linear alignment equations for system is given by   1 K k k    .

## B. Closed-form solutions

The  closed-form  transmitters     , j k V can  be  solved  from

$$\cdot$$

and 1 E E q q  , where P q and E q represent  a  set  of vertices  and  a  set  of  edges  in  subgraph q ,  respectively.  By analyzing IAC graph G , the necessary and sufficient conditions for solving  has been derived in [7], and can be summarized in the below:

 .  In  [7],  an  IAC  graph   , G P E  has  been  proposed  to analyze the solvability of  , where P and E represent a set of vertices and a set of edges, respectively. Furthermore, we have  shown  that G and  have  one-to-one  correspondence, i.e., each precoding vector   , j k v  and each alignment equation in  can be represented by one unique vertex and one unique edge in G , respectively, and vice versa. Note that IAC graph is different from a general representation of graph, as each edge in IAC graph holds a label to declare the index of MAC where the alignment  equation  is  formed.  Moreover,  as  each  variable   , j k v  may  not  appear  in  all  alignment  equations  in  ,  the equations  involving  the  same  subset  of  variables  has  been collected  into  one  subset.  In  other  words,  can  be  divided into several independent subsets, and solving the independent subsets respectively is equivalent to solving  . Correspondingly,  each  independent  subset  of  forms  one independent connected subgraph of G . Each  connected subgraph  has  no  isolated  vertex,  and  no  connection  to  other subgraphs.  For  each  connected  subgraph q ,  it  is  denoted  as   , G P E q q q  , such that   1 2 , , , G G G G Q   , 1 P P Q q q    Q  

Proposition 1. For a connected subgraph in IAC graph G , if and only if the vertices form at most one loop, the precoding vectors involved can always be solved.

$$\cdots \nu \cdots \varepsilon \, \varepsilon \\ \left \{ \nu _ { \ell } ^ { [ j, k ] } \right \} \colon$$

Then, it has been further proven that the solutions     , j k v  , obtained from  ,  can always guarantee the independence of k S  and k I  , which can be stated in the following proposition:

Proposition 2. The precoding vectors , j k v  solved from S  and

Proposition 1 can always lead to the independence of k k I  ,   1, k K  .

Finally, a necessary and sufficient condition for the existence of closed-form IAC transceivers has been proven, and can be summarized by the following theorem:

Theorem 1. In  the   , , K M J Gaussian interference MAC

system,  based  on  the  proposed  symbol-to-symbol  alignment scheme,  closed-form  IAC  solutions  exist  if  and  only  if  the following inequalities are satisfied:

$$\sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } + \max \left \{ d ^ { [ j ; k ^ { \prime } ] } \right \} _ { k ^ { \prime } \in [ k + 1, K ] } \leq M \quad \quad \ \ ( 9 ) \quad \text{ obtain}$$

$$\sum _ { k ^ { \prime } = k _ { \text{AC} } + 1 } ^ { K } \sum _ { j ^ { \prime } = 1 } ^ { N _ { k ^ { \prime } } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \leq M, \ k _ { \text{IAC} } = 1, 2, \cdots, K - 1 \quad ( 1 0 ) \quad \text{IV}.$$

$$\sum _ { j = 1 } ^ { N _ { 1 } } d ^ { [ j, 1 ] } + \sum _ { k = 1 } ^ { k _ { 1 A C } } ( k - 1 ) \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } + \sum _ { k ^ { \prime } = k _ { 1 A C } + 1 } ^ { K } ( k _ { 1 A C } - 1 ) \sum _ { j ^ { \prime } = 1 } ^ { N _ { k } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \quad ( 1 1 ) \quad \text{(1)} \quad \text{(closed-f)} \\ \leq k _ { 1 A C } \cdot M \quad \text{(NEP-hard)}$$

$$\text{$\quad $At last, as long as the conditions in Theorem $1$ are satisfied,} \\ \text{$the closed-form IAC solutions exist and can be found from IAC} \quad \text{tuple of} \\ \text{graph $G$. Since the interferences caused by the $1^{st}$ MAC can be} \\ \text{cancelled} \ \text{ immediately} \ \text{ at} \ \text{ the} \ \text{ 2} ^ { n d } \ \text{ to} \ \text{ the} \ \text{ $K$ -th} \ \text{ MACs}, \\ \left \{ \mathbf v _ { \ell } ^ { [ j, 1 ] } \Big | \forall \ell \in \Big [ 1, d ^ { [ j, k ] } \Big ], \forall j \in \Big [ 1, N _ { k } \Big ] \right \} \ \text{ will not appear in $\Psi$. Let} \\ \mathbf V = \left \{ \mathbf v _ { \ell } ^ { [ j, k ] } \Big | \forall \ell \in \Big [ 1, d ^ { [ j, k ] } \Big ], \forall j \in \Big [ 1, N _ { k } \Big ], \forall k \in \Big [ 2, K \Big ] \right \} \ \text{ denote} \\ \text{the set of precoding vectors in $\Psi$ as well as the set of vertices} \quad \text{system},..}$$

the set of precoding vectors in  as well as the set of vertices in G .  Therefore, each subset q  V V can be found by going through  'loop'  in  its  corresponding  subgraph G q ,   1, q Q  and   1 2 , , , Q  V V V V  . For the given system configuration   , , K M J and         , 1, , 1, j k k d j N k K     , construction  of  the  basis SIA I k as  well  as  selection  of  the alignment  pairs for each  equation  in (8) is not unique. Therefore, there may exist many different possible  , each of which  leads  to  a  different G . As  the  expression  of  the closed-form  solutions  depend  on  the  structure  of G , it  is difficult to explicitly give a general expression which can cover all the possibilities. Hence, we briefly give the procedures to obtain  the  closed-form  solutions  for  each  possibility  in  the below. More details on the explicit expressions of closed-form solutions for the different possibilities have been given in [8].

According to Proposition 1 , there are two types of subgraphs: one-loop case and no-loop case. For one-loop case, one precoding vector involved in the loop can be expressed by a  product  of  itself  and  one  full  rank  matrix,  and  thus,  this precoding vector can be chosen as any eigenvector of the full rank matrix. Then, the remaining precoding vectors represented in G q can be computed through the edge. For the no-loop case, we can just pick the direction of one precoding vector randomly and find the remaining precoding vectors through the edges.

$$& \text{and find the remaining preceding vectors through the edges. } & \text{$\frac{1}{k}$} \\ & \text{Furthermore, $\left\{v_{\ell}^{[j,1]}\left|\forall \ell \in \left [ 1, d ^ { [j,k]}\right], \forall j \in \left [ 1, N _ { k } \right ] \right \} $ can be found $ } & \text{$\frac{1}{k}$}$$

by  letting         1 ,1 ,1 1 1 I j j    V H  where 1 I  is  known  from

V . Once the transmitters           , , 1, , 1, , 1, j k j k k d j N k K           v   are solved, 1 { } I K k k   is determined  and  then,  the  receiver k U can  be obtained by   I k k   U  ,   1, k K   .

## IV. THE ACHIEVABLE DOFS WITH THE CLOSED-FORM IAC SOLUTIONS

In this section, we first derive the DoFs that can be achieved for   , , K M J MAC system with the proposed suboptimal yet closed-form  IAC  solutions,  denoted  as CS IAC DoF . As  it  is NP-hard to find the maximum achievable DoFs by IAC, we then derive a necessary condition that must be satisfied by any tuple of DoF,         , 1, , 1, j k k d j N k K     for  IAC, based on which an upper bound on the maximum achievable DoFs, denoted as upper IAC DoF , can be obtained.

## A. The achievable DoFs: DoF CS IAC

Theorem 2. In the   , , K M J Gaussian interference MAC system, the maximum achievable DoFs with the symbol-to-symbol alignment-based closed-form IAC solutions is  2 M and it is achieved when IAC 2 . k 

Proof: The  achievable  DoFs  can  be  derived  from  the necessary and sufficient conditions in Theorem 1. Substituting   , CS IAC 1 1 k K N j k k j DoF d      into (11) yields

$$\text{the} \underset { + } { \text{of} } \underset { k = 1 } { \sum } ^ { k _ { l A C } } ( k - 1 ) \overset { N _ { k } } { \underset { j = 1 } { \sum } } d ^ { [ j, k ] } + ( k _ { l A C } - 1 ) \left ( D o F _ { l A C } ^ { \text{CS} } - \overset { k _ { l A C } } { \underset { k = 1 } { \sum } } \overset { N _ { k } } { \underset { j = 1 } { \sum } } d ^ { [ j, k ] } \right ) \\ \text{the} \underset { i = 1 } { \sum } ^ { N _ { l } } \leq k _ { l A C } \cdot M - \overset { N _ { l } } { \underset { j = 1 } { \sum } } d ^ { [ j, 1 ] } \\ \text{ver}$$

After some algebraic manipulations, (12) can be equivalently expressed as

$$\text{-form} \\ \text{$\iota[8]$.} \\ \text{$es$ of} \\ \text{case,} \\ \text{$\text{$\text{$\text{$k^{\prime}=1}$} } } \quad ( k _ { \iota A C } - 1 ) \cdot \left ( D o F _ { \iota A C } ^ { \text{CS} } - M \right ) - \sum _ { k = 2 } ^ { k _ { \iota A C } } \left ( \sum _ { k ^ { \prime } = 1 } ^ { k } \sum _ { j ^ { \prime } = 1 } ^ { N _ { k ^ { \prime } } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } - \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) \\ \text{ed by} \\ \iota, \text{ this} \\ \text{e full} \\ \iota. \$$

We can then rewrite (13) as

$$\sum _ { k = 2 } ^ { k _ { l A C } } \left \{ \left ( D o F _ { l A C } ^ { \text{CS} } - \sum _ { k ^ { \prime } = 1 } ^ { k } \sum _ { j ^ { \prime } = 1 } ^ { N _ { k ^ { \prime } } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \right ) - \left ( M - \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) \right \} \\ \leq M - \sum _ { j = 1 } ^ { N _ { l } } d ^ { [ j, l ] }$$

Referring  to  the  STS  alignment  structure,  the  number  of linear alignment equations formed at receiver k is     , , IA SIA CS IAC 1 1 1 I I k k N N k j k j k k k k k j j DoF d M d                               

and hence, (14) becomes

$$\sum _ { k = 2 } ^ { k _ { \text{LAC} } } | \Phi _ { k } | \leq M - \sum _ { j = 1 } ^ { N _ { 1 } } d ^ { [ j, 1 ] } \quad \quad ( 1 5 ) \quad N _ { k _ { \text{LAC} } },$$

Partitioning IAC 2 k k k    as IAC IAC 2 2 3 k k k k k k          and substituting   1 ,1 CS 2 IAC 1 N j j DoF M d       into (15) yields

$$\ D o F _ { | \text{AC} } ^ { \text{CS} } \leq 2 M - \sum _ { k = 3 } ^ { k _ { | \text{AC} } } | \Phi _ { k } | \text{ \quad \quad } \text{(1)}$$

For  the  last  term  on  the  right-hand  side,  as IAC 3 0 , k k k     CS IAC DoF is  bounded  by  2 M and  furthermore,  the  bound  is tight when IAC 3 0 . In fact,  2 k k k     M can be achieved when IAC 3 0 , together with k k k     2 0 , implying that   IAC 2 . k  This completes the proof. 

In the sequel, using IAC graph   , G P E  ,  we provide an intuitive interpretation on the proof. For a general   , , K M J MAC system, if we increase the total number of transmitted data streams CS IAC DoF , the caused total number of interferences will  grow  much  faster  than CS IAC DoF . Correspondingly,  the number of edges grows much faster than that of the vertices in IAC graph G .  According  to Proposition  1 ,  in  order  for  the existence of closed-form solutions         , 1, , 1, j k k j N k K     V , G is allowed to have at most one loop at each subgraph G q , i.e., it requires that E P q q  ,   1, q Q  .  Therefore, CS IAC DoF cannot  be  increased  arbitrarily and  2 M can be achieved when E P q q  holds,   1, q Q  .

Assume that G is structured by following the same order as the  decoding  operation  in  IAC,  namely,  from  the  1 st to  the K -th MACs.  At  the  1   MAC,  each  interference  vector st IA SIA ,1 1 1 i I -I f  will be uniquely aligned onto one interference basis vector SIA ,1 1 i I n  and moreover, the alignment operation is not allowed between any two basis vectors. Therefore, a set of vertices which correspond to the interference vectors aligned onto ,1 i n have been connected to the reference vertex represented by ,1 i n ,  forming one connected subgraph with no loop. Then, a total of   1 ,1 SIA 1 1 I N j j M d     subgraphs have been formed, each of which has 1 E P n n   ,     1 ,1 1 1, N j j n M d           .  Hence,  each  subgraph  allows  only one  more  edge  and  then,  the  total  number  of  edges  added through  the  2 nd to K -th  MACs  should  be  no  more  than     1 ,1 1 N j j M d    , giving the inequality in (15).

Next,  we  briefly  illustrate  how 2 M is achieved  when IAC 2 . Recall that the total number of edges added through k  the 2 nd to K -th MACs should be no more than     1 ,1 1 N j j M d    . Together with IAC 3 0  for k k k     IAC 2 , k  then, the following inequality should be satisfied:

$$\sum _ { k = 2 } ^ { K } | \Phi _ { k } | = | \Phi _ { 2 } | \leq M - \sum _ { j = 1 } ^ { N _ { 1 } } d ^ { [ j, 1 ] }$$

Substituting IAC 2 k  into (10) yields   , 3 1 k K N j k k j d M      . Let   , 3 1 k K N j k k j d M      and  then, we have

$$& | \Phi _ { 2 } | = \left | I _ { 2 } ^ { I A } \right | - \left | \overline { I } _ { 2 } ^ { S I A } \right | \\ & \quad = \left ( \sum _ { k = 3 } ^ { K } \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) - \left ( M - \sum _ { j = 1 } ^ { N _ { 2 } } d ^ { [ j, 2 ] } \right ) \quad \quad ( 1 8 ) \\ & \quad = \sum _ { j = 1 } ^ { N _ { 2 } } d ^ { [ j, 2 ] }$$

Substituting (18) into (17), we have     1 2 ,1 ,2 1 1 N N j j j j d d M       . We can set     1 2 ,1 ,2 1 1 N N j j j j d d M       , together with   , 3 1 k K N j k k j d M      . Then, a total of CS IAC 2 DoF M  can be achieved.

B. Upper bound on the maximum achievable DoFs with IAC: upper IAC DoF

IAC inherits  the  NP-hardness from IA  on  maximizing  the total achievable DoFs for the general system configurations. In this  subsection,  we  first  give  a  necessary  condition  for  IAC feasibility  in  MAC  channel,  which  is  an  extension  of  the existing  results  in  [2][3]  and  [9].  Based  on  the  necessary feasibility condition of IAC, we then derive an upper bound on the  total  DoFs  that  can  be  achieved  with  IAC,  denoted  as upper IAC DoF .

Theorem 3. In the   , , K M J Gaussian interference MAC system, any tuple of DoFs         , 1, , 1, j k k d j N k K     that is achievable with IAC must satisfy the following inequalities:

      , , 1 , , , , 1, k N j k j k k j d d M k k k k j N               (19)

$$\sum _ { k ^ { \prime } = k _ { \iota \mathcal { C } } + 1 } ^ { K } \sum _ { j ^ { \prime } = 1 } ^ { N _ { k ^ { \prime } } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \leq M, \ \ k _ { \iota \mathcal { C } } \leq K - 1$$

$$\nu \searrow 1 \beta \cdot \text{sub} \\ + \sum _ { [ j ^ { \prime }, k ^ { \prime } ] ; \{ k, \cdot \} \in \Upsilon _ { \text{sub} } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \left ( M - d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \right ) \quad \text{(} \\ \geq \sum _ { \{ k, [ j ^ { \prime }, k ^ { \prime } ] \} \in \Upsilon _ { \text{sub} } } \left ( \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) d ^ { [ j ^ { \prime }, k ^ { \prime } ] }$$

$$\sum _ { k ^ { \prime } = k _ { \text{LAC} } + 1 } ^ { K } \sum _ { j ^ { \prime } = 1 } ^ { N _ { k ^ { \prime } } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \leq M, \quad k _ { \text{LAC} } \leq K - 1 \quad \ ( 2 0 ) \quad \ \ \forall \left [ j ^ { \prime }, \right ] \\ \sum _ { k ^ { \prime } \{ i \}, [ j ^ { \prime }, k ^ { \prime } ] \} \in \Upsilon _ { s u b } } \left ( \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) \left ( M - \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
 \quad + \sum _ { [ j ^ { \prime }, k ^ { \prime } ] \} \{ k, i \} \in \Upsilon _ { s u b } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \left ( M - d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \right ) \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

where sub  is a subset of indices defined by            IAC , , : 1, , 1, , 1, k k j k k k k k K j N            ,  and     , , j k   or   , k  denote  that  there  exists k or   , j k   such that    sub , , k j k    .

Proof : We first prove the inequality in (19). Referring to the MAC  channel given in system descriptions, we have     , 1 k N j k k j rank d    U and       , , j k j k rank d      V .  As  each element of channel matrix   , j k k   H drawn i.i.d. from a continuous distribution,   , j k k   H is generic and hence,         , , , j k j k j k k rank d        H V . Together with     , , j k j k k k      U H V 0 , the transmitter k U must satisfy         , , span span j k j k k k      U H V and  thus,  (19)  is  true.  The inequality (20) is obvious by the definition of IAC k , i.e., for any feasible  IAC  strategy,  there  always  exists  a IAC k .  Now  we prove (21) for IAC in MAC channel by extending the existed proof  for  IA  in  [2][3]  and  [9],  the  total  number  of  scalar variables  should  be  no  less  than  the  total  number  of  scalar equations for any subset sub  . For any certain    sub , , k j k    , there is     , , j k j k H k k      U H V 0 . Recall     , 1 k N j k k j rank d    U and       , , j k j k rank d      V . Then, the total  numbers  of  scalar  variables  in k U and   , j k   V ,  after eliminating superfluous variables, are        , , 1 1 k k N N j k j k j j d M d      and       , , j k j k d M d      , respectively.  The  details  of  the  superfluous  variables  can  be referred  to  [1]  and  [3].  As  any  combination  of  one  column vector  in k U and  one  column  vector  in   , j k   V forms  one equation, the total number of scalar equations is       , , 1 k N j k j k j d d     . As  the interferences received  at the   IAC 1 k  -th to K -th MACs are not required to be aligned in IAC,  only counts the 1 st to IAC k -th MACs, i.e.,

      IAC : , , 1, k j k k     . Furthermore, since the interferences caused by 1 st to IAC k -th MACs can be immediately cancelled at k -th MAC,  only includes the remaining interferences, i.e.,     , : , j k k     , where     1, , 1, k k k K j N       . This completes the proof of (21). 

In  (21),  there  exist  a  total  of IAC 1 1 2 1  subsets, k K k k k k N              each of which has to be checked to identify the achievability of a  tuple  of  DoFs         , 1, , 1, j k k d j N k K     . Then,  the underlying computational complexity will be prohibitive and thus, the upper bound given by Theorem 3 is hard to obtain. Meanwhile,  if  we  let sub    , the  following  infeasibility condition  can  be  configured  from  (21):  any  tuple  of  DoFs         , 1, , 1, j k k d j N k K     is not achievable if

$$\colon & \text{to the} \quad \sum _ { k = 1 } ^ { k _ { I A C } } \left ( \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) \left ( M - \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) + \sum _ { k = 2 } ^ { K } \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \left ( M - d ^ { [ j, k ] } \right ) \\ s \text{ each} \quad & < \sum _ { k = 1 } ^ { k _ { I A C } } \left \{ \left ( \sum _ { j = 1 } ^ { N _ { k } } d ^ { [ j, k ] } \right ) \left ( \sum _ { k ^ { \prime } = k + 1 } ^ { K } \sum _ { j ^ { \prime } = 1 } ^ { N _ { k ^ { \prime } } } d ^ { [ j ^ { \prime }, k ^ { \prime } ] } \right ) \right \} \\ \text{rom } a$$

Then, an upper bound on the maximum achievable DoFs can be  derived  by  solving  (22)  with  equality.  However,  it  is  not straightforward to obtain the analytical expression of upper IAC DoF , and so a numerical solution of upper IAC DoF is given for comparison in next subsection.

## C.Comparison of DoFs:  DoF CS IAC vs.  DoF upper IAC

In  this  subsection,  the  maximum  achievable  DoFs  of  the proposed closed-form IAC solutions, given by CS IAC 2 DoF M = , is compared with the upper bound of the general IAC, denoted as upper IAC DoF . Numerical results are given to show  the comparison between CS IAC DoF and upper IAC DoF . We first estimate upper IAC DoF from  (22).  In   , , K M J MAC channel,  we  fix K and M while generating    1 , k N k K  and         1 1 , , , , j k k d j N k K   randomly by following the discrete uniform distributions,   1, ~U k N M and      1 int , ~U , j k k d M N ,  respectively.  Notice  that J can  be obtained by 1 K k k J N    . For the tuple of DoFs         , 1, , 1, j k k d j N k K     , if (22) does not hold true, we have   , upper IAC 1 1 = k K N j k k j DoF d     .

upper upper

Fig 2.  The CDF of CS IAC DoF as varying M and K

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00248v1-figure-d330652e-c1b4-4932-871e-e8ba73ea72c1.jpg)

We calculate the cumulative distribution function (CDF) of upper IAC DoF by  10 4 Monte Carlo runs. In each run, IAC k can be calculated by its definition. As the interferences require to be aligned only when no fewer than three cells interfere with each other,  we  set 3 .  Furthermore,  we  consider K  7    by K  assuming that each cell cooperates with the cells only in its first tier in cellular network.

Fig. 2 shows the CDFs of upper IAC DoF ,     upper IAC F Pr = x DoF x  , for 2,4,6,8 . Note that there is M  no CDF curves for 5,6,7  in Fig. 2 (a), because with only K  two Tx/Rx antennas, IAC cannot be achieved by more than 4 MACs. Since     upper IAC Pr F x DoF x   ,  the  upper  bound  of DoFs for general IAC is given as     upper -1 IAC 1 DoF F   .  It  is observed  from  Fig.  2  that  the  upper  bound  is  given  by   upper IAC 2 DoF M   when 3 .  An  intuitive  explanation  on K  this result follows in the below. Let us first consider the IA case in the 3-user interference channel, where each of Tx and Rx has M antennas. The two interferers can be considered virtually as a  single  one  with  the  alignment  operation,  even  while  each receiver k sees two  interferers. For  example,  receiver  1 virtually regards  transmitter  2  as  the  only  interferer  and receiver 2 virtually regards transmitter 3 as the only interferer, while  receiver  3  virtually  regards  transmitter  1  as  the  only interferer. For a successful decoding, a sum of the simultaneous data streams for each combination in the above should be no more  than M .  Therefore,  given  an  extreme  assumption  that interferences can be always aligned, the maximum total number of simultaneous data streams through IA in 3-user interference channel will be  3 2 . Then, following the same principle, let M us look into the IAC case for three interfering MACs. Also with IA operation, receiver 1 virtually regards the 2nd MAC as a massive interferer and hence, a sum of the simultaneous data streams for the 1st MAC and 2nd MAC should be no more than M . For receiver 2, since the interference effect caused by the 1st MAC has been subtracted by IC operation, it only regards the 3rd  MAC  as  an  interferer.  Similarly,  a  sum  of  the simultaneous  data  streams  for  the  2nd  MAC  and  3rd  MAC should be no more than M . For receiver 3, however, it will be different in the sense that the maximum of M data streams can be transmitted, as no interferences exist due to the IC operation.

Fig 3.  The gap ratio IAC g for 2,4,6,8 M 

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00248v1-figure-9fdb3851-8a1e-4833-b9d4-e051437e3403.jpg)

Therefore, by combining the results of three MACs, an upper bound of 2 M can be obtained. Finally, together with CS IAC 2 DoF M  , it indicates  that  our  proposed  closed-form solutions  can  meet  the  upper  bound  when 3 .  This  also K  illustrates that our proposed scheme has made a full use of the whole  spatial  dimension  characterized  by  three  interfering MACs.

$$\text{MACs.} \quad & \text{Large } \text{nu} \\ \text{Now, we present the numerical results to compare } \text{Do} F _ { \text{LAC} } ^ { \text{CS} } \text{ to } \text{guarante} \\ \left ( \text{Do} F _ { \text{LAC} } ^ { \text{upper} } \right ) ^ { * }. \text{To check their difference, we define the gap ratio} \\ \text{as } g _ { \text{LAC} } = & \left [ \left ( \text{Do} F _ { \text{LAC} } ^ { \text{upper} } \right ) ^ { * } - \text{Do} F _ { \text{LAC} } ^ { \text{CS} } \right ] \Big / \left ( \text{Do} F _ { \text{LAC} } ^ { \text{upper} } \right ) ^ { * }. \text{As shown in} \\ \text{Fio} \ 3 \text{ it is observed that } \varrho \dots = 0 \text{ for } K = 3 \text{ confirmino that}$$

Moreover, the curve IAC g increases yet eventually converges to  a  constant  as K increases,  which  indicates  the  maximum value of IAC g by a diamond mark in Fig. 3. We observe from these results that the capacity gap increases with both K and M . However,  our  proposed  closed-form  solution  can  achieve  at least 66.6% of the upper bound on the capacity, even for the large  number  of  antennas.  In  fact,  its  performance  can  be guaranteed within 20% of the upper bound with a small number of  K,  e.g., 4 .  Note  that  some  values  of K  IAC g are  not shown, simply because IAC cannot be applied to some values of K .

Fig. 3, it is observed that IAC 0  for g  3 , confirming that K  our proposed closed-form solutions have achieved the upperbound when 3 . For all other cases, we observe that K  CS IAC DoF can reach approximately 66.6% of upper IAC DoF .

## V. CONCLUSION

Following  our  earlier  proposals  on  the  closed-form  IAC solutions for   , , K M J Gaussian interference MAC channel, this paper aims to derive the total DoFs that can be achieved by

them. Instead of the specific configuration that has to be the same number of data streams for all transmitters, a general tuple of DoFs         , 1, , 1, j k k d j N k K     has been investigated. We  have  shown  that  regardless  of K and J , a  total  of CS IAC 2 DoF M  can be achieved. The results also hold true for the K -user MIMO  interference  channel,  which can be immediately reduced from the MAC channel. In the existing works on the total achievable DoFs obtained by IA in K -user MIMO interference  channel  [2,3],  the  maximum  total  DoFs of 2   1 MK K  is  achieved  only  by  a  specific  configuration where each link has the same target DoFs. For a general tuple of DoFs, however, there only exists an upper bound on the total achievable DoFs, which given as ( 2 1 ). In fact, this upper M  bound is not tight since it is obtained by easing the inequality constraint.  As  compared  with  these  results,  our  closed-form IAC solutions improve the total achievable DoFs over IA for both specific and general cases. More interestingly, CS IAC 2 = DoF M can  be  achieved  only  with IAC 2 .  It  implies k  that  our  improvement  can  be  achieved  just  by  sharing  the decoded signals of only two receivers through a backhaul link for cancellation. In other words, additional capacity has been obtained only by a reasonable amount of complexity.

We have evaluated our results by referring to the  optimal IAC  solutions.  As  it  is  NP-hard  to  derive  the  maximum achievable DoFs by optimal IAC solutions, its upper bound has been  derived  for comparison  by  relying  on  a  necessary feasibility condition for IAC, which is just an extension of the existing  IA  result.  As  sufficiency  of  the  necessary  condition remains  unknown,  the  tightness  of  the  upper  bound  has  not been proven until now. Furthermore, it is quite challenging to check  the  necessary  condition  for  each  subset  of  alignment equations. Therefore, we derive an upperbound by checking the complete set of alignment equations, which makes the upper bound generally looser than the one obtained by checking each subset.  The  numerical  results  have  shown  that  the  proposed closed-form IAC solutions can achieve the upper bound for the case with three interfering MACs, and can achieve approximately 66.6% of the upper bound for other cases with more than three MACs. As this rather large gap seems to be mainly attributed to the loose upper bound, our future work will be also focused on deriving a tighter upper bound.

## REFERENCES

- [1] C.  M.  Yetis,  T.  Gou,  S.  A.  Jafar,  and  A.H.  Kayran,  "On  feasibility  of interference alignment in MIMO interference networks," IEEE Trans. on Signal Processing , vol. 58, no. 9, pp.4771-4782 , Sep. 2010.
- [2] G.  Bresler,  D.  Cartwright,  and  D.  Tse,  'Feasibility  of  Interference Alignment  for  the  MIMO  Interference  Channel,' IEEE Trans.  On Inf. Theory , vol. 60, no. 9, pp.5573-5586, Sep. 2014.
- [3] M.  Razaviyayn,  G.  Lyubeznik,  and  Z.-Q.  Luo,  'On  the  degrees  of freedom achievable through interference alignment in a MIMO interference channel,' IEEE Transactions on Signal Processing , vol. 60 no. 2, Page 812-821, Feb. 2012.
- [4] M. Razaviyayn, M.Sanjabi, and Z.-Q. Luo, 'Linear transceiver design for interference alignment: complexity and computation,' IEEE Trans. Inf. Theory , vol. 58, no. 5, pp. 2896-2910, May. 2012.
- [5] S.  W.  Peters,  R.  W.  Heath,  'Interference  alignment  via  alternating minimization,'  in Proc.  2009  IEEE  Int.  Conf.  Acoust.,  Speech  Signal Process (ICASSP) , Apr, 2009.
- [6] K. Gomadam, V. R. Cadambe, and S. A. J afar, 'A distributed numerical approach to interference alignment and applications to wireless interference  networks,' IEEE  Trans.  on  Inform.  Theory ,  vol.57,  no.6, pp.3309-3322, Jun. 2011.
- [7] X. Qu and C.G. Kang, "A closed-form solution to implement interference alignment  and  cancellation  for  a  gaussian  interference  multiple  access channel," IEEE Trans. Wireless Commun., vol.  13,  no.  2,  pp.  710-723, Feb. 2014.
- [8] X. Qu and C.G. Kang, 'A closed-form transceiver design for interference alignment  and  cancellation  in  MIMO  interference  channel,' Internal technical report.
- [9] L.  Ruan,  V.K.N.  Lau,  and  M.Z.  Win,  'The  feasibility  conditions  for interference alignment in MIMO networks,' IEEE Trans. Signal Process. , vol.61, pp.2066-2077, Apr. 2013.
Qu Xin Chung G. Kang
Achievable Degrees of Freedom for Closed-form Solution to Interference Alignment and Cancellation in Gaussian Interference Multiple Access Channel
A combined technique of interference alignment (IA) and interference
cancellation (IC), known as interference alignment and cancellation (IAC)
scheme, has been proposed to improve the total achievable degrees of freedom
(DoFs) over IA. Since it is NP-hard to solve the transceiver under a given
tuple of DoFs or to maximize the total achievable DoFs in the general system
configuration by IA (or IAC), the optimal transceiver cannot be obtained in
polynomial time. Meanwhile, it has been known that a closed-form yet suboptimal
transceiver can be designed for IAC by employing a symbol-to-symbol (STS)
alignment structure. As its performance has not been known yet, we aim to
derive the total DoFs that can be achieved by such suboptimal but closed-form
IAC transceivers for Gaussian interference multiple access channels with K
receivers and J users (transmitters), each with M antennas. Our analysis shows
that the closed-form IAC transceivers under consideration can achieve a maximum
total achievable DoFs of 2M, which turns out to be larger than those achieved
in classical IA, e.g., 2MK/(K+1) DoFs by a specific configuration where each
link has the same target DoFs. Moreover, considering the NP-hardness of
deriving the maximum total achievable DoFs with the optimal IAC transceiver,
its upper bound has been derived for comparison with the results of our
closed-form IAC transceiver. Numerical results illustrate that its performance
can be guaranteed within 20% of the upper bound when the number of multiple
access channels are relatively small, e.g., K <=4.