Source-linked AI summary
The Approximate Capacity of the Many-to-One and One-to-Many Gaussian Interference Channels
Guy Bresler, Abhay Parekh, David Tse
TL;DR
The paper asks whether approximate-capacity methods for the two-user Gaussian interference channel extend to many users. It uses a deterministic model to guide capacity analysis and lattice codes to align interference, obtaining constant-gap characterizations for many-to-one and one-to-many channels. The deterministic view also reveals reciprocity between these channel types, while the many-to-one Gaussian gap remains somewhat loose.
Problem
The paper addresses how to characterize Gaussian interference channels with more than two users, extending a one-bit approximate-capacity result to structured many-user cases.
Method
The paper uses a deterministic signal-scale model to guide the Gaussian analysis, with lattice codes for many-to-one interference alignment and Gaussian random codebooks for one-to-many channels.
Results
The many-to-one and one-to-many Gaussian capacity regions are determined within constant gaps, and the deterministic channels exhibit exact reciprocity corresponding to approximate Gaussian reciprocity.
Takeaways & Limitations
Signal-scale alignment is central for translating the deterministic many-to-one strategy to Gaussian channels, while one-to-many channels admit a simpler Gaussian-codebook approach.
Takeaways & Limitations
The many-to-one Gaussian achievable-to-outer-bound gap, (2K + 5) log K bits per user, is somewhat loose and may be improved by exploiting interference-pattern structure.
Abstract
from arXiv · showhide
Recently, Etkin, Tse, and Wang found the capacity region of the two-user Gaussian interference channel to within one bit/s/Hz. A natural goal is to apply this approach to the Gaussian interference channel with an arbitrary number of users. We make progress towards this goal by finding the capacity region of the many-to-one and one-to-many Gaussian interference channels to within a constant number of bits. The result makes use of a deterministic model to provide insight into the Gaussian channel. The deterministic model makes explicit the dimension of signal scale. A central theme emerges: the use of lattice codes for alignment of interfering signals on the signal scale.
1 Introduction
The paper extends approximate-capacity analysis to many-to-one and one-to-many Gaussian interference channels using a deterministic model and lattice-based interference alignment. It establishes constant-gap capacity characterizations and exposes reciprocity between the two channel types.
- The paper studies many-to-one and one-to-many Gaussian interference channels, where interference is experienced or caused by only one user.
- The capacity regions are characterized within constant gaps independent of the channel gains.For many-to-one channels, the gap is less than (2K + 5) log K bits per user; for one-to-many channels, it is 2K + 1 bits for user 0 and 1 bit for each other user.
- The deterministic model retains essential Gaussian-channel features while making signal-scale dimensions explicit and simplifying the capacity analysis.The generalized degrees-of-freedom region of the Gaussian channel equals the capacity region of an appropriate deterministic channel.
- Lattice codes align multiple interfering signals on the signal scale, enabling the Gaussian many-to-one achievable scheme.The alignment localizes the aggregate interference so its impact is practically as though it came from one user.
- The one-to-many channel is essentially achievable with Gaussian random codebooks through a generalized Han-Kobayashi scheme.In the deterministic model, reversing transmitters and receivers makes the many-to-one and one-to-many capacity regions identical; in Gaussian channels, this reciprocity holds approximately.
- The deterministic model reveals reciprocity between the two channel types and guides both their capacity approximations.
2 Gaussian Interference Channel and Motivating Example
The section introduces the multi-user Gaussian interference channel and uses a three-user many-to-one example to show why Gaussian-codebook strategies can fail, while lattice-based alignment can achieve a much higher sum-rate.
- Channel model: The channel has K + 1 users, with each receiver decoding its corresponding message under power, noise, and gain-based SNR/INR definitions.The motivating special cases are the many-to-one channel, where users 1 through K interfere at receiver 0, and the reciprocal one-to-many channel.
- Motivating example: For the three-user example, Gaussian Han-Kobayashi codebooks attain a sum-rate of at most log(1 + 3β2) ≈ 2 log β.Users 1 and 2 split their signals into private and common parts, with private signals treated as noise and common signals decoded at receiver 0.
- Motivating example: A discrete-codebook strategy achieves a rate within a constant of the approximately 3 log β optimal sum-rate for β = 22n.The even-power restriction simplifies analysis, while the scheme itself extends to arbitrary real-valued channel gains.
- Motivating example: Lattice-subset codebooks align users 1 and 2's interference so their aggregate effect is essentially the same as that of a single interferer.In the example, user 0 can decode its fine signal despite the combined interference.
- Motivating example: The Gaussian-codebook limitation arises because the sumset of random interferer codebooks can fill the signal space, leaving no room for user 0 to communicate.With m points in each codebook, the sumset can have up to m2 points.
- Motivating example: The deterministic channel model is introduced to expose signal-scale structure and provide a framework for approximating the many-to-one channel capacity within a constant gap.The model is used because it retains essential Gaussian-channel features while being significantly simpler.
3 Deterministic channel model
The deterministic model abstracts Gaussian channels into signal levels, preserving noise-induced information loss and signal superposition while simplifying analysis. Applied to interference channels, it provides insight especially in the high-SNR regime and supports analysis of many-to-one and one-to-many structures.
- Point-to-point channel: Each input bit occupies a signal level, with lower-significance bits lost when they fall below the noise level.The model uses n = ⌊log SNR⌋ levels for a point-to-point channel.
- Multiple-access channel: In the deterministic multiple-access channel, incoming bits on the same level are added modulo two, so levels remain separate.Modulo-two addition makes the model tractable while representing signal superposition.
- Interference channel: The deterministic interference channel shifts each transmitter’s signal according to an integer gain and adds signals level by level modulo two.The model is constructed from the deterministic multiple-access channel and retains noise loss and signal superposition.
- Interference channel: The model is most relevant at high SNR, where communication is interference-limited, but also provides insight into finite-SNR Gaussian channels.Many-to-one interference occurs only at receiver 0, whereas one-to-many interference is caused by only one user.
4 Deterministic Many-to-One Interference Channel
The deterministic many-to-one interference channel decomposes into parallel level-specific sub-channels. Its capacity region equals the sum of those sub-channel capacities, with level allocation and combinatorial outer-bound arguments establishing achievability.
- Channel decomposition: The many-to-one channel is a parallel channel with one sub-channel for each level at receiver 0.Theorem 3 establishes that the total capacity equals the sum of the capacities of these sub-channels.
- Achievable region: The achievable strategy assigns each level either to user 0 or to all users interfering with user 0 on that level.Interfering users align on a level, making their aggregate cost to user 0 equivalent to that of one user.
- Achievable region: Users can transmit without interfering with user 0 on levels above user 0’s signal or below the noise level at receiver 0.These interference-free rates are characterized by ffree(i) = (n0i − nii)+ + (n0i − n00)+.
- Achievable region: Each single-level capacity region is achieved by time-sharing between transmission by user 0 and simultaneous transmission by all interfering users.The two operating points use uniformly random bits on the selected level.
- Outer bound: The outer bound uses individual and sum-rate constraints proved with genie-aided side information informed by the deterministic interference structure.At each level, receiver 0 is given all but one interfering signal from a selected user set, together with additional signal components.
- Capacity characterization: All corner points of the outer-bound polyhedron are achievable, so convexity makes the polyhedron the capacity region.The construction also achieves every corner point with zero probability of error using a fixed codebook with inputs i.i.d. over time.
5 Approximate Capacity Region of the Gaussian Many-to-One Interference Channel
The Gaussian many-to-one channel is characterized through inner and outer bounds guided by a deterministic model. Lattice-based signaling emulates deterministic level allocation, yielding a capacity approximation with a gap scaling as (2K + 5) log K bits per user.
- Capacity approximation: Approximately 5K log K bits per user separate the Gaussian many-to-one inner and outer bounds.The achievable region and outer bound lie within 3K log K and 2K log K bits per user, respectively, of an appropriate deterministic channel.
- Achievable strategy: Each level uses an independent lattice code with common code structure across transmitting users, and either user 0 or all interfering users transmit on that level.Independent dithers are used, while power constraints determine which levels each user can access.
- Level construction: The signal power-to-noise range is partitioned into intervals that serve as Gaussian analogues of deterministic channel levels.Endpoints are formed from SNR and INR values, with intervals [q_k−1, q_k] defining the levels.
- Achievable strategy: Lattice codes align multiple interferers so their aggregate effect can be decoded as a single interfering signal at receiver 0.Decoding proceeds from the highest level downward, treating lower-level signals as Gaussian noise and subtracting decoded signals.
- Capacity approximation: The achievable Gaussian region lies within (2K + 1) log K bits per user of the corresponding deterministic capacity region and within (2K + 5) log K bits per user of the stated outer-bound region.The deterministic comparison uses at most (M + 1) log K bits per user, with M ≤ 2K + 1.
- Degrees of freedom: The generalized degrees-of-freedom region is described by the outer-bound constraints and equals the scaled capacity region of an appropriate deterministic channel for rational parameters.The constraint terms account for below-noise signal portions, levels with multiple interferers, and levels used once.
6 Deterministic One-to-Many Interference Channel
The deterministic one-to-many channel is obtained by reversing transmitter and receiver roles in the many-to-one channel, yielding identical capacity regions. Its achievable scheme assigns each signal level to user 0 or to all users experiencing interference, and a generalized Han-Kobayashi scheme achieves the same region.
- Achievable scheme: Each signal level is allocated either to user 0 or to all users experiencing interference from that level.This allocation is the one-to-many counterpart of the many-to-one capacity-achieving scheme.
- Reciprocity: Reversing transmitter and receiver roles maps the deterministic many-to-one channel to a one-to-many channel with the same capacity region.Theorem 18 states this reciprocity using gains ˜n_ii = n_ii and ˜n_0i = n_i0.
- Capacity region: The resulting achievable region is exactly the deterministic many-to-one region, and its outer bound matches it.The proof concludes by identifying identical achievable and outer regions.
- Han-Kobayashi scheme: A generalized Han-Kobayashi scheme achieves the deterministic one-to-many capacity region using constraints (37), (38), (39), and (40).Its constraints contain the level-by-level achievable region because they are looser than the corresponding individual and pairwise constraints.
7 Approximate Capacity Region of the One-to-Many Gaussian Interference Channel
The one-to-many Gaussian channel has one interfering transmitter and K affected users. Its capacity region is approximated by Gaussian-codebook and generalized Han-Kobayashi strategies, with a gap of (2K + 1, 1, . . . , 1) bits.
- Channel model: The one-to-many Gaussian channel has one user causing interference to K other users, ordered by increasing INR.Users with INR_i ≤ 1 may treat interference as noise while losing at most 1 bit relative to point-to-point capacity.
- Outer bound: Theorem 20 places the capacity region within (2K + 1, 1, . . . , 1) bits of the stated individual and subset sum-rate constraints.The constraints are parameterized by SNR_i and INR_i under the ordering and INR_1 > 1 assumptions.
- Achievable scheme: The Gaussian achievable scheme uses a superposition of random Gaussian codebooks, with receiver i jointly decoding its signal and selected codebooks from user 0.This rate-splitting construction is analogous to the deterministic Han-Kobayashi scheme.
- Power-level construction: The signal of user 0 is divided into power intervals according to the interference levels observed by the K receivers.Each receiver decodes codebooks arriving above its intended signal while treating the remaining signals as noise.
- Gap analysis: The achievable region loses at most K bits at user 0 relative to the deterministic region, while the outer-bound comparison contributes K + 1 additional bits.Together these losses yield the theorem’s gap.
- Scheme comparison: Using an independent-level achievable scheme instead of the Han-Kobayashi scheme would produce a larger inner–outer bound gap.The paper therefore uses the generalized Han-Kobayashi construction for the Gaussian one-to-many channel.
8 Conclusion
The deterministic model exposes the structure of the many-to-one and one-to-many channels and closely guides their Gaussian analyses. Lattice codes are needed to transfer interference alignment to the Gaussian many-to-one channel, while deterministic reciprocity clarifies the relationship between the two channel types.
- Deterministic model: The deterministic model makes subset sum-rate constraints and the channels’ structural relationships easier to observe.Gaussian outer-bound proofs closely follow the deterministic proofs, including translated side information.
- Interference alignment: Lattice codes are necessary to align interfering signals on the signal scale when translating the deterministic many-to-one strategy to the Gaussian channel.The deterministic model itself exhibits the alignment phenomenon with simpler capacity-achieving schemes.
- Reciprocity: Reciprocity between the many-to-one and one-to-many channels is evident in the deterministic setting but veiled in the Gaussian setting.The deterministic model therefore provides a clear representation of this basic relationship.
- Open limitation: The many-to-one Gaussian gap of (2K + 5) log K bits per user is described as somewhat loose.The paper suggests accounting more carefully for the combinatorial interference pattern and tightening the outer-bound estimate.
Appendix I Gaussian Han and Kobayashi achieves sum-rate of at most log(1 + 3β2).
The appendix shows that, in the specified two-user setting, a Gaussian Han-Kobayashi scheme’s decodability constraints at receiver 0 impose an upper bound on its achievable sum-rate.
- Claim: The appendix proves that a Gaussian Han-Kobayashi scheme cannot achieve a sum-rate greater than log(1 + 3β^2).The proof analyzes the four private and common messages decoded through receiver 0’s MAC constraints.
- Decoding structure: Receiver 0 must decode message 0 and then the private and common messages from users 1 and 2.The resulting tuple lies within a four-user MAC region evaluated with Gaussian inputs.
- MAC constraints: The proof checks individual, pairwise, and higher-order MAC constraints using the receivers’ assumed decodability conditions.The argument uses β ≥ 2 and inequalities involving S_1 and S_2 to establish the remaining constraints.
- Conclusion: Because receiver 0 can decode all three messages, the MAC constraints upper-bound the sum-rate achieved by the Gaussian scheme.This establishes the stated appendix claim.
Appendix II Proof of Lemma 6
The appendix proves Lemma 6 by showing that incompatible tight constraints force a violation of another constraint. The proof uses a bipartite-graph characterization of interference levels and carefully partitions users around a separating level.
- Incompatible constraints on two user sets imply that another constraint from Theorem 3 is violated.
- An occluded user can be removed while preserving equality of the corresponding sum-rate constraint.Occlusion means every level where the user interferes is occupied by another user in the occluding set.
- The proof partitions S at level k∗ into Sa and Sb, whose interference occupies disjoint level sets.The analogous partition is made for S′ around user a.
- The resulting algebraic expressions are compared with equation (65), producing a contradiction.
Appendix III Proof of the Sum-Rate Constraint for the Many-to-One Gaussian Channel
The appendix derives a Gaussian many-to-one sum-rate outer bound using genie-provided side information motivated by the deterministic channel. Entropy bounds and simplifications then yield a cruder bound with a deterministic-like form.
- The genie gives receiver 0 the portion of each interfering signal overlapping with the next signal, following the deterministic model.This side-information choice is the central insight behind the sum-rate proof.
- Fano’s inequality and data processing convert the genie-aided channel into an entropy-based sum-rate bound.
- Gaussian entropy maximization, Jensen’s inequality, and the power constraint bound the conditional-entropy terms.
- The resulting bound contains the total rate r0 + r1 + · · · + rm and terms involving INRm and SNR0.
- The outer bound is loosened through cases based on INRk and SNRk to obtain a simpler deterministic-like expression.
- The simplified bound includes max(log(INRm), log(SNR0)) and an additive penalty of (m + 2) log(m + 1) + 1.