PaperlayerView exact revision on arXiv

Source-linked AI summary

Feedback Capacity of the Gaussian Interference Channel to within 2 Bits

Changho Suh, David Tse

arXiv:1005.3338v1cs.IT

TL;DR

The paper asks how much feedback can improve communication in the two-user Gaussian interference channel. It develops achievable schemes and a new outer bound, obtaining constant-gap capacity characterizations and showing that feedback can provide multiplicative gains through improved resource utilization.

  • Problem

    The paper studies whether feedback can significantly increase capacity in interference channels where each receiver decodes only its corresponding transmitter's message.

  • Method

    The paper develops explicit achievable schemes and a new outer bound, using a deterministic model to provide insight into the Gaussian channel.

  • Results

    The feedback capacity region is characterized to within 2 bits per user and the symmetric capacity to within 1 bit per user universally.

  • Takeaways & Limitations

    Feedback can provide multiplicative gain by maximizing resource utilization and enabling more efficient resource sharing between interfering users.

Abstract

from arXiv · show

We characterize the capacity region to within 2 bits/s/Hz and the symmetric capacity to within 1 bit/s/Hz for the two-user Gaussian interference channel (IC) with feedback. We develop achievable schemes and derive a new outer bound to arrive at this conclusion. One consequence of the result is that feedback provides multiplicative gain, i.e., the gain becomes arbitrarily large for certain channel parameters. It is a surprising result because feedback has been so far known to provide no gain in memoryless point-to-point channels and only bounded additive gain in multiple access channels. The gain comes from using feedback to maximize resource utilization, thereby enabling more efficient resource sharing between the interfering users. The result makes use of a deterministic model to provide insights into the Gaussian channel. This deterministic model is a special case of El Gamal-Costa deterministic model and as a side-generalization, we establish the exact feedback capacity region of this general class of deterministic ICs.

I. INTRODUCTION

This paper characterizes the two-user Gaussian interference channel with feedback approximately, showing that feedback can yield unbounded multiplicative gains by improving resource utilization. It develops achievable schemes and new outer bounds, uses a deterministic model for insight, and exactly characterizes a broader deterministic class.

  • Method: The authors develop explicit achievable schemes and a tighter outer bound, using block Markov encoding, backward decoding, and Han-Kobayashi message splitting.The symmetric scheme uses two stages, while the general rate-region scheme uses infinitely many stages.
  • Motivation and main findings: Feedback provides multiplicative capacity gain in certain Gaussian interference regimes, with the gain becoming arbitrarily large as SNR and INR increase.The gain is unbounded in the very strong interference regime and the feedback-to-non-feedback capacity ratio can exceed one.
  • Capacity-region structure: The feedback capacity region requires only three types of inequalities, unlike the non-feedback region, which includes R1 + 2R2 and 2R1 + R2 bounds.The paper attributes this difference to efficient resource utilization under feedback.
  • Interpretation: Feedback improves resource utilization by enabling more efficient resource sharing between interfering users.The resource-hole interpretation links this utilization improvement to the deactivation of the 2R1 + R2 bound.
  • Deterministic-model generalization: The deterministic model is a special case of the El Gamal-Costa model, and its exact feedback capacity region is established as a side-generalization.The result also supports inferring an approximate feedback capacity region for two-user Gaussian MIMO interference channels.
  • Main contributions: The paper characterizes the feedback capacity region to within 2 bits per user and the symmetric capacity to within 1 bit universally.The result applies across all channel parameters.

A. Deterministic Model

The deterministic interference channel models signals as binary levels, using the model to develop feedback schemes for strong and weak interference. Feedback fills resource holes and exploits side information, improving symmetric rates over non-feedback transmission.

  • Model: The linear deterministic model represents each link by signal bit levels, with upper levels above noise and overlapping levels combined modulo 2.In the symmetric channel, direct links have n levels and cross links have m levels.
  • Strong Interference Regime: 3/2 is the symmetric rate in the illustrated strong-interference example, compared with 1 without feedback.The second stage refines previously sent bits without transmitting additional information, yielding a 50% improvement.
  • Strong Interference Regime: In strong interference, feedback lets transmitters relay the other user's information through the cross links, creating an alternative path.The two-stage scheme uses feedback to decode and forward the other user's bits, allowing receivers to solve the resulting linear equations.
  • Interpretation: The resource-hole interpretation attributes feedback gains to fuller resource utilization and improved sharing of signal levels.The feedback scheme packs all resource levels and refines corrupted bits without causing new interference.
  • Weak Interference Regime: In weak interference, information is split into common m bits and private n −m bits, with private levels treated as cheaper because they consume fewer receiver resources.The non-feedback scheme sends private bits first and then selects common bits according to m and n.

C. Optimality of the Achievable Scheme for the Deterministic IC

The deterministic model explains feedback’s gain as fuller resource utilization without reducing transmission cost, yielding the V curve. The paper then translates this insight into a two-stage Gaussian scheme using feedback and Alamouti-based orthogonalization.

  • Deterministic IC: The paper first conjectures that the achievable scheme cannot exceed the V curve, then proves this optimality rigorously.The earlier resource-hole argument alone did not establish the conjecture.
  • Deterministic IC: The achievable symmetric feedback rate traces the V curve, while the non-feedback capacity traces the W curve because some resource levels remain unused without feedback.The V curve reflects full utilization; the W curve reflects underutilization over part of the interference range.
  • Deterministic IC: Feedback fills previously unused resource levels, whereas it cannot reduce the transmission cost of common bits.A common bit may still consume two resource levels across the receivers.
  • Gaussian IC: The Gaussian construction uses two stages: feedback lets transmitters obtain the other user’s signal, then Alamouti processing makes the received signals orthogonal.This enables separation of the users’ signals across two time slots.
  • Gaussian IC: In strong interference, the scheme achieves the relevant rate bound, while in weak interference it combines Alamouti processing for common information with newly added private information.Private signals cannot be completely ignored in the Gaussian channel.
  • Gaussian IC: Amplify-and-forward avoids message-splitting and eliminates the performance loss caused by private signals, although computing its rate region is more demanding.The paper therefore focuses on decode-and-forward despite its larger gap.

E. An Outer Bound

The outer-bound analysis compares the achievable symmetric rate with a new bound to quantify the remaining gap. It finds a worst-case one-bit gap near equal SNR and INR, with different asymptotic behavior across interference regimes.

  • Gap analysis: The gap between the inner and outer bounds is upper-bounded by exactly 1 bit.The comparison is presented numerically in Fig. 3.
  • Gap analysis: The worst-case gap occurs when SNR ≈ INR, while for α ≥ 2 the gap is around 0.5 bits.These statements describe the reported gap behavior for the corresponding parameter regimes.
  • Gap analysis: In the strong-interference regime, the gap approaches 0 as SNR and INR increase, whereas in the weak-interference regime it does not.The supplied passage does not specify the weak-regime limiting value.
  • Outer-bound comparison: The scheme uses uncorrelated transmitter signals, so it loses beamforming gain, while the outer bound permits arbitrary transmitter correlation.The resulting 1-bit guarantee is therefore based on the outer bound; the actual gap may be smaller.
  • Outer-bound comparison: Beamforming gain matters mainly when SNR and INR are close, corresponding to α ≈ 1, where the channel is equivalent to a multiple access channel.The cited related schemes are optimal in that multiple-access case.

IV. CAPACITY REGION TO WITHIN 2 BITS

The paper develops feedback schemes that approximate the Gaussian interference-channel capacity region and uses deterministic insights to organize the construction. The resulting region is supported by explicit achievable distributions and is described with fewer inequality types than the non-feedback approximation.

  • Achievable region: The proposed achievable scheme approximates the capacity region of the Gaussian interference channel with feedback.The construction is presented as a region-achieving scheme rather than only a symmetric-rate argument.
  • Deterministic insight: An infinite-staged scheme is needed in a deterministic example to amortize an unavoidable initial loss and approach the rate pair (2, 1).The two-staged construction alone does not achieve that pair.
  • Achievable region: The scheme uses block Markov encoding, message-splitting, and backward decoding to propagate common information through feedback.Each transmitter decodes the other user’s common message and carries both common messages forward.
  • Gaussian construction: In the Gaussian channel, amplify-and-forward performs better than decode-and-forward because private signals cannot be completely ignored, but it requires heavy rate-region computations.The paper consequently focuses on decode-and-forward despite its larger gap.
  • Region characterization: The generic scheme also applies to discrete memoryless and El Gamal-Costa deterministic interference channels, supporting the stated deterministic generalization.The Gaussian result follows by selecting an appropriate joint input distribution.
  • Achievable region: Private power is chosen so that each private signal appears below the noise level at the other receiver, with remaining power assigned to the common message.This adapts the simplified Han–Kobayashi power split.
  • Region characterization: The feedback achievable region is described by three types of inequalities, unlike the non-feedback approximation’s five types including 2R1+R2 and R1+2R2.The paper states that whether the exact feedback region also needs only three types remains unknown.

B. An Outer Bound Region

The outer-bound section establishes converse constraints for the feedback capacity region using cutset bounds and a tighter non-cutset bound. Its proof combines a noisy genie with functional relationships induced by feedback.

  • Outer bound: Theorem 3 gives an outer region that contains the feedback capacity region.The theorem is established through symmetric proofs of the stated bounds.
  • Outer bound: Two of the converse inequalities are cutset bounds, while the non-cutset bound is the main proof challenge.The non-cutset bound is then used to obtain the symmetric-capacity outer bound.
  • Proof strategy: The proof begins with Fano’s inequality and applies entropy and mutual-information inequalities, conditioning arguments, and the channel’s memoryless structure.These steps lead from the finite-blocklength inequalities to the desired upper bounds.
  • Proof strategy: The converse uses a genie that provides a noisy version of the interfering signal together with the other user’s message.The noisy genie avoids the loose bound that would result from revealing the full interfering signal.
  • Proof strategy: Claims about feedback-induced functional relationships among channel variables are essential to proving the non-cutset bound.The paper identifies several such relationships and uses them in the entropy calculations.

C. 2-Bit Gap to the Capacity Region

The achievable and outer-bound regions differ by at most 2 bits/s/Hz/user. The gap arises from message-splitting and the relay structure inherent in the feedback interference channel.

  • 2 bits/s/Hz/user is the gap between the inner and upper bound regions.The proof bounds each individual-rate and sum-rate difference by 2 bits.
  • Message-splitting causes a loss when decoding common messages while treating private signals as noise.
  • 1 bit of the gap comes from doubled effective noise power caused by private signals.
  • The other 1-bit gap is associated with the relay structure of the feedback interference channel.When one user’s rate is ignored, the other transmitter–receiver pair can be viewed as a relay Gaussian channel with a 1-bit inner–outer gap.
  • The actual gap may be less than 2 bits because the outer bound permits arbitrary correlation between transmitters.
  • Reducing the gap below 1 bit is difficult without substantial progress on the single-relay Gaussian channel.
  • The symmetric capacity is achieved to within 1 bit by the infinite-staged scheme, but the source of this gap differs from the two-staged scheme.The infinite-staged scheme loses 1 bit through message-splitting, whereas the two-staged scheme loses it through absent beamforming gain.

V. THE FEEDBACK CAPACITY REGION OF EL GAMAL-COSTA MODEL

The paper characterizes the exact feedback capacity region of the El Gamal-Costa deterministic interference channel. The result also yields the feedback capacity region of the linear deterministic interference channel as a corollary.

  • The El Gamal-Costa deterministic interference channel is a special case used to provide insights into the Gaussian interference channel.
  • Theorem 5 gives the exact feedback capacity region for the El Gamal-Costa deterministic interference channel.
  • The model requires each transmitter’s visible component V_k to be recoverable at the other receiver as a common signal.
  • The capacity region is described by a joint distribution p(u, x1, x2)=p(u)p(x1|u)p(x2|u) and entropy bounds on R1, R2, and R1+R2.
  • The linear deterministic interference channel’s feedback capacity region follows as a corollary of Theorem 5.It is achieved with constant U and independent uniformly distributed X1 and X2.

VI. ROLE OF FEEDBACK

Feedback enlarges the interference-channel capacity region by filling otherwise unused signal resources, even when symmetric capacity does not improve. The paper combines deterministic insights, achievable schemes, and a new outer bound to establish these gains and their approximation guarantees.

  • Feedback can provide multiplicative gain even in regimes where symmetric capacity does not improve.
  • The feedback capacity region is enlarged in the symmetric linear deterministic regime despite unchanged symmetric capacity.
  • Feedback fills resource holes, increasing resource utilization and removing the 2R1 + R2 bound in the illustrated setting.An initial-stage hole can be amortized with infinitely many stages.
  • Kramer’s scheme can have an unbounded gap to symmetric capacity for every α except α=1.
  • The proposed achievable scheme attains the symmetric capacity to within 1 bit and the capacity region to within 2 bits.
  • The paper uses block Markov encoding with infinitely many stages and derives a new outer bound for the approximate capacity-region characterization.
  • The exact feedback capacity region is characterized for the El Gamal-Costa deterministic interference channel.
  • Feedback can provide multiplicative gain in many-to-many channels, unlike point-to-point, many-to-one, or one-to-many channels.

APPENDIX A

The appendix develops an Alamouti-based amplify-and-forward scheme for the symmetric Gaussian interference channel and explains it through a noisy binary expansion model. Feedback lets transmitters learn interference-plus-noise and forward scaled innovations for decoding.

  • The proposed symmetric-rate scheme uses two stages and Alamouti-based amplify-and-forward transmission.
  • Feedback allows each transmitter to recover interference plus noise by subtracting previously transmitted signals from the feedback.
  • The noisy binary expansion model adds memoryless Bernoulli noise to a deterministic model to represent signal–noise interaction.
  • The binary expansion interpretation shows that the second stage need not send additional information beyond the innovation.
  • The transmitters scale and forward the recovered signals, allowing receivers to combine observations and decode the transmitted bits.
  • The scheme matches the Alamouti-based amplify-and-forward construction in the Gaussian channel.
  • The coding proof uses block Markov encoding, backward decoding, error analysis, and Fourier–Motzkin elimination.

APPENDIX C

The appendix proves an outer bound using dependence-balance arguments and an auxiliary variable that induces conditional independence between the users’ inputs. It then completes the individual-rate and sum-rate converse bounds.

  • Converse construction: Given U_i, X1i and X2i are conditionally independent.The proof first shows conditional independence of W1 and W2 given U_i, then derives the corresponding input independence.
  • Rate bounds: The individual-rate outer bound follows from Fano’s inequality, entropy nonnegativity, and the fact that conditioning reduces entropy.The appendix separately derives the first individual-rate bound and then considers a second bound involving the feedback-dependent variables.
  • Rate bounds: The sum-rate bound is obtained by expanding mutual information and applying the functional dependencies of outputs, inputs, and auxiliary variables.The proof introduces a uniformly distributed time index Q and concludes with an input distribution satisfying p(u, x1, x2) = p(u)p(x1|u)p(x2|u).
  • Converse construction: The converse uses the dependence-balance-bound technique to construct an auxiliary variable U_i.The construction establishes I(W1; W2|U_i) = 0 and supports the subsequent conditional-independence argument.
  • Converse construction: The auxiliary variable is chosen from past auxiliary sequences using U_i := (V i−1 ...).The surrounding argument uses the feedback-dependent functional relationships of each channel input to define the auxiliary variable.

1. Since the channel is deterministic

Because the channel is deterministic, the first transmitter’s input depends on its message and past feedback, while information from the second message to the first receiver passes through V2i.

  • 1. Since the channel is deterministic: X1i is a function of (W1, V i−1 2 ).The deterministic encoding rule makes the current input depend on the first message and the past feedback sequence.
  • 1. Since the channel is deterministic: Information from W2 to the first link pair must pass through V2i.The passage also notes that X1i depends on past output sequences until the current time.

APPENDIX D

Appendix D evaluates dominant terms in the high-SNR regime after setting INR = SNR^α, with the final case determined by the resulting asymptotic expression.

  • APPENDIX D: INR is parameterized as SNR^α for the high-SNR analysis.The appendix invokes prior expressions to evaluate the relevant asymptotic terms under this parameterization.
  • APPENDIX D: In the high-SNR regime, SNR is a dominant term and 0 < ρ∗ < 1.This condition appears in the asymptotic evaluation of the relevant expression.
  • APPENDIX D: For α ≥1, the first and second dominant terms are SNR^4.The passage identifies the corresponding dominant terms before stating that this yields the desired result in the final case.
Loading 1005.3338v1…