Source-linked AI summary
Interference Alignment with Asymmetric Complex Signaling - Settling the Host-Madsen-Nosratinia Conjecture
Viveck R. Cadambe, Syed A. Jafar, Chenwei Wang
TL;DR
The paper addresses whether constant complex Gaussian interference channels can exceed the conjectured one degree of freedom for almost all channel coefficients. It introduces asymmetric complex signaling and establishes 1.2 degrees of freedom generally, with corresponding limits for three-user linear alignment.
Problem
The Host-Madsen-Nosratinia conjecture concerns whether constant complex Gaussian interference channels can achieve more than one degree of freedom, a question that must be resolved in the complex setting.
Method
The paper uses interference alignment with asymmetric complex signaling over supersymbols of five complex channel symbols and analyzes phase-alignment conditions.
Results
1.2 degrees of freedom are achievable for almost all constant complex channel coefficients, while three-user linear alignment cannot exceed 1.2 except on a measure-zero subset.
Takeaways & Limitations
Asymmetric complex signaling is identified as an essential component of interference-network capacity analysis and also supports the paper's broader capacity perspective.
Takeaways & Limitations
The analyzed three-user linear alignment scheme constrains the coefficient vectors in conditions (71) and (72) to all-zero tuples.
Abstract
from arXiv · showhide
It has been conjectured by Host-Madsen and Nosratinia that complex Gaussian interference channels with constant channel coefficients have only one degree-of-freedom regardless of the number of users. While several examples are known of constant channels that achieve more than 1 degree of freedom, these special cases only span a subset of measure zero. In other words, for almost all channel coefficient values, it is not known if more than 1 degree-of-freedom is achievable. In this paper, we settle the Host-Madsen-Nosratinia conjecture in the negative. We show that at least 1.2 degrees-of-freedom are achievable for all values of complex channel coefficients except for a subset of measure zero. For the class of linear beamforming and interference alignment schemes considered in this paper, it is also shown that 1.2 is the maximum number of degrees of freedom achievable on the complex Gaussian 3 user interference channel with constant channel coefficients, for almost all values of channel coefficients. To establish the achievability of 1.2 degrees of freedom we introduce the novel idea of asymmetric complex signaling - i.e., the inputs are chosen to be complex but not circularly symmetric. It is shown that unlike Gaussian point-to-point, multiple-access and broadcast channels where circularly symmetric complex Gaussian inputs are optimal, for interference channels optimal inputs are in general asymmetric. With asymmetric complex signaling, we also show that the 2 user complex Gaussian X channel with constant channel coefficients achieves the outer bound of 4/3 degrees-of-freedom, i.e., the assumption of time-variations/frequency-selectivity used in prior work to establish the same result, is not needed.
1 Introduction
The introduction frames degrees of freedom as a high-SNR measure of accessible signaling dimensions and reviews why constant interference channels remained unresolved. It motivates asymmetric complex signaling as a new direction for addressing this gap.
- Motivation: Degrees of freedom measure the number of independent signaling dimensions accessible in a communication network.They also provide a first-order capacity approximation whose accuracy approaches 100% as SNR grows.
- Motivation: The Høst-Madsen-Nosratinia conjecture proposed that constant-coefficient K-user interference channels generally have only 1 degree of freedom, despite an outer bound of K/2.Prior results left the conjecture unresolved for almost all channel coefficient values.
- Prior interference alignment: Time-varying or frequency-selective channels achieve K/2 degrees of freedom almost surely through interference alignment, but constant channels lack the distinct rotations needed by standard vector-space schemes.With constant channels, multiple channel uses produce a scaled identity matrix, so signal vectors align identically at every receiver.
- Prior interference alignment: Signal-level alignment can exceed 1 degree of freedom for specially structured constant coefficients, but those coefficient conditions occupy measure-zero subsets.Examples include multilevel and lattice schemes using particular rational, algebraic, or parity-based coefficient structures.
- Introduction: The phase-alignment example demonstrates that a complex constant interference channel can achieve K/2 degrees of freedom for a special choice of channel phases.Its exact sum-capacity is K/2 log(1 + 2SNR) bits/channel-use, but the example does not establish performance for arbitrary coefficients.
- A New Idea - Asymmetric Complex Signaling: The paper investigates asymmetric complex signaling, which optimizes a complex system over its underlying real dimensions instead of restricting inputs to circularly symmetric complex Gaussians.The introduction contrasts this approach with the established optimality of circularly symmetric inputs in point-to-point, multiple-access, and broadcast channels.
2 Phase Alignment
The section examines whether phase-based beamforming can achieve 3/2 degrees of freedom in the 3-user constant complex interference channel. The construction requires aligned interference and channel-phase conditions, but its exact 3/2 solution applies only to a measure-zero subset.
- Signal-space design: 3/2 degrees of freedom requires one degree of freedom per user over the channel’s two-dimensional real signal space.The design therefore selects three real two-dimensional precoding vectors, one for each user.
- Signal-space design: The precoding vectors are optimized for channel coefficients but remain independent of the transmitted messages.The scalar real codewords carry the messages along these channel-dependent vectors.
- Signal-space design: At receiver 1, the two interfering signals must span one dimension so that one interference-free dimension remains for the desired signal.The same interference-alignment requirement is imposed symmetrically at receivers 2 and 3.
- Phase conditions: The phase-alignment solution is restricted to a measure-zero subset of channel coefficients, so it does not determine the conjecture’s validity.The proof links the restriction to the requirement that a real vector be an eigenvector of a rotation matrix.
3 Achievability of 1.2 Degrees of Freedom
The paper uses a five-symbol extension and asymmetric real signaling to align interference within a ten-dimensional real space. Four streams per transmitter yield 1.2 degrees of freedom for almost all constant channel coefficients, settling the conjecture negatively.
- 3 Achievability of 1.2 Degrees of Freedom: A five-symbol extension creates a 10-dimensional real signal space in which interference is constrained to at most 6 dimensions at each receiver.Four desired dimensions and no more than six interference dimensions fill the available real space.
- 3 Achievability of 1.2 Degrees of Freedom: 1.2 degrees of freedom results from sending 12 real streams over 10 real dimensions, equivalently 6 complex streams over 5 complex symbols.Each transmitter sends four separately encoded real streams along four linearly independent real vectors.
- 3 Achievability of 1.2 Degrees of Freedom: Two alignments at each receiver reduce eight interfering signals to a six-dimensional interference space.The construction specifies corresponding alignments for receivers 1, 2, and 3.
- Linear independence: The remaining signaling vectors are chosen from the alignment equations after the first two vectors at each transmitter are sampled from a continuous distribution.This random construction ensures alignment while enabling a probability-one linear-independence argument.
- Linear independence: When the relevant sine-function arguments are not integer multiples of π, all ten real coefficients vanish, establishing linear independence of desired and interfering vectors.Each desired signal can then be projected into the null space of the other desired and interfering vectors.
- General result: Theorem 2 establishes 1.2 degrees of freedom for the 3-user channel under its phase conditions, and Corollary 1 extends at least 1.2 degrees of freedom to K users for almost all coefficients.The K-user extension uses only three active users, while the remaining users are shut off.
- General result: The corollary settles the Høst-Madsen-Nosratinia conjecture in the negative, while a separate theorem identifies coefficient conditions yielding only 1 degree of freedom.The paper notes that related phase expressions occur in both the achievability and singularity conditions.
4 Upper bound
For almost all constant complex channel coefficients, the considered linear interference-alignment schemes achieve at most 1.2 degrees of freedom in the 3-user interference channel.
- 4 Upper bound: The upper bound concerns this class of linear schemes and does not exclude other schemes exceeding 1.2 degrees of freedom in special measure-zero channel cases.The paper notes that 3/2 degrees of freedom are achievable in some such cases.
- 4 Upper bound: A signal vector can align with interference at only one undesired receiver without becoming inseparable from interference at its desired receiver.Such inseparability makes the vector useless for providing an interference-free signaling dimension.
- 4 Upper bound: 1.2 degrees of freedom is the maximum achievable by the considered linear interference-alignment schemes for almost all constant complex 3-user channels.The exception is a subset of channel-coefficient values with measure 0.
- 4 Upper bound: The signaling space is partitioned according to whether each subspace aligns with interference at unintended receivers.The partitions are disjoint because simultaneous alignment at both undesired receivers prevents separation at the desired receiver.
- 4 Upper bound: Counting desired dimensions and overlapping interference dimensions at all three receivers yields the 1.2-degree-of-freedom upper bound.At receiver 1, the desired signal occupies d1 dimensions, while the two interfering signals occupy d2 + d3 − d23 dimensions within 2S dimensions; analogous constraints hold at the other receivers.
5 Asymmetric Complex Signaling - Applications
The paper applies asymmetric complex signaling to interference-as-noise settings and to constant-coefficient X channels, including a 4/3-degree-of-freedom result without channel variation.
- 5.1 Rate Region with Interference as Noise: Asymmetric complex signaling, channel extensions, and interference alignment can significantly affect achievable interference-channel rates even when receivers treat interference as noise.The standard MISO interference-channel model excludes these possibilities, making its achievable rates suboptimal for the corresponding single-antenna interference channel.
- 5.1 Rate Region with Interference as Noise: For iterative interference-channel rate optimization, incorporating asymmetric complex signaling may provide higher rates and possibly higher degrees of freedom.This application is discussed for schemes that treat interference as noise, including algorithms that do not ignore interference alignment.
- 5.2 The 2 User X Channel: The 2-user X channel has four independent messages, with one message from each transmitter to each receiver.Its physical channel is the same as the 2-user interference channel, but its message configuration differs.
- 5.2 The 2 User X Channel: 4/3 degrees of freedom are achievable on the constant-coefficient 2-user complex Gaussian X channel.The achievability proof uses a 3-complex-symbol extension, while the converse is established in prior work.
- 5.2 The 2 User X Channel: In the extended X channel, beamforming achieves 2 interference-free streams for each of the 4 messages.The construction aligns the 4 interfering vectors at each receiver into a 2-dimensional interference space, leaving the desired streams linearly independent.
6 Conclusion
The paper overturns the conjecture for almost all constant complex channels by achieving 1.2 degrees of freedom through asymmetric complex signaling. It identifies scope limits and positions asymmetric complex signaling as a broader conceptual contribution.
- Conclusion: 1.2 degrees of freedom are achievable for complex Gaussian interference networks with more than two users and constant coefficients, for almost all channel values.The scheme uses three simultaneously active users and five complex channel symbols per supersymbol.
- Conclusion: For the three-user channel, each signal vector can align with interference at no more than one undesired receiver, limiting this scheme to 1.2 degrees of freedom.This is the stated maximum for the considered linear beamforming and interference alignment schemes.
- Conclusion: The same scheme achieves the 4/3-degree-of-freedom outer bound for the two-user complex Gaussian X channel with constant coefficients.This removes the prior reliance on time-varying or frequency-selective channel coefficients for that result.
- Conclusion: The degrees of freedom of real Gaussian interference channels with constant coefficients remain open for almost all channel values.For three users, future progress may combine magnitude-based signal-level alignment with phase-based signal-vector alignment.
- Conclusion: Asymmetric complex signaling emerges as a fundamental idea with potential applications beyond the degrees-of-freedom result.The paper places it alongside interference alignment, channel extensions, and inseparability of parallel interference channels as essential ingredients in the broader problem.