I. INTRODUCTION

T HE capacity of wireless interference networks is a rapidly evolving research front, spurred in part by exciting breakthroughs such as the idea of interference alignment [2] which provides fascinating theoretical insights and shows much promise under idealized conditions. The connection to practical settings however remains tenuous. This is in part due to the following two factors. First, because of the assumption of precise channel knowledge, idealized studies often get caught in the minutiae of channel realizations, e.g., rational versus irrational values, that have little bearing in practice. Second, by focusing on the degrees-of-freedom (DoF) of fully connected networks, these studies ignore the most critical aspect of interference management in practice -the differences of signal strengths due to path loss and fading (in short, network topology). Indeed, the DoF metric treats every channel as essentially equally strong (capable of carrying exactly 1 DoF). So the desired signal has to actively avoid every interferer, whereas in practice each user needs to avoid only a few significant interferers and the rest are weak enough to be safely ignored. Therefore, by trivializing the topology of the network, the DoF studies of fully connected networks make the problem much harder than it needs to be. Non-trivial solutions to this harder problem invariably rely on much more channel knowledge than is available in practice. Thus, the two limiting factors re-enforce each other.

Evidently, in order to avoid these pitfalls, one should shift focus away from optimal ways of exploiting precise channel knowledge (which is rarely available), and toward powerful even optimal ways of exploiting a coarse knowledge of interference network topology. This line of thought motivates robust models of interference networks where only a coarse knowledge of channel strength levels is available to the transmitters and no channel phase knowledge is assumed. This is the multilevel topological interference management framework. It is a generalization of the elementary topological interference management (TIM) framework introduced in [3], wherein the transmitters can only distinguish between channels that are connected (strong) and not connected (weak).

A. Robust principles of interference management: Ignore, avoid

Existing wireless interference networks are mainly based on two robust interference management principles -1) ignore interference that is sufficiently weak, and 2) avoid interference that is not. In slightly more technical terms, ignoring interference translates into treating interference as noise (TIN) [4], [5], and avoiding interference translates into access schemes such as TDMA/FDMA/CDMA. Recent work has explored the optimality of both of these principles.

1) TIN: The optimality of the first principle, treating interference as noise when it is sufficiently weak, is discussed extensively. In [6], [7], [8], it is shown that in a so-called "noisy interference" regime, TIN achieves the exact sum capacity of interference channels. In [9], for general -user interference channels, it provides a broadly applicable TIN-optimality condition under which TIN is optimal from a generalized degrees-of-freedom (GDoF) perspective and achieves a constant gap (of no more than log(3 ) bits) to the entire capacity region. Remarkably, this result holds even if perfect channel knowledge is assumed everywhere. The GDoF-optimality result of TIN is also generalized to other channel models (e.g.,channels [10], [11], parallel channels [12], compound networks [13], MIMO channels [14], and 0090-6778 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCOMM.2021.3102623, IEEE Transactions on Communications 2 cellular networks [15], [16]) and is reformulated from a combinatorial perspective [17]. 2) TIM: The optimality of the second principle, avoidance, has been investigated most recently by [3], as the TIM problem. With channel knowledge at the transmitters limited to a coarse knowledge of network topology (which links are stronger/weaker than the effective noise floor), TIM is shown in [3] to be essentially an index coding problem [18]. TIM subsumes within itself the TDMA/FDMA/CDMA schemes as trivial special cases, but is in general much more capable than these conventional approaches. Remarkably, for the class of linear schemes, which are found to be optimal in most cases studied so far, and within which TIM is equivalent to the index coding problem, TIM is essentially an optimal allocation of signal vector spaces based on an interference alignment perspective [19]. Variants of the TIM problem have also been investigated, such as those under short coherent time [20], with alternating connectivity [21], [22], with multiple antennas [23], with transmitter/receiver cooperation [24], [25], with reconfigurable antennas [26], with network topology uncertainty [27], and with confidential messages [28].

B. TIM-TIN: Joint view of signal vector spaces and signal power levels

The two principles -avoiding versus ignoring interference -which are mapped to TIM and TIN, respectively, naturally correspond to interference management in terms of signal vector spaces and signal power levels. TIM uses the interference alignment perspective [3], [19] to optimally allocate signal vector subspaces among the interferers. Note that in order to resolve the desired signal from interference based on the signal vector spaces, the strength of each signal is irrelevant. What matters is only that desired signal and the interference occupy linearly independent spaces. TIN, on the other hand, optimally allocates signal power levels among users by setting the transmit power levels at transmitters and the noise floor levels at receivers. Thus TIN depends very much on the strengths of signals relative to each other. Associating TIM with signal vector space allocations and TIN with signal power level allocations within the multilevel TIM framework, we refer to the joint allocation of signal vector spaces and signal power levels as the TIM-TIN problem.

TIM-TIN Problem: With only a coarse knowledge of channel strengths available to the transmitters, we wish to carefully allocate not only the beamforming vectorfoot_1 directions (signal vector spaces) but also the transmit powers (signal power levels) to each of those beamforming vectors. The necessity of a joint TIM-TIN perspective is evident as follows. In vector space allocation schemes used for DoF studies, the signal space containing the interference is entirely rejected (zeroforced). This is typically fine for linear DoF studies because all signals are essentially equally strong, every substream carries one DoF, so any desired signal projected into the interference space cannot achieve a non-zero DoF. However, once we account for the difference in signal strengths in the GDoF framework, the signal vector space dimensions occupied by interference may not be fully occupied in terms of power levels if the interference is weak. So, non-zero GDoF may be achieved by desired signals projected into the same dimensions as occupied by the interference, where interference is weaker than desired signal. It is this aspect that we wish to exploit in this work. It is worthwhile noticing that within the multilevel TIM framework, in general the solution based on a combination of TIM and TIN is not optimal. For example, in [29] it has been shown that for -user symmetric interference channels, the GDoF optimal solution relies on rate splitting and superposition encoding at transmitters and (partial) interference decoding at receivers. 2 The appeal of joint TIM-TIN mainly lies in its implementation simplicity and wide applicability in existing wireless networks.

C. Overview of results

First, to address the TIM-TIN problem, an analytical baseline approach is presented. Because of the minimal channel knowledge requirements in the TIM and TIN settings, a robust combination of the two, denoted as TIM-TIN decomposition presents itself. Any given network is decomposed into a TIM component and a TIN component, containing only strong and weak interferers, respectively, and a direct multiplication of the signal dimensions available in each is shown to be achievable in the original network. In other words, the TIM solution identifies the fraction of the signal space that is available to each user, and within each of these available signal space dimensions, the TIN approach identifies the fraction of signal levels that are available to the same user. A product of the two fractions therefore identifies the net fraction of signal dimensions available to each user in this decomposition based approach. The optimality of this decomposition approach is also discussed for some non-trivial network settings.

Next, a distributed numerical approach is developed, which only needs local channel measurements to update transmit powers and beamforming vectors. The proposed algorithm, called ZEST, utilizes the reciprocity of wireless networks, and is guaranteed to be convergent in terms of GDoF. As a byproduct, the duality of the TIM-TIN problem is established. We also include modest numerical experiments that demonstrate superior GDoF performance and fast convergence of ZEST.

Notations: For a positive integer /, [/] , {1, 2,...,/}. For vectors u and v, we say that u dominates v if u v, where denotes componentwise inequality. For a matrix A, det(A) denotes its determinant, span(A) represents the space spanned by the column vectors of A, and A(8, 9) is the entry of A in the 8-th row and 9-th column. All logarithms are to the base

In the multilevel TIM framework, only a coarse knowledge of channel strength levels is available to the transmitters and no channel phase knowledge is assumed. The channel strength level knowledge at transmitters can either be perfect or quantized. We also assume that receivers have perfect channel state information. Apparently, multilevel TIM is a generalization of the elementary one in [3]. It also should be noted that unlike most previous works in pursuit of the coarse DoF metric where all non-zero channels are essentially treated as approximately equally strong (i.e., each non-zero channel carries one DoF), in the multilevel TIM framework, the main challenge lies in how to leverage the disparate channel strengths, and the more general GDoF metric is of interest. This progressive refinement (from DoF to GDoF) has been shown instrumental for capacity approximation of Gaussian interference networks in recent works [9], [10], [30], [31], where the GDoF result usually further serves as a stepping stone for the capacity characterization within a constant gap.

Below we define the problem of multilevel TIM with quantized channel strength levels, or quantized multilevel TIM (QM-TIM) in more details. 3 Note that in practice, the desired signal strength and interfering signal strength usually fall into different ranges, so it is reasonable to assume that desired links and interfering links have different quantization schemes. For direct channels, the channel strength levels are assumed to be large enough to guarantee a satisfying interference-free achievable rate. As a result, for direct links the quantized channel strength levels are always normalized to one ( i.e., U 88 = 1, 88 2[ ]) without loss of generality. While for interfering links, for better interference management, there are ; quantization thresholds C 1 ,C 2 ,...,C ; , where 0  C 1 < C 2 <. . .<C ; < 1. Hereafter, we denote the QM-TIM problem with the above quantization configuration by QM-TIM(C 1 ,C 2 ,...,C ; ). Apparently, the original TIM problem is a special case of QM-TIM, which can be denoted by QM-TIM(0). As another example, the simplest setting of QM-TIM beyond the elementary one is QM-TIM(C 1 ,C 2 ). One natural choice for the two quantized thresholds could be C 1 = 0 and C 2 = 0.5. In this case, we have the following three kinds of interfering links: 1) Weak interfering links: the interfering links that are no stronger than the noise floor; 2) Medium interfering links: the interfering links whose channel strength level value falls into the range from 0 to 0.5; 3) Strong interfering links: the interfering links whose channel strength level is no less than 0.5.

III. TIM-TIN PROBLEM FORMULATION

In this section, we formulate the TIM-TIN problem within the multilevel TIM framework formally. As mentioned before, with only a coarse knowledge of channel strengths available to the transmitters, in the TIM-TIN problem, we allocate not only the beamforming vectors but also the transmit powers to each of those beamforming vectors, in order to jointly optimize both signal vector space and signal power level allocations.

For a -user interference channel in (1), over = channel uses, Transmitter 8 sends out 1 8 (1 8  =) independent scalar data streams, each of which carries one symbol B 8,; and is transmitted along an = ⇥ 1 beamforming vector v 8,; , ; 2[

Assume that all symbols B 8,; are drawn from independent Gaussian codebooks, each with zero mean and unit power, and the beamforming vectors v 8,; are scaled to have unit norm. Over = channel uses, Receiver : obtains an = ⇥ 1 vector

;=1 p % U :8 4 9\ :8 p % A 8,; v 8,; B 8,; + z : , where z : is an = ⇥ 1 zero mean unit variance circularly symmetric AWGN vector at Receiver :, % A 8,; is the transmit power for ;-th data stream of User 8. Due to the unit power constraint, we require A 8,;  0. For User :, the covariance matrix of the desired signal is

)% A :,; +U :: . The covariance matrix of the net interference-plus-noise is

where I is an = ⇥ = identity matrix, and

)% A 8,; +U :8 is the covariance matrix of the interference from Transmitter 8 < :. Given the beamforming vectors of each transmitter and power allocations of all data streams, as in the TIM-TIN problem the receivers do not attempt to decode interference from unintended transmitters, for User : 2[ ] the achievable rate per channel use is given byfoot_4

and the achievable GDoF value 3 : is

Next, we simplify the achievable GDoF expression into a more intuitive form. Consider a term of the type log

) is an = ⇥ 1 vector. Without loss of generality, assume ^1 ^2 ... ^< 0. Consider the vectors v 8 's one by one. For v 1 , we relabel it as v ⇧(1) and correspondingly its power exponent ^1 as ^⇧(1) . For v 2 , if it falls into span(v ⇧( 1) ), we remove it and then proceed to v 3 ; otherwise, we relabel it as v ⇧(2) and correspondingly ^2 as ^⇧ (2) . We repeat this operation for each vector. In other words, for v 8 , if it falls into span(v ⇧(1) ,...,v ⇧(;) ) (i.e., the space spanned by all previous linearly independent vectors obtained from {v 1 ,...,v 8 1 }), we remove it and then proceed to v 8+1 ; otherwise, we relabel it as v ⇧(;+1) and correspondingly its power exponent ^8 as ^⇧(;+1) . Finally, we have W  = linearly independent beamforming vectors V ⇧ = {v ⇧(1) ,...,v ⇧(W) } and their associated power exponents P ⇧ = {^⇧ (1) ,...,^⇧ (W) }. With those definitions, we have the following lemma.

Lemma 1: Suppose that v 8 , 8 2[ <] are = ⇥ 1 vectors, and ^1 ^2 ... ^< 0. We have

The proof of Lemma 1 is given in Appendix A. Now we can proceed to the following lemma. Lemma 2: In the TIM-TIN problem, given the beamforming vectors and the power allocations for each user, zero-forcing with successive cancellation (ZF-SC) achieves the maximal GDoF value of each user given by (3). 5The proof of Lemma 2 is deferred to Appendix B. With Lemma 2, to maximize the achievable GDoF in the TIM-TIM problem, the remaining challenge is choosing beamforming vectors and their powers for each user judiciously. To address this problem, in the following we develop two approaches, i.e., an analytical decomposition approach and a numerical distributed approach.

Example 1: To help understand Lemma 1 and 2, consider a 3-user interference channel, in which over 2 channel uses User 1, 2 and 3 deliver 2, 2 and 1 data streams, respectively. Given the beamforming vectors, the transmitted power allocated to each symbol and channel strength levels for each link, the received signal at Receiver 1 is depicted in Fig. 1, where v 2,1 and v 3,1 are aligned along one direction. The length of the vector represents the received power of the carried symbol. We have

)] log % and

. Following Lemma 1, we have

So the achievable GDoF value of User 1 is

Fig. 1: The received signal at Receiver 1, where the length of the vector represents the received power of the carried symbol. Here the number of channel uses = is 2.

Next, we illustrate how to achieve this GDoF value via a ZF-SC receiver. To decode B 1,1 , we first zero force the strongest interference B 1,2 and then treat all the other interference as noise. The achievable GDoF value of data stream B 1,1 is

After recovering B 1,1 , we subtract it off from the received signal and then decode B 1,2 . Similarly, we first zero force the strongest interference B 3,1 (and its aligned counterpart B 2,1 ) and then treat the remaining interference B 2,2 as noise.

The achievable GDoF value of data stream

). The achievable GDoF value for User 1 is the sum of 3 1,1 and 3 1,2 , which equals (5). Also note that the achievable GDoF value does not depend on the decoding order, i.e., if we reverse the decoding order of B 1,1 and B 1,2 , we still achieve the same GDoF value for User 1. ⌅

IV. AN ANALYTICAL DECOMPOSITION APPROACH

In this section, for the TIM-TIN problem we present an analytical baseline approach, denoted by TIM-TIN decomposition. The basic idea is as follows. Any given network can be decomposed into a TIM component and a TIN component, each containing all the desired links and non-overlapping interfering links, such that in total, these two components cover all the interfering links. In other words, denote the sets of all interfering links in the original network, TIM component, and TIN component by I, I TIM , and I TIN , respectively. We have I TIM \I TIN = q and I TIM [I TIN = I. First, consider the TIM component only. Assume that all the links are equally strong. Applying the TIM solution yields an achievable GDoF tuple (3 1,TIM ,...,3 ,TIM ), which identifies the fraction of the signal space available to each user. Next, consider the TIN component only. Applying appropriate power control at each transmitter and treating interference as noise at each receiver, we obtain an achievable GDoF tuple (3 1,TIN ,...,3 ,TIN ), which identifies within the available signal space dimensions assigned to each user, the fraction of signal levels that are available to each of them. Finally, the product of the two above fractions, i.e., the GDoF tuple (3 1,TIN ⇥3 1,TIM ,...,3 ,TIN ⇥3 ,TIM ), is achievable, identifying the net fraction of signal dimensions available to each user by this decomposition approach. Note that the decomposition is quite flexible, i.e., any interfering link can be considered in either TIM or TIN component (but not both simultaneously). Therefore, for one interference channel, we have multiple possible decompositions. For this TIM-TIN decomposition approach, we have the following theorem. 6Theorem 1: For one specific TIM-TIN decomposition in a general -user interference channel, let D TIM be the achievable GDoF region of the TIM component via signal space approach (i.e., interference alignment and ZF), and D TIN be the achievable GDoF region of the TIN component via signal level approach (i.e., power control and TIN). Then, the following GDoF region is achievable in the original -user interference channel,

The whole achievable GDoF region based on the TIM-TIN decomposition approach is given by D TIM TIN = Convex Hull

⇣ -

TIM TIN

D⌘

, where TIM TIN denotes the set of all the possible TIM-TIN decompositions and the convex hull operation comes from time-sharing.

Proof : The key is to prove (6). In a specific TIM-TIN decomposition, for User :, denote the set of its interferers in the TIM component by I : . To achieve the GDoF tuple (3 1,TIM ⇥ 3 1,TIN ,...,3 ,TIM ⇥ 3 ,TIN ) in the original channel, the beamforming vectors of each user are the same as those yield the GDoF tuple d TIM in the TIM component, and the power allocation for (all the data streams of) each user follows from the solution that yields the GDoF tuple d TIN in the TIN component. Receiver : zero-forces the interference from the users in I : and treats the remaining interference as noise, which achieves the GDoF value 3 :,TIM ⇥ 3 :,TIN . ⌅ Example 2: Consider a 5-user interference channel within the QM-TIM(0,0.5) framework in Fig. 2(a). The network is decomposed into a TIN component and a TIM component as shown in Fig. 2(b) and Fig. 2(c), respectively. For the TIN component, which contains all the medium interfering links and satisfies the TIN-optimality condition of [9], according to Theorem 1 in [9] we obtain that its optimal symmetric GDoF value is 0.6. In the TIM component, which contains all the strong interfering links, the symmetric GDoF value is 0.5 [3]. Therefore, through this decomposition, in the original network the symmetric GDoF value 0.6 ⇥ 0.5 = 0.3 is achievable. The achievable scheme is given explicitly in Fig. 2(d). In this scheme, = = 2 and 1 8 = 1, 88 2{ 1,...,5}. More specifically, the achievable scheme uses a 2 dimensional space and 4 beamforming vectors, where any two of them are linearly independent and , 2 and , 5 are aligned along the same vector. The transmit power allocations are A 1 = 0, A 2 = 0.1, A 3 = 0.2, A 4 = 0.3 and A 5 = 0.4. It is easy to verify that every user achieves a GDoF value 0.3.

• ⌅ As mentioned before, within the multilevel TIM framework, in general the solution based on a combination of TIM and TIN (including the decomposition approach presented in this section) is not optimal from an information theoretic perspective. However, this robust decomposition approach works rather well when the quantized channel strength levels for cross links are concentrated around the bottom half of the signal levels, where it characterizes the symmetric GDoF value to a constant factor that is no larger than 2.

Theorem 2: For QM-TIM(C 1 ,C 2 ,...,C ; ) where C ;  0.5, the TIM-TIN decomposition approach characterizes the symmetric GDoF value 3 sym within a factor of 1 1 C ;  2. The proof of Theorem 2 is relegated to Appendix C.

Remark 1: The setting of QM-TIM(C 1 ,C 2 ,...,C ; ) where C ;  0.5 is justified by the conjecture that the optimal allocation of limited quantization bins for interfering links would be more concentrated near the noise floor. Intuitively, this is because the opportunities to communicate exist only where the desired signal significantly dominates noise/interference strengths, especially for settings with channel uncertainties where one might be forced to treat interference as noise. Although in general the optimal channel quantization is still an interesting open problem (which is beyond the scope of this paper), the above conjecture is partially settled for the 2-user Z interference channel in [33].

Finally, we show that TIM-TIN decomposition may achieve the optimal GDoF for certain network settings. Here we consider a class of multilevel neighboring interference channel, which is a generalization of the cellular blind interference alignment problem (or wireless index coding problem) in [19]. In order to limit the number of parameters while still covering broad classes of network setups, here we mainly study symmetric cases, i.e., where relative to its own position, each receiver has the same set of strong and medium interfering links. More specifically, consider the channel depicted in Fig. 3, which is a locally connected interference channel with an infinite number of users within the QM-TIM(0,0.5) framework. For each receiver :, there are 2(( + ")+1 transmitters connected to it with channel strength level no less than the effective noise floor. One of them is the desired Transmitter :. The 2( transmitters with indices {: (, ..., : 1} and {: + 1,...,: + (} are connected to Receiver : with strong interfering links, and the 2" transmitters with indices {: ( ", ..., : ( 1} and {: + ( + 1,...,: + ( + " } are connected to Receiver : with medium interfering links. For such networks, we have the following result. Theorem 3: For the above symmetric multilevel neighboring interference channel, the symmetric GDoF value is

which is achievable by TIM-TIN decomposition.

The proof details are provided in Appendix D. It is notable that for the symmetric neighboring interference channel, the signal space approach (with one-to-one alignments, see Appendix D) always achieves 1/(( + " + 1) GDoF. When ">( + 1, according to Theorem 3, the decomposition approach outperforms the pure signal space approach in terms of GDoF, and with " increasing the gap between these two strictly increases.

Remark 2: The result in Theorem 3 can be extended to some asymmetric cases directly. For instance, suppose that the number of strong interferers for each user : is still 2(, whose indices are still {: (, ..., : 1} and {: + 1,..,:+ (}. However, different users have different numbers of medium interferers. For User :, the indices of the medium interferers are {: ( " * : ,...,: ( 1} and {: + ( + 1,...,:+ ( + " ⇡ : }. If 8:, " * : >(and " ⇡ : >(, the symmetric GDoF value for such asymmetric multilevel neighboring interference channels remains as 1 2((+1) . The converse and achievability arguments both follow from the proof of Theorem 3.

V. A D ISTRIBUTED NUMERICAL APPROACH

The TIM-TIN decomposition approach is a centralized analytical method, which requires the coarse channel strength information of all links in the network together for joint signal vector space and signal power level allocation. In this section, we devise a distributed numerical algorithm to address the TIM-TIN problem, which only requires local measurements on the signal strengths at each user. The proposed algorithm is built upon a distributed power control algorithm based on the duality of TIN [34], whose key ingredient is restated below.

Lemma 3: (Lemma 1 in [34]) In a general -user interference channel, assume that a valid power allocation (A 1 ,...,A ), 7 A 8  0, 88 2[ ], achieves a GDoF tuple (3 1 ,...,3 ). In its reciprocal channel using the power allocation ( Ā1 ,...,Ā ), where

the achieved GDoF tuple ( 31 ,..., 3 ) dominates (3 1 ,...,3 ), i.e., 3:

The proposed TIM-TIN distributed numerical algorithm, called ZEST, is specified at the top of the right column in this page. 8 The convergence of the ZEST algorithm is given in Theorem 4.

Theorem 4: In the ZEST algorithm, ! 3 (<) ⌃ converges. The proof of Theorem 4 is presented in Appendix E, where we show that

Remarkably, the proof of Theorem 4 leads to the duality of the TIM-TIN problem naturally.

Theorem 5: (Duality of TIM-TIN) In the TIM-TIN problem, any -user interference channel and its reciprocal channel have the same achievable GDoF region.

Proof : Through (9), one can find that for any channel with arbitrary beamforming vectors and power allocations, in its reciprocal channel, we can always construct some beamforming vectors and their associated power allocations, such that the obtained GDoF tuple in the reciprocal channel dominates that achieved in the original channel. Since in the TIM-TIN problem, the achievable GDoF region for any interference channel must be upper-bounded, the original channel and its reciprocal channel have the same achievable GDoF region. ⌅

A. Numerical Validations

To further validate the GDoF performance of the proposed ZEST algorithm, we consider a random 5-user interference channel. We assume that the channel strength levels of all direct links are always equal to 1. Motivated by cellular networks where users suffer strong interference from neighboring cells, we assume that at Receiver 8, the interference from Transmitter 8 1 and 8+1 are strong interference, and the others are weak. 9 For the strong interference, we assume that their channel strength levels fall into a uniform distribution of [G, 1], and the channel strength levels of the weak interfering links fall into a uniform distribution of [0, 1 G], where G 0.5. Following [13], [17], [34], we keep the channel strength levels 7 In the TIN scheme, assume that the allocated power to User 8 2[ ] is % A 8 , A 8  0. From the GDoF perspective, we refer to the power exponent vector (A 1 ,...,A ) as the power allocation. 8 Note that in steps 3) and 5) of the ZEST algorithm, when the beam ; 2 [1 : ] of User : 2[ ] updates its power allocation following Lemma 3, it treats all the remaining received beams after ZF and SC (including the other desired beams of User :) as interference. Also note that since in steps 2) and 4) a successive cancellation is adopted in the lexicographic order, the beam ; of User : does not receive interference from beam s of User :, where B, ; 2[ 1 : ] and B<;. 9 Here we consider a cyclic setting, i.e., when 8 = 1, 8 1 = 5 and when 8 = 5, 8 + 1 = 1.

Algorithm 1 ZEST: ZEro-forcing with Successive cancellation and power control for TIM-TIN 1) Let < = 1. Set = and 1 : , and randomly choose unit-norm beamforming vectors ! v (<) :,; and power allocations ! A (<) :,; that satisfy the unit power constraint, :

2) In the original channel, update the receiving vectors ! u (<) :,; to the unit-norm ZF-SC receiving vectors that achieve the maximal GDoF value for each user (See Lemma 2. Without loss of generality, the cancellation is taken in the lexicographic order). Compute the achievable GDoF tuple ! d (<) and the achievable sum-GDoF value ! 3 (<) ⌃ . 3) Reverse the direction of the communication. Calculate the power allocation A (<) :,; for each data stream in the reciprocal channel following (8), and set the beamforming and receiving vectors v (<) :,; and u (<) :,; following v (<) :,; = ! u (<) :,; , u (<) :,; = ! v (<) :,; , 8: 2[ ], 8; 2[ 1 : ]. Compute the achievable GDoF tuple d (<) switch and the achievable sum-GDoF value 3 (<) ⌃,switch (using receivers with the reverse lexicographic cancellation order). 4) In the reciprocal channel, update the receiving vectors u (<) :,; to the unit-norm ZF-SC receiving vectors that achieve the maximal GDoF value for each user (Again, the cancellation is taken in the lexicographic order). Compute the achievable GDoF tuple d (<) and the achievable sum-GDoF value 3 (<) ⌃ . 5) Reverse the direction of the communication. Calculate the power allocation ! A (<+1) :,;

for each data stream in the original channel following (8), and set ! v (<+1) :,; = u (<) :,; , ! u (<+1) :,; = v (<) :,; , 8: 2[ ], 8; 2[ 1 : ]. Compute the achievable GDoF tuple ! d (<) switch and the achievable sum-GDoF value ! 3 (<) ⌃,switch (using receivers with the reverse lexicographic cancellation order). Then let < = < + 1. 6) Repeat steps 2) through 5) until the achievable sum GDoF value (i.e., ! 3 (<) ⌃ ) converges or < reaches a predefined threshold.

U 89 fixed and scale the parameter % in each random channel realization, and we always assume that every transmitter is subject to a unit peak power constraint and the noise variance at each receiver is normalized to one. Since all the direct channels are with channel strength level 1, % in fact denotes the SNR of the desired link for each user.

We compare the achievable sum-GDoF of the proposed ZEST algorithm, the well-known distributed interference alignment algorithm Max-SINR [35],foot_7 the state-of-the-art power control algorithm SAPC (i.e., SINR approximation power control) [36], TDMA (i.e., the orthogonal scheme with equal time sharing among all users) and the full power transmission (i.e., every user always utilizes full power to transmit its own signal). It is notable that Max-SINR and SAPC optimizes the signal space allocation and signal level allocation, respectively. Among all the schemes considered here, only ZEST jointly optimizes the signal space and signal level allocation for data transmission. For both ZEST and Max-SINR, we set the number of channel uses = as 2 and the number of scalar data streams for each user 3 : as 1, 8: 2{ 1,...,5}. We also note that for both ZEST and Max-SINR, different initializations may yield different sum-rates, particularly for ZEST in low and medium SNR regimes. 11 In our experiment, for both ZEST and Max-SINR, in each channel realization we start from multiple random initializations and pick the largest yielded sum-rate as the final solution. When the SNR value % is less than 30 dB, we set the number of random initializations as 30, and 10 otherwise. How to smartly choose the initialization of ZEST to improve sumrate in low and medium SNR regimes is an interesting open question.

In our experiments, we consider two specific G values, i.e., G = 0.5 and G = 0.75, where the latter models the settings with more diverse channel strengths between strong and weak interfering links. For the two different G values, the averaged sum-rate of all algorithms over 200 random channel realizations are given in Fig. 4(a) and 4(b), respectively. It can be seen that in both cases ZEST achieves the largest sum-GDoF value (i.e., the steepest slope in the high SNR regime) among all the schemes. More interestingly, ZEST outperforms SAPC, TDMA and the full power transmission almost over the entire SNR range. Compared with Max-SINR, ZEST is particularly favorable in the settings with more disparate interference strengths (e.g., when G = 0.75), and in both cases ZEST only suffers slight sum-rate degradation when the SNR value is relatively low.

Next, we consider the convergence of the ZEST algorithm. In general, the numerical results show that in all channel realizations and in all SNR regimes, ZEST exhibits a much faster convergence rate than Max-SINR and SAPC. In our experiment, a few iterations are usually sufficient for ZEST's convergence. A representative example is given in Fig. 5 when G = 0.5 and SNR = 30 dB. Note that as shown in Fig. 5, the convergence of Max-SINR is not always monotone, which has been reported in [37] as well.

While our numerical experiments are modest in scale and scope, they are indicative of the following strengths of ZEST: 1) with proper initialization and choice of parameters (e.g., the numbers of channel uses and data streams), ZEST appears capable of achieving superior GDoF performance compared with the conventional schemes which only optimize the allocation of signal vector space or signal power levels individually, 11 We point out that the convergence of Max-SINR is still open. In our experiment, we note that for Max-SINR, with a sufficient number of iterations, different initializations usually converge to the same sum-rate. In practice, when the number of iterations is limited, different initializations may lead to different final solutions though. In [37] a convergent Max-SINR algorithm is developed, which in fact jointly optimizes the signal vector space and signal power level allocations. However, the proposed algorithm in [37] is based on the duality of SINR in multiuser MIMO networks under an artificial sum power constraint. While in ZEST, the convergence is guaranteed under the practical individual user power constraint. But due to the non-convexity of the problem, the convergent point depends on the initialization. For SAPC, following [36] we always set the initial power of each user as its maximal transmit power. especially for the cases where the interference strengths are disparate; 2) ZEST exhibits a fast convergence rate. More elaborate numerical experiments that study the performance of ZEST at a larger scale remain an interesting topic for future work. Advances in the ability to efficiently find good initialization points for ZEST in large networks are likely to be particularly impactful. Ongoing efforts along these lines, that compare and contrast MaxSINR, and TIMTIN, and combine them with autoencoders based on deep learning principles are notable in this regard [38]. Evidently, this research avenue remains an active area with much potential for progress.

VI. CONCLUSION

In this paper, we formulate a joint signal vector space and signal power level allocation problem (i.e., the TIM-TIN problem) under the assumption that only a coarse knowledge of channel strengths and no knowledge of channel phases is available to the transmitters. A decomposition of the problem into TIN and TIM components is proposed as a baseline. A distributed numerical algorithm called ZEST is developed as well. The convergence of the ZEST algorithm leads to the duality of the TIM-TIN problem. The joint TIM-TIN approach is promising as a building block for existing and future wireless networks, due to its robustness to channel uncertainty at the transmitters, implementation simplicity (e.g., no need to decode any interference, and being implemented in a distributed fashion) and its potential for superior performance. However, this line of research is still in its early stages. It is hoped that this work could inspire more future research in this area. Future directions include, e.g., translating theoretical insights obtained in this work into the design of practical largescale wireless networks, such as device-to-device networks and heterogeneous cellular networks.

APPENDIX A PROOF OF LEMMA 1

Let G 8 ⇠C N ( 0,% ^8 ) be independent Gaussian variables. Denote by z an = ⇥ 1 zero mean unit variance circularly symmetric Gaussian vector. When <>W , denote the

= log

where ( 12) is due to the facts that v ⇧ 0 ( 9) , 8 9 2[ < W] is a linear combination of the vectors in V ⇧ = {v ⇧(1) , v ⇧(2) ,...,v ⇧(W) }, and the term Õ < W 9=1 v ⇧ 0 ( 9) G ⇧ 0 ( 9) becomes insignificant when % approaches infinity. More specifically, as % !1 , for the term v 8 (G 8 + G 9 + ... + G : ) (8<9<. . .<:), only the symbol G 8 with the dominant power exponent ^8 matters, implying that for the vector v 8 we can ignore all the other independent symbols with equal or smaller power exponents in the limit of % !1 . The following is essentially the same as the proof of Lemma 1 in [39]. Define

] with size = ⇥ W, and the diagonal matrix P ⇧ , diag[% ^⇧(1) % ^⇧ (2) ... % ^⇧(W) ] with size W ⇥ W.W e have

= log

APPENDIX B PROOF OF LEMMA 2 Recall that in Section III, from vectors V = {v 1 ,...,v < } and their associated power exponents R = {^1,...,^<}, we obtain W  = linearly independent beamforming vectors V ⇧ = {v ⇧(1) , v ⇧(2) ,...,v ⇧(W) } and their associated power exponents P ⇧ = {^⇧ (1) ,^⇧ (2) ,...,^⇧ (W) }. Define these operations as N E and N ^, respectively, i.e., N E (V, R) = V ⇧ and N ^(V, R) = P ⇧ . Denote by ^⌃,N ^(V, R) the sum of all entries in N ^(V, R).

To prove lemma 2, without loss of generality, we only need to consider User 1 and assume that the successive cancellation is taken in the lexicographic order. According to the chain rule, we have

Let

We have

For Receiver 1, denote the sets of the beamforming vectors and associated power exponents for all the received data streams as V 1 and R 1 , respectively. Consider each term in the right hand side of (19). Start with 3 1,1 . We have the following two cases.

. From Lemma 1, we have

Therefore, in the GDoF sense, we have

, which is achievable by zero-forcing all the data streams falling into span(N E (V 1 , R 1 )\v 1,1 ) and treating the remaining interference as noise.

We have ' 1,1 = >(log(%)) and 3 1,1 = 0, which is trivially achievable (by ZF and TIN). After decoding B 1,1 , we subtract it out from the received signal and then consider the second term in the right hand side of (19), i.e., 3 1,2 . Similarly, we can argue that by zero-forcing certain interfering data streams for B 1,2 and treating others as noise, 3 1,2 is achievable. Repeating this subtract-and-decode argument until all the desired data streams for User 1 are decoded, we establish that 3 1 is achievable via the ZF-SC receiver and complete the proof.

APPENDIX C PROOF OF THEOREM 2

In the the original network is decomposed into a TIN component containing all the interfering links with channel strength levels no stronger than C ; and a TIM component containing all the other interfering links. First, consider the TIN component. When C ;  0.5, the TIN component satisfies the TIN-optimality condition identified in [9] (recall that the channel strength level of the direct link is normalized to 1). Following Theorem 1 in [9], its symmetric GDoF value 3 TIN sym 1 C ; . Next, for the TIM component, assume that given the optimal signal space solution, the optimal symmetric GDoF value is denoted by 3 TIM sym . Finally, according to Theorem 1 in this paper, the symmetric GDoF value 3 TIM sym ⇥ 3 TIN sym is achievable. For the converse, 3 TIM sym and 3 TIN sym are both outer bounds for the original network, since removing interfering links from the channel does not decrease GDoF. Therefore, min{3 TIM sym ,3 TIN sym } can serve as an outer bound for the symmetric GDoF value of the original network. We have 3 TIN sym ⇥ 3 TIM sym  3 sym  min{3 TIN sym ,3 TIM sym }, and the symmetric GDoF value 3 sym can be characterized to a factor

which is no larger than 2.

APPENDIX D PROOF OF THEOREM 3

First, consider the achievability. When " is no larger than (, the achievable scheme is to treat all the medium interfering links as strong interfering links and apply the one-to-one alignment (see Theorem 6 of [19]). Note that this scheme falls into the category of TIM-TIN decomposition, where the TIN component contains no interfering links and the TIM component contains all the medium and strong interfering links. Otherwise, when " is larger than (, we use the following decomposition to achieve the optimal symmetric GDoF value: let the TIN and TIM component contain all the medium interfering links and all the strong interfering links, respectively. For the TIN component, the achievable symmetric GDoF value is 1 2 , and for the TIM component, the achievable symmetric GDoF value is 1 (+1 [19]. Therefore, in the original network, the symmetric GDoF value 1 2((+1) is achievable.

Next, consider the converse. We start with a useful lemma. Lemma 4: Consider a 3-user interference channel within the QM-TIM(0,0.5) framework, where 8, 9, : 2{ 1, 2, 3}, 8 < 9, 9 < :, and 8 < :. Denote by ; 89 the link between Transmitter 9 and Receiver 8, M the set of all medium interfering links, and S the set of all strong interfering links. If ; 89 2S , and ; :8 ,; 8: ,; :9 ,; 9: 2{ S[M} , then the sum GDoF value of this channel is 1. Proof: The achievability is straightforward. In the following we only consider the converse. Without loss of generality, we assume 8 = 1, 9 = 2, and : = 3. To obtain the desired outer bound, we first set U 21 = 0. This does not hurt the sum capacity because regardless of the channel strength level of the cross link ; 21 , we can always provide the message , 1 to Receiver 2 through a genie and remove this interfering link.

Without perfect channel knowledge at transmitters, the channel can be regarded as a compound channel (with an infinite number of channel states), and its capacity is upper bounded by the capacity of any possible channel state [13]. By definition, in QM-TIM(0,0.5) for both strong and medium interfering links, their channel strength levels can be set as the threshold value 0.5. Consider a specific channel realization where U 11 = U 22 = U 33 = U 12 = 1, U 13 = U 31 = U 23 = U 32 = 0.5, and all the links have the same channel phase. The capacity of the original channel is upper bounded by this case.

For any reliable decoding scheme, Receiver 1 can always decode its own message , 1 . After decoding , 1 , Receiver 1 can subtract it from its received signal and has the same signal as Receiver 2. So Receiver 1 can also decode , 2 . Now consider Transmitters 1 and 2. We find that they have the same channel vectors to Receiver 1 and 3. It implies that the sum capacity of the original channel is upper bounded by that of a 2-user interference channel with transmitters {) 1,2 ,) 3 } and receivers {' 1 ,' 3 }, where ) 1,2 is a combination of Transmitter 1 and 2. The sum-GDoF value of this 2-user interference channel (where both desired links have channel strength level 1 and both cross links have channel strength level 0.5) is known to be 1 [30]. Therefore, we establish the desired outer bound.

⌅

As mentioned before, for the compound channel setting, the capacity of any possible channel state serves as a capacity upper bound. To complete the converse proof, the main task is to identify the channel state providing the tightest upper bound. For both cases discussed below, the proof follows three steps: (1) picking up the target subnetwork with a certain number of users, (2) identifying the specific channel realizations which provide the desired outer bound, and (3) completing the proof by reducing the obtained channel to a relatively simple equivalent channel with known sum-GDoF result. Case I ("  (): Consider any consecutive ( + " + 1 users. Without loss of generality, assume that the user indices range from 1 to ( + " + 1. For these users, we intend to prove the outer bound 3 1 + 3 2 + ... + 3 (+" +1  1.

Towards this end, first remove all the users other than the considered ( + " + 1 users, which does not hurt the sum capacity of users 1 to (+" +1. Next, in the remaining network, divide the ( + " + 1 users into three subgroups as shown in Fig. 6(a): • G 1 : this subgroup includes users 1 to "; • G 2 : this subgroup includes users " + 1 to ( + 1; • G 3 : this subgroup includes users ( + 2 to ( + " + 1.

To derive the desired outer bound, consider the channel realization below. Assume that all the links have the same channel phase. For the direct links, recall that their channel strength levels are all equal to 1. For the medium interfering links, we set their channel strength levels to be exactly 0.5. For the strong interfering links, we set their channel strength levels to be either 1 or 0.5 as follows. For all the transmitters in G 1 , we assume that the cross links between them and the receivers in G 1 and G 2 are all with channel strength level 1, while the cross links between them and the receivers in G 3 are all with channel strength level 0.5. Next, for the transmitters in G 2 , the cross links between them and all the receivers are with channel strength level 1. Finally, for the transmitters in G 3 , the cross links between them and the receivers in G 2 and G 3 are all with channel strength level 1, while the cross links between them and the receivers in G 1 are all with channel strength level 0.5. Now, note that in this network, all the receivers in the same subgroup G 8 8 2{1, 2, 3}, are equipped with the same received signal. Thus removing all of them but one cannot hurt the sum capacity. Also note that for all the transmitters in the same subgroup G 8 , 8 2{1, 2, 3}, they have the same channel vectors to all the remaining three receivers. Thus combining all the transmitters in each subgroup into one transmitter does not hurt the sum capacity either. Therefore, the network is reduced to a 3-user interference channel where U 13 = U 31 = 0.5 and all the other links are with channel strength level value 1. According to Lemma 4, the sum-GDoF value of this network is 1, which establishes the desired outer bound.

Case II (">( ): Consider any consecutive 2(( + 1) users. Without loss of generality, assume the user indices range from 1 to 2(( + 1). For these users, we intend to show 3 1 + 3 2 + ... + 3 2((+1)  1. Similar to the previous case, we first remove all the other users. In the remaining network, divide the 2(( + 1) users into two subgroups as shown in Fig. 6(b): • G 1 : this subgroup includes users 1 to ( + 1;

• G 2 : this subgroup includes users ( + 2 to 2(( + 1). Again, assume that all the links have the same channel phase. For the direct links, their channel strength levels are all 1. For the medium interfering links, we set their channel strength levels to be exactly 0.5. Next, we set the channel strength levels of the strong interfering links to be either 1 or 0.5 as follows. For transmitters in each subgroup G 8 , the cross links between them and the receivers in the same subgroup G 8 are all with channel strength level 1, and the cross links between them and all the receivers in the other subgroup G 9 are with channel strength level 0.5, where 8, 9 2{ 1, 2} and 8 < 9. Removing all the receivers but one in each subgroup G 8 , 8 2{ 1, 2}, cannot hurt the sum capacity. Combining all the transmitters in each subgroup G 8 , 8 2{ 1, 2}, into one transmitter cannot hurt the sum capacity either. Finally, we end up with a 2-user interference channel with U 11 = U 22 = 1, U 12 = U 21 = 0.5 and sum-GDoF value 1 [30], which leads to the desired outer bound.

APPENDIX E PROOF OF THEOREM 4

As the sum-GDoF of an interference channel must be upper bounded by a finite value, to prove this theorem, we only need to show that the achievable sum-GDoF via the ZEST algorithm monotonically increases after each update, i.e., Recall that a successive cancellation procedure is adopted at each receiver. According to the ZEST algorithm given in Section V, without loss of generality, we have assumed that the cancellation is taken in the lexicographic order. Therefore, for Receiver : 2[ ], the effective channel strength level from data stream ? of User : to data stream @ of User : is 0, for ?, @ 2[ 1 : ] and ?<@ . Set the corresponding entries of G as 0, i.e., is the 9-th entry of ! d (<) .

Similarly, for the reciprocal channel in the <-th iteration with beamforming vectors v (<) 9,B = ! u (<) 9,B and receiving vectors u (<) :,; = ! v (<) :,; , we construct a counterpart ⌫-user interference channel with the channel strength level matrix G = ! G ) , which is the reciprocal channel of IC > and denoted by IC A . 12Assume that in IC A , the allocated power to Transmitter 8 is  3 (<) 9,switch , 8 9 2[ ], and hence prove (a). The proof of (c) follows similarly. Therefore, we establish (21) and complete the proof.