PaperlayerView exact revision on arXiv

Source-linked AI summary

Completely Stale Transmitter Channel State Information is Still Very Useful

Mohammad Ali Maddah-Ali, David Tse

arXiv:1010.1499v3cs.IT

TL;DR

Long feedback delays can make current-channel prediction useless for multiplexing gains. The paper instead exploits stale CSI to recover receivers’ prior side information, showing that outdated feedback still provides degrees-of-freedom gains and can be optimal under i.i.d. receiver channels.

  • Problem

    When feedback delay makes delayed CSIT independent of the current channel, it is unclear whether the resulting loss of multiplexing gain is fundamental or specific to prediction-based schemes.

  • Method

    The transmitter uses delayed CSIT to learn side information that receivers obtained from previous transmissions rather than to predict the current channel.

  • Results

    For M ≥ K, the scheme achieves K degrees of freedom, and this is optimal when receiver channels are independent and identically distributed.

  • Takeaways & Limitations

    Completely outdated CSIT can provide a degrees-of-freedom gain in a memoryless channel, even when prediction-based schemes provide none.

Abstract

from arXiv · show

Transmitter channel state information (CSIT) is crucial for the multiplexing gains offered by advanced interference management techniques such as multiuser MIMO and interference alignment. Such CSIT is usually obtained by feedback from the receivers, but the feedback is subject to delays. The usual approach is to use the fed back information to predict the current channel state and then apply a scheme designed assuming perfect CSIT. When the feedback delay is large compared to the channel coherence time, such a prediction approach completely fails to achieve any multiplexing gain. In this paper, we show that even in this case, the completely stale CSI is still very useful. More concretely, we show that in a MIMO broadcast channel with $K$ transmit antennas and $K$ receivers each with 1 receive antenna, $\frac{K}{1+1/2+ ...+ \frac{1}{K}} (> 1) $ degrees of freedom is achievable even when the fed back channel state is completely independent of the current channel state. Moreover, we establish that if all receivers have independent and identically distributed channels, then this is the optimal number of degrees of freedom achievable. In the optimal scheme, the transmitter uses the fed back CSI to learn the side information that the receivers receive from previous transmissions rather than to predict the current channel state. Our result can be viewed as the first example of feedback providing a degree-of-freedom gain in memoryless channels.

I. INTRODUCTION

The paper asks whether completely outdated CSIT fundamentally prevents multiplexing gains and shows that it remains useful in MIMO broadcast channels. Under i.i.d. receiver channels, the achieved degrees of freedom are optimal.

  • Motivation: Feedback delay creates quantization and timing inaccuracies, with delayed information potentially describing a channel that has already changed.The prediction-based approach can offer no multiplexing gain when coherence time is shorter than feedback delay.
  • Contribution: The paper answers affirmatively that delayed feedback can provide non-trivial multiplexing gains even when it cannot predict the current channel.The transmitter instead uses outdated CSI to learn side information received during previous transmissions.
  • Main results: For M ≥ K, the scheme achieves K degrees of freedom per second per Hz, with sum rate scaling as log2 SNR + o(log2 SNR).This result applies under full-rank channel assumptions and weak channel-statistics conditions.
  • Main results: When receiver channels are independent and identically distributed, the achieved degrees of freedom are optimal.The paper also characterizes the order-one DoF region for M = K.
  • Comparison: For K ≥ 2, outdated CSI yields more than one degree of freedom, although it does not reach the K degrees of freedom available with perfect CSIT.When K is large, the achievable gain is almost linear in K.
  • Scope: The paper leaves the optimal degrees of freedom unresolved for some cases with more users than transmit antennas.Specifically, the achievable expression does not match the upper bound when M < K − j + 1.

III. ACHIEVABLE SCHEME FOR THEOREM 1

The achievable-scheme analysis centers on the square case M = K and begins with M = K = 2 and M = K = 3.

  • The scheme's key case is a system with equal numbers of transmit antennas and receivers.
  • The analysis starts with the concrete cases M = K = 2 and M = K = 3.
  • The square cases provide the starting point for explaining the achievable scheme for Theorem 1.

A. Achievable Scheme for M = K = 2

For M = K = 2, the scheme uses two phases over three time-slots: receivers first obtain and save overheard equations, then the transmitter swaps those equations using outdated CSIT.

  • The two-phase scheme uses three time-slots to transmit independently encoded symbols intended for the two receivers.Phase one feeds the receivers; phase two swaps overheard equations.
  • Each receiver saves an overheard equation carrying information intended for the other receiver.These saved equations are later used to resolve the receiver's own symbols.
  • The received equations are sufficient to solve for each receiver's two intended symbols when the relevant channel matrix is full rank.The construction ignores bounded noise variance for degrees-of-freedom counting.
  • The transmitter uses CSI from earlier time-slots to form and transmit a linear combination of the two overheard equations.This swapping transmission occurs at time-slot n = 3.
  • The scheme can use arbitrary random linear combinations of the intended symbols and of the two overheard equations, including rank-one choices in the final transmission.
  • With 2N transmit antennas and N antennas at each receiver, the same scheme achieves DoF of 4N.

2) Generating Higher Order Symbols:

The scheme recursively converts private symbols into higher-order common symbols, whose delivery yields improved degrees of freedom for two- and three-receiver systems.

  • 2) Generating Higher Order Symbols:: DoF1(2, 2) = 4/3 is obtained by delivering four private symbols over two initial slots plus one slot for their shared equation.
  • 2) Generating Higher Order Symbols:: Overheard equations are combined into common symbols so each receiver can recover the desired equation using side information already saved from earlier transmissions.
  • 2) Generating Higher Order Symbols:: For K = 3, phase one sends three private symbols per receiver and generates three order-two symbols from nine data symbols.
  • 2) Generating Higher Order Symbols:: Without using overheard equations, the nine-stream three-receiver construction would require six additional slots and yield DoF of one.
  • 2) Generating Higher Order Symbols:: DoF1(3, 3) = 18/11 follows after accounting for the delivery of order-two and order-three symbols.Phase three itself uses one time-slot per order-three common symbol, so DoF3(3, 3) = 1.
  • 2) Generating Higher Order Symbols:: The three-receiver construction generates order-two symbols, then order-three common symbols, and finally broadcasts each order-three symbol to all receivers.The three phases successively increase message order before final common delivery.

C. General Proof of Achievability for Theorem 1

The achievable scheme concatenates K phases that successively convert order-j symbols into order-(j+1) symbols, yielding the stated degrees of freedom in square and rectangular systems.

  • C. General Proof of Achievability for Theorem 1: K phases successively transform order-j symbols into order-(j+1) symbols, with the final phase generating no additional symbols.Each phase can also be viewed as delivering common symbols of a fixed order through all later phases.
  • C. General Proof of Achievability for Theorem 1: For each receiver subset S of size j, the transmitter sends K−j+1 random linear combinations whose overheard equations become simultaneously useful to receivers in S.The transmitter combines overheard equations associated with subsets of size j+1 to create higher-order symbols.
  • C. General Proof of Achievability for Theorem 1: DoF_K(K)=1, and solving the recursive phase relation establishes achievability of Theorem 1 in the square case.The same recursive construction underlies the order-j delivery process.
  • C. General Proof of Achievability for Theorem 1: K−j+1 transmit antennas suffice for phase j, so the square-system DoF for order-j messages extends to rectangular systems whenever M ≥ K−j+1.The construction uses only the antennas required by the current phase rather than all K antennas.

D. Implementation Issues

The symbol-by-symbol scheme can be implemented block by block to exploit channel coherence and reduce training and feedback overhead; for large coherence products, the DoF approaches 4/3.

  • D. Implementation Issues: Block-by-block implementation exploits time-frequency coherence to reduce channel training and feedback overhead.The discussion specializes to M=K=2 and uses blocks consecutive in time and frequency.
  • D. Implementation Issues: 4/3 is approached when T_cW_c ≫ 1 in the M=K=2 implementation.The reported expression is described as close to 4/3 for most wireless channels with large coherence-time–bandwidth products.

IV. OUTER-BOUND

The converse upgrades the channel into a physically degraded broadcast channel, reduces common-message requirements to private messages, and applies feedback-capacity arguments across receiver permutations.

  • IV. OUTER-BOUND: The converse gives receivers instantaneous channel-state information while retaining delayed information at the transmitter and received signals.This constructs an outer-bound channel with stronger receiver-side information.
  • IV. OUTER-BOUND: A permutation-based upgrade gives later receivers the outputs of earlier receivers, producing a physically degraded broadcast channel.The resulting channel is denoted the improved channel.
  • IV. OUTER-BOUND: Order-j common messages can be treated as private messages for the earliest receiver in each required subset because degradedness lets later receivers decode them.The message requirements are reassigned according to the smallest receiver position in the permutation.
  • IV. OUTER-BOUND: Feedback does not improve the physically degraded channel, so marginal distributions suffice; summing the resulting inequalities over all K! permutations proves the theorem.The converse consequently ignores receiver coupling in the improved channel.

V. THE DoF REGION FOR K = M

For K=M, the paper characterizes the DoF region and establishes achievability by induction, while a three-receiver, two-antenna construction shows an extra receiver can improve order-one DoF but remains suboptimal.

  • V. THE DoF REGION FOR K = M: The DoF region for M=K is characterized as the polyhedron specified by the outer-bound constraints.The proof proceeds by induction on K.
  • V. THE DoF REGION FOR K = M: A strictly positive corner point must equal (1,1,...,1); other feasible points are obtained through convex combinations and time-sharing.Perturbation arguments show that positive non-equal points are not corners, and induction handles points with zero coordinates.
  • A. Achievable Scheme for M = 2, K = 3: For M=2 and K=3, the sub-optimal construction uses six first-phase slots to send 12 order-one messages and generate three order-two symbols.The generated symbols are then delivered using the order-two scheme.
  • A. Achievable Scheme for M = 2, K = 3: DoF_1(2,3) exceeds DoF_1(2,2), demonstrating that the extra receiver can improve achievable DoF.The construction purifies overheard equations and combines them into symbols needed by receiver pairs.
  • A. Achievable Scheme for M = 2, K = 3: 24/17 remains below 3 for the achieved DoF_1(2,3), so the proposed three-receiver scheme is not optimal.The paper also notes that 3 can be achieved for order-one messages by ignoring one receiver.

B. General Proof for Theorem 4

The general algorithm uses K−j+1 phases to convert order-j symbols into higher-order symbols, while delayed CSIT supplies purified overheard equations that enable decoding. This construction supports the stated outer-bound relationship, including a case where M<K−j+1 requires a sub-optimal extension.

  • General algorithm: K−j+1 phases progressively transform order-j symbols into order-(j+1) symbols, with the final phase delivering order-K symbols.Phase j takes symbols needed by j receivers and generates symbols needed by j+1 receivers.
  • Phase construction: Each subset-specific sub-phase sends random linear combinations of symbols desired by its j receivers using K−j over ηj time-slots.The transmitter uses at least qj+1 antennas, and the received equations are denoted LS,r(t).
  • Antenna-limited case: When M<K−j+1, the available overheard equations need not be linearly independent, so only qj combinations are simultaneously useful to each receiver.The paper develops a sub-optimal algorithm for this antenna-limited case.
  • Decoding: Receivers obtain enough linearly independent equations to solve all designated order-j symbols after the generated higher-order symbols are delivered.The construction explicitly counts the desired and overheard equations used for decoding.
  • Side-information generation: Delayed CSIT lets the transmitter form random combinations of purified equations that are simultaneously useful to all receivers in a subset of size j+1.These combinations become order-(j+1) symbols for the next phase.

VII. IMPROVED SCHEME FOR M = 2

For M=2, the paper improves the earlier achievable scheme by introducing an alternative solution for M=K=2 and using its idea to obtain the optimal scheme for M=2, K=3. The resulting scheme meets the outer bound, showing the earlier scheme is generally suboptimal.

  • Comparison: The earlier scheme achieves DoF1(2,3)=24/11, while the improved construction reaches the outer bound.The passage states that the earlier scheme is loose in this setting.
  • Improved scheme: The alternative approach for M=K=2 provides the key idea for achieving the optimal DoF when M=2 and K=3.The paper first explains the alternative two-user solution before establishing tightness for the three-user case.

A. Alternative Scheme for M = K = 2

For M=K=2, the alternative scheme first creates common order-two symbols from overheard linear combinations, then delivers those symbols to both receivers. It starts with four order-one symbols in one time-slot and achieves the stated DoF expression.

  • Phase one: One shared transmission mixes four order-one symbols for receivers A and B, giving each receiver a linear combination containing both users’ symbols.Receiver A observes L1(uA,vA)+L3(uB,vB), with an analogous mixture at receiver B.
  • Side information: Each receiver needs the other user’s mixed contribution plus its own mixed contribution to recover its two desired symbols.The required side information is L2(uA,vA) and L3(uB,vB).
  • Common symbols: The two needed mixed contributions are packaged as two order-two symbols, uAB and vAB, because both receivers require them.These common symbols are delivered in a later phase.
  • Accounting: The phase converts 4 order-one symbols in 1 time-slot into 2 order-two symbols, which are then delivered using the order-two scheme.The construction’s achieved DoF is obtained by combining these phase costs.

B. Optimal Scheme for M = 2 and K = 3

For M=2 and K=3, the optimal construction organizes transmissions so receivers can share overheard linear combinations as order-two symbols. Its accounting meets the outer bound, and the design is connected to packet-erasure broadcast schemes through delayed knowledge of prior reception states.

  • B. Optimal Scheme for M = 2 and K = 3: The first phase uses 12 order-one messages in 3 time-slots to generate 6 order-two symbols for the M=2, K=3 system.The paper identifies this sub-algorithm as leading to an optimal scheme.
  • B. Optimal Scheme for M = 2 and K = 3: Receivers A, B, and C each observe mixtures of symbols intended for A and B during the first time slot.The mixtures are represented by L1 through L6 in the described realization.
  • B. Optimal Scheme for M = 2 and K = 3: The decoding design gives each receiver four required linear combinations, including combinations shared by receiver pairs.The listed combinations allow each receiver to solve for its four desired symbols.
  • B. Optimal Scheme for M = 2 and K = 3: The transmitter delivers pairwise-common combinations to receiver pairs A-B, A-C, and B-C.These combinations are the side information required by the receivers’ decoding conditions.
  • B. Optimal Scheme for M = 2 and K = 3: The M=2, K=3 algorithm meets the outer bound, establishing that the earlier Section VI scheme is suboptimal in general.The passage reports the outer-bound value as DoF*1(2,3)≤3/2.
  • Connections: The schemes are inspired by packet-erasure broadcast channels, where delayed feedback reveals prior erasure states and overheard packets become exploitable side information.The connection is conceptual rather than a claim that the channels are identical.
  • X. CONCLUSIONS: In memoryless multiuser channels, feedback can increase capacity because overheard information can be exploited in future transmissions.This contrasts with the cited point-to-point memoryless-channel result.

APPENDIX A AN IDENTITY

The appendix establishes identity (47) by defining its left-hand side as f(j) and proving the required relations for j in the stated range. It also notes that Equation (49) follows by induction.

  • The proof considers j satisfying 1 ≤ j ≤ K and, subsequently, 1 ≤ j ≤ K −1.
  • The appendix defines the left-hand side of identity (47) as f(j).
  • The established relations yield identity (47).
  • Equation (49) can be proved by induction.
Loading 1010.1499v3…