Feasibility Conditions for Interference Alignment

The degrees of freedom of MIMO interference networks with constant channel coefficients are not known in general. Determining the feasibility of a linear interference alignment solution is a key step toward solving this open problem. Our approach in this paper is to view the alignment problem as a system of bilinear equations and determine its solvability by comparing the number of equations and the number of variables. To this end, we divide interference alignment problems into two classes - proper and improper. An interference alignment problem is called proper if the number of equations does not exceed the number of variables. Otherwise, it is called improper. Examples are presented to support the intuition that for generic channel matrices, proper systems are almost surely feasible and improper systems are almost surely infeasible.


I. INTRODUCTION
The degrees of freedom (DoF) of wireless interference networks represent the number of interference-free signalingdimensions in the network. In a network with K transmitters and K receivers and non-degenerate channel conditions, it is well known that K non-interfering spatial signaling dimensions can be created if the transmitters or the receivers are able to jointly process their signals. Cadambe and Jafar [1] recently introduced the idea of interference alignment for the K-user wireless interference network with time-varying/frequencyselective channel coefficients, and showed that K/2 spatial signaling dimensions are available inspite of the distributed nature of the network which precludes joint processing of signals at transmitters or receivers. While a number of interference alignment solutions have appeared since [1] for different channel settings, many fundamental questions remain unanswered. One such problem is to determine the feasibility of linear interference alignment for MIMO interference networks with constant channel coefficients. It is this open problem that we address in this paper.
Suppose we denote by (M × N, d) K , the K-user interference network where every transmitter has M antennas, every receiver has N antennas and each user wishes to achieve d DoF. We call such a system a symmetric system. Consider the following examples.
• (2 × 2, 1) 3 -It is shown by [1] that the in the 3user interference channel with 2 antennas at each node, each user can achieve 1 degree of freedom by linear † The author is supported in part by The Scientific and Technological Research Council of Turkey (TUBITAK). The author is on leave at University of California, Irvine.
interference alignment, i.e. by linear beamforming at the transmitters and linear combining at the receivers. • (5×5, 2) 4 -Consider the 4-user interference channel with 5 antennas at each user. Suppose we wish to achieve 2 DoF per user, for a total of 8 network DoF. An analytical solution to this problem is not known but numerical evidence in [2] clearly indicates that a linear interference alignment solution exists. Numerical algorithms are one way to determine the feasibility of linear interference alignment. But, is there a way to analytically predict the feasibility of alignment? In other words, without running the numerical simulation could we have predicted whether a linear interference alignment solution will exist for the (5 × 5, 2) 4 system? • Now consider three distinct systems -(6 × 4, 2) 4 , (7 × 3, 2) 4 , (8×2, 2) 4 . Are these systems feasible? Clearly, the last one, (8 × 2, 2) 4 is feasible, because simple transmit zero-forcing is enough to eliminate the interference at every receiver. Is the feasibility of (8 × 2, 2) 4 case related to the feasibility of other cases where each transmitter successively donates one antenna to the receiver? We will show that these three systems and the (5 × 5, 2) 4 case belong to the same group.
In this paper, we address all these questions, as well as more complex asymmetric cases where each node may have different number of antennas and each user may demand different number of degrees of freedom. The basic approach is to consider the linear interference alignment problem formulation as a system of bilinear equations. We determine the correct way to count the number of variables and equations for a general MIMO interference alignment problem. Then, based on the number of variables and equations we classify the system as either proper (number of equations does not exceed number of variables), or improper (number of equations exceeds the number of variables), with the intuitive understanding that proper systems are almost surely feasible, and improper systems are almost surely infeasible.
Aside from the detailed conditions that classify a general (asymmetric) system as proper or improper, our analysis yields a useful rule of thumb for symmetric systems (M × N, d) K . We find that donating an antenna from each transmitter to the corresponding receiver, or vice versa, does not change the nature of the system (proper or improper), provided every node still has at least d antennas. For example, consider the system (2 × 3, 1) 4 . Is this system proper? While this question may be difficult to answer at first, now suppose we transfer one antenna from each transmitter to its corresponding receiver, to obtain the system (1 × 4, 1) 4 . This system is clearly proper, because simple zero-forcing achieves 1 degree of freedom for each user in this system. This tells us that the system (2 × 3, 1) 4 is also proper. Thus, the following are groups of proper systems, related by the rule of thumb defined above.
The first and last members of each group are easily seen to be proper (because a simple zero-forcing solution exists), thereby also determining the status of the rest of the members of the group. Improper systems can be similarly grouped as well. Completely asymmetric cases require a more sophisticated set of feasibility conditions. The analysis is supported by numerical results for a wide variety of cases, including the specific examples listed above. We begin with the system model.

II. SYSTEM MODEL
We consider the same K-user MIMO interference channel as considered in [2]. The received signal at the n th channel use can be written as follows: ) denotes the Kuser MIMO interference network, where the k th transmitter and receiver have M k and N k antennas, respectively and the k th user demands d [k] DoF. As defined earlier, (M × N, d) K denotes the K-user symmetric MIMO interference network, where each transmitter and receiver has M and N antennas, respectively, and each user demands d DoF, so that the total DoF demand is Kd. Some sample asymmetric and symmetric systems are shown in Fig. 1.

III. LINEAR INTERFERENCE ALIGNMENT SCHEME
In interference alignment precoding, the transmitted signal from the k th user is vector that denotes the d [k] independently encoded streams transmitted from the k th user. The M [k] ×d [k] precoding filters V [k] are designed to maximize the overlap of interference signal subspaces at each receiver while ensuring that the desired signal vectors at each receiver are linearly independent of the interference subspace. Therefore, each receiver can zeroforce all the interference signals without zero-forcing any of the desired signals. The zero-forcing filters at the receiver are denoted by U [k] . In [2], it is shown that an interference alignment solution requires the simultaneous satisfiability of the following conditions: where † denotes the conjugate transpose operator. Very importantly, [2] explains how the condition (2) is automatically satisfied almost surely if the channel matrices do not have any special structure, ) and are designed to satisfy (1), which is independent of all direct channels H [kk] . The scenarios where it is difficult to theoretically determine the feasibility of interference alignment can be evaluated numerically using an iterative algorithm proposed in [2]. In this work, we develop analytical criteria to predict the feasibility of interference alignment. Our approach is to count the number of equations and variables in (1). We assume generic MIMO channels with no structure and force the required ranks of the transmit and receive filters by design. Thus, (2) is satisfied automatically and we only need to count the number of variables and equations for (1).

IV. PROPER SYSTEM
The notion of a proper network is based on counting the number of equations and the number of variables involved in the bilinear equations (1). While the formal definition appears later, put simply, the system network is proper if and only if the cardinality of every subset of the equations is less than or equal to the number of variables involved in that subset of equations. Otherwise, the network is considered improper. The reason for this classification is the following intuition that forms the basis of our approach in this paper.
Key Insight : The interference alignment problem is almost surely feasible for proper systems and almost surely infeasible for improper systems.
Instead of a formal proof, we refer to Bezout's theorem, which states that a system of m generic polynomial equations in m variables will almost surely have as many common solutions as the product of the degrees of the polynomials. For our case, it suffices if there is one solution. The feasibility conditions in our case correspond to a system of polynomial equations, whose generic nature is due to the generic channel matrices. Due to the special bilinear form of the equations it needs to be shown that the polynomials are sufficiently generic. We are able to construct the rigorous proof for the (2×3, 1) 4 case which is omitted here due to lack of space. We expect generalizations to all cases should be possible, albeit cumbersome.
Next we explicitly account for all equations and variables. Let us start with the total number of equations N e and the total number of variables N v .

A. Counting the Number of Equations N e and Variables N v
To obtain N e and N v , we rewrite the condition in (1) as follows: m are the transmit and the receive beamforming vectors (columns of precoding and interference suppression filters, respectively). N e is directly obtained from (3) as follows: However, calculating the number of variables N v is less straightforward. In particular, we have to be careful to not count any superfluous variables that do not help with interference alignment. At Thus, the columns of V [k] are the basis for the transmitted signal space. However, the basis representation is not unique for a given subspace. In particular, consider any full rank Then vectors. It is easy to argue that there is no other basis representation for the transmitted signal space with fewer variables.
Therefore, by eliminating all superfluous variables for the interference alignment problem, the number of variables to be designed for the precoding filter of the k th transmitter, [k] . Likewise, the actual number of variables to be designed for the interference suppression filter of the k th receiver, . As a result, the total number of variables in the network to be designed is:

B. Proper System Characterization
To formalize the definition of a proper system, we introduce some notation. We use the notation E mn kj to represent the equation The set of variables involved in an equation E are indicated by the function var(E). Clearly where | · | is the cardinality of a set. Using this notation, we denote the set of N e equations as follows: This leads us to the formal definition of a proper system.
In other words, for all subsets of equations, the number of variables involved must be at least as large as the number of equations in that subset. Condition (14) provides us a way to predict the feasibility of interference alignment in a general ) system. However, note that it can be computationally cumbersome because we have to test all subsets of the set of all equations. In most cases however, especially if the system is improper, simply comparing the total number of equations and the total number of variables may suffice.
Theorem 1: Example 1: Consider the (5 × 5, 3)(5 × 5, 2) 3 system, i.e. a 4-user interference networks where all nodes have 5 antennas, user 1 demands 3 DoF and users 2, 3, 4 demand 2 DoF each. There are a total of 60 equations, so that there are 2 60 − 1 subsets of the set of all equations. Testing each of them could be very challenging. However, since the total number of variables N v = 48 is less than the number of equations, the system is easily seen to be improper.
Similarly, one can sometimes identify the bottleneck equations in the system by checking the equations with the fewest number of variables, i.e., the equations involving the transmitters and receivers with the fewest antennas.
Example 2: As a simple example, consider the system (2 × 1, 1) 2 which is clearly feasible (proper) because simple zeroforcing is enough for achievability. However, now consider the (2 × 1, 1)(1 × 2, 1) system, which also has the same total number of equations N e and variables N v as the (2 × 1, 1) 2 system. Thus, only comparing N v , N e would lead one to believe that this system is proper. However, suppose we check E 11 12 which connects transmitter 2 and receiver 1, both of which have only one antenna each, i.e., let S = {E 11 12 } so that |S| = 1. However var(E 11 12 ) = 0. Thus, this system has an equation with zero variables, which makes it improper, and therefore infeasible.
Example 3: Several interesting cases emerge from applying the condition (15). For example, consider the 2 user interference channel (2 × 3, 1)(3 × 2, 1) where a total of 2 degrees of freedom are desired. It is easily checked that this system is proper and the achievable scheme is described in [3]. However, now consider the 4-user interference channel consisting of two sets of these channels, all interfering with each other (2 × 3, 1) 2 (3 × 2, 1) 2 which is a 4-user interference channel and a total of 4 degrees of freedom are desired. It is easily verified that this is a proper system, i.e. it satisfies (15). It turns out that a closed form solution for alignment can be found in this case. It is somewhat surprising that going from two users to four users simply doubled the degrees of freedom in this case, without any penalty for interference between the users in terms of degrees of freedom. Since in this paper our focus is only on feasibility and not on closed form solutions, we omit the details of this example.
In general, testing if a large asymmetric system is proper can be cumbersome. However, for the case of symmetric systems of the type (M × N, d) K , the process is much simpler. Remark: Theorem 2 implies that for every user to achieve d degrees of freedom in a K user interference channel, it suffices to have a total of M + N ≥ (K + 1)d antennas between the transmitter and receiver of a user. The antennas can be distributed among the transmitter and receiver arbitrarily, as long as each of them has at least d antennas. In particular, to achieve K degrees of freedom in a K user symmetric network we only need a total of K +1 antennas between the transmitter and receiver of each user. The system (2 × 3, 1) 4 is such an example.
Proof: Because of the symmetry each equation is involved with the same number of variables and any deficiency in the number of variables shows up in the comparison of the total number of variables versus the total number of equations. Plugging in the values of N v , N e computed earlier, we have the result of Theorem 2.
The following corollary shows the limitations of linear interference alignment over constant MIMO channels (with no symbol extensions).
Corollary 1: The ratio of the sum degrees of a proper (M × N, d) K system, normalized by a single user's degree of freedom in the absence of interference is bounded by: Proof: The proof is straightforward from the condition of Theorem 2.
Remark: For the case that M = N note that the total number of degrees of freedom for a proper system is no more than twice the number of degrees of freedom achieved by each user in the absence of interference. Note that for diagonal (time-varying) channels it was shown in [1] that the total number of degrees of freedom is K/2 times the number of degrees of freedom achieved by each user in the absence of interference. This result shows that the diagonal structure of the channel matrix is very helpful. Going from the case of no structure (arbitrary MIMO channels) to diagonal structure the ratio of total degrees of freedom to the single user degrees of freedom increases from a maximum value of 2 to K/2.
The following corollary identifies the groups of symmetric systems, which are either all proper or all improper. Example 7: The systems (1 × 4, 1) 4 , (2 × 3, 1) 4 , (3 × 2, 1) 4 , (4 × 1, 1) 4 are in the same group, formed by switching between transmit and receive antennas. It is easy to see that the (4 × 1, 1) 4 system is proper, because simple zero-forcing suffices to achieve the DoF demand. By virtue of being in the same group, the rest are proper as well.
Example 8: Consider a (2 × 8, 2) 4 symmetric system. Again, the DoF for this interference channel can be trivially obtained by zero-forcing at each receiver. By switching antennas from each transmitter to receiver, an equivalent (5 × 5, 2) 4 symmetric system of Example 6 is obtained, which is also proper.

V. NUMERICAL RESULTS
We tested numerous interference alignment problems, both symmetric and asymmetric, and especially including each of the examples presented in this paper, using the numerical algorithms of [2]. In every case so far, we have found the results to be consistent with the guiding intuition of this work, proper systems are feasible and improper systems are not.
In this section we provide numerical results for a few interesting and representative cases. The results are in terms of the leakage interference, as defined in [2] -i.e. the fraction of the interference power that is present in the dimensions reserved for the desired signal. The interference percentage at the k th receiver is evaluated as follows: where λ j denotes the smallest eigenvalue of a matrix, Tr denotes the trace of a matrix and Q [k] denotes the interference covariance matrix at the k th receiver: The numerator and the denominator of (18) are the interference and desired signal space powers at the k th receiver, respectively.
In Fig. 2, the interference percentages versus the total number of beams are presented. The total number of beams are started from the DoF of each network. Therefore, after the first point on the x-axis, interference percentage of each network is not zero. The non-zero interference percentage indicates that interference alignment is not possible.

VI. CONCLUSION
We propose an analytical method to predict the feasibility of interference alignment via linear schemes over constant MIMO channels that have no structure (i.e. no symbol extensions). Our approach to determine feasibility is to count the number of equations and variables. We define a system as proper if the number of variables is not smaller than the number of equations, and as improper otherwise, with the understanding that proper systems are feasible almost surely, while improper systems are almost surely infeasible. This observation follows from Bezout's theorem and the generic nature of the channel coefficients, and can be rigorously shown in some cases, to be included in the full paper. The full paper will also include closed form solutions for interference alignment for several cases, such as (2 × 3, 1) 2 (3 × 2, 1) 2 , (3 × 3, 1)(2 × 3, 1) 3 , (2 × 4, 1)(2 × 3) 3 , (2 × 4, 1) 2 (4 × 2, 1) 2 (3 × 3, 1) etc.

ACKNOWLEDGMENT
The first author would like to thank V. R. Cadambe at University of California, Irvine for valuable discussions on interference alignment.