Exercises

$R_1 \leq \log_2(1 + 10) = \log_2(11) \approx 3.459\;\text{bits/s/Hz}KATEXPLACEHOLDER0ENDR_2 \leq \log_2(1 + 10) = \log_2(11) \approx 3.459\;\text{bits/s/Hz}$$

$R_1 + R_2 \leq \log_2(1 + 10 + 10) = \log_2(21) \approx 4.392\;\text{bits/s/Hz}$$

Decode user 1 first (user 1 sees user 2 as noise):

$R_1 = \log_2(1 + 10/(1+10)) = \log_2(21/11) \approx 0.933$

$R_2 = \log_2(1 + 10) \approx 3.459$

Check: $0.933 + 3.459 = 4.392$ $\checkmark$

Decode user 2 first: by symmetry, $(R_1, R_2) = (3.459, 0.933)$.

The pentagon has vertices at $(0,0)$, $(3.459, 0)$, $(3.459, 0.933)$, $(0.933, 3.459)$, and $(0, 3.459)$. $\blacksquare$

$C_{\text{sum}} = \log_2\det\!\left(\mathbf{I}_{N_r} + \frac{1}{\sigma^2}(P_1\mathbf{h}_1\mathbf{h}_1^H + P_2\mathbf{h}_2\mathbf{h}_2^H)\right)KATEXPLACEHOLDER0END= \log_2\det\!\left(\mathbf{I}_{N_r} + \frac{1}{\sigma^2}\mathbf{H}\mathbf{P}\mathbf{H}^{H}\right)$$where$\mathbf{H} = [\mathbf{h}_1, \mathbf{h}_2] \in \mathbb{C}^{4 \times 2}$.

This is precisely the capacity of a $2 \times 4$ point-to-point MIMO channel $\mathbf{H}$ with input covariance $\mathbf{Q} = \mathbf{P} = \text{diag}(P_1, P_2)$.

Interpretation: The MAC sum rate is maximised when users transmit independently with their individual power constraints, and the receiver performs SIC. The result equals what a cooperative 2-antenna transmitter could achieve with the same total power and the same channels — the lack of transmitter cooperation costs nothing in terms of sum rate. $\blacksquare$

$f(\emptyset) = \log_2\det(\mathbf{I}) = \log_2(1) = 0$. $\checkmark$

For $\mathcal{S} \subseteq \mathcal{T}$:

$$\mathbf{R}_\mathcal{T} = \sigma^2\mathbf{I} + \sum_{k \in \mathcal{T}}P_k\mathbf{h}_k\mathbf{h}_k^H = \mathbf{R}_\mathcal{S} + \sum_{k \in \mathcal{T}\setminus\mathcal{S}}P_k\mathbf{h}_k\mathbf{h}_k^H$$

Since $\mathbf{R}_\mathcal{T} \succeq \mathbf{R}_\mathcal{S}$ (positive semidefinite ordering), $\det(\mathbf{R}_\mathcal{T}) \geq \det(\mathbf{R}_\mathcal{S})$, so $f(\mathcal{T}) \geq f(\mathcal{S})$. $\checkmark$

The marginal gain of adding user $k$ to set $\mathcal{S}$:

$$f(\mathcal{S} \cup \{k\}) - f(\mathcal{S}) = \log_2(1 + P_k\mathbf{h}_k^H\mathbf{R}_\mathcal{S}^{-1}\mathbf{h}_k)$$

For $\mathcal{S} \subseteq \mathcal{T}$: $\mathbf{R}_\mathcal{T} \succeq \mathbf{R}_\mathcal{S}$, so $\mathbf{R}_\mathcal{T}^{-1} \preceq \mathbf{R}_\mathcal{S}^{-1}$, hence:

$$\mathbf{h}_k^H\mathbf{R}_\mathcal{T}^{-1}\mathbf{h}_k \leq \mathbf{h}_k^H\mathbf{R}_\mathcal{S}^{-1}\mathbf{h}_k$$

Therefore:

$$f(\mathcal{T} \cup \{k\}) - f(\mathcal{T}) \leq f(\mathcal{S} \cup \{k\}) - f(\mathcal{S})$$

confirming submodularity. $\blacksquare$

$\mathbf{h}_1^H\mathbf{h}_2 = (1 \cdot 1 + 1 \cdot (-1))/2 = 0$.

The channels are orthogonal.

With orthogonal channels and equal power $P_1 = P_2 = 10$:

$$R_{\text{sum}}^{\text{DPC}} = \log_2(1 + 10 \cdot 1/2 \cdot 2) + \log_2(1 + 10 \cdot 1/2 \cdot 2)$$

Actually, with beamforming along each channel direction: $|\mathbf{h}_1^H\mathbf{w}_1|^2 = 1$ with $\mathbf{w}_1 = \mathbf{h}_1$.

$R_{\text{sum}}^{\text{DPC}} = \log_2(1+10) + \log_2(1+10) = 2\log_2(11) \approx 6.92$

ZF precoder: $\mathbf{W} = \mathbf{H}^{H}(\mathbf{H}\mathbf{H}^{H})^{-1}$. Since $\mathbf{H}\mathbf{H}^{H} = \mathbf{I}$: $\mathbf{W} = \mathbf{H}^{H} = [\mathbf{h}_1, \mathbf{h}_2]$.

Columns already have unit norm, so no power penalty.

$R_{\text{sum}}^{\text{ZF}} = 2\log_2(11) \approx 6.92$.

DPC and ZF achieve the same rate because orthogonal channels mean ZF incurs no power penalty — it is a unitary rotation, equivalent to eigenmode transmission. $\blacksquare$

For fixed powers $(P_1, P_2)$, the MAC capacity region $\mathcal{C}_{\text{MAC}}(P_1, P_2)$ is a convex polyhedron (intersection of linear inequalities in $(R_1, R_2)$).

$\mathcal{C}_{\text{BC}}(P) = \bigcup_{P_1+P_2 \leq P} \mathcal{C}_{\text{MAC}}(P_1, P_2)$.

Take any two rate points $(R_1^a, R_2^a) \in \mathcal{C}_{\text{MAC}}(P_1^a, P_2^a)$ and $(R_1^b, R_2^b) \in \mathcal{C}_{\text{MAC}}(P_1^b, P_2^b)$ with $P_1^a + P_2^a \leq P$ and $P_1^b + P_2^b \leq P$.

For $\lambda \in [0,1]$, define $P_k^\lambda = \lambda P_k^a + (1-\lambda)P_k^b$. Then $P_1^\lambda + P_2^\lambda \leq P$.

The MAC rate constraints are concave in the powers (since $\log\det$ is concave in PSD matrices). Therefore:

$$\lambda R_k^a + (1-\lambda)R_k^b \leq R_k^{\text{bound}}(P_k^\lambda)$$

for all subset constraints, showing that $\lambda(R_1^a, R_2^a) + (1-\lambda)(R_1^b, R_2^b) \in \mathcal{C}_{\text{MAC}}(P_1^\lambda, P_2^\lambda) \subseteq \mathcal{C}_{\text{BC}}(P)$.

Hence $\mathcal{C}_{\text{BC}}(P)$ is convex. $\blacksquare$

User 1 is encoded without any pre-cancellation. User 2 is DPC-encoded against user 1's codeword.

User 2's rate: $R_2 = \log_2(1 + P_2\|\mathbf{h}_2\|^2/\sigma^2)$ (interference from user 1 is pre-cancelled).

User 1's rate: $R_1 = \log_2(1 + P_1|\mathbf{h}_1^H\mathbf{w}_1|^2/ (\sigma^2 + P_2|\mathbf{h}_1^H\mathbf{w}_2|^2))$ (sees user 2 as interference).

Roles reversed: user 1 benefits from DPC (higher rate), user 2 sees user 1's interference (lower rate).

Rule: The user encoded last (with DPC) gets the most benefit. This produces different corner points of the capacity region. The entire boundary is traced by varying the encoding order and power allocation. $\blacksquare$

With $N_t = 4$, $K = 3$: the effective ZF channel gain is $\chi^2_{2(4-3+1)} = \chi^2_4$ distributed (2 complex degrees of freedom).

$$\text{SNR}_{k}^{\text{ZF}} \sim \frac{P}{K\sigma^2} \cdot \chi^2_4 / 2$$

The mean effective gain is $N_t - K + 1 = 2$.

At $P/(K\sigma^2) = 100/3 \approx 15.2$ dB:

$$\mathbb{E}[R_k^{\text{ZF}}] = \mathbb{E}\!\left[\log_2\!\left(1 + \frac{100}{3}\cdot G_k\right)\right]$$

where $G_k \sim \text{Gamma}(2, 1)$ (mean 2).

Using $\mathbb{E}[G_k] = 2$: $R_k^{\text{ZF}} \approx \log_2(1 + 100/3 \cdot 2) \approx \log_2(67.7) \approx 6.08$ bits/s/Hz (Jensen's bound; exact value is slightly lower due to Jensen's inequality).

$\|\mathbf{h}_k\|^2 \sim \chi^2_{2N_t} = \chi^2_8$ with mean $N_t = 4$.

$R_k^{\text{DPC}} \approx \log_2(1 + 100/3 \cdot 4) \approx \log_2(134.3) \approx 7.07$

Gap: $\approx 1.0$ bit/s/Hz per user. This constant gap reflects the ZF power penalty. $\blacksquare$

$\alpha = 2/10 = 0.2$.

$$\mathbf{H}\mathbf{H}^{H} = \begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix}$$

$$\mathbf{H}\mathbf{H}^{H} + 0.2\mathbf{I} = \begin{bmatrix} 5.2 & 4 \\ 4 & 5.2 \end{bmatrix}$$

$\det = 5.2^2 - 16 = 27.04 - 16 = 11.04$

$$(\mathbf{H}\mathbf{H}^{H} + 0.2\mathbf{I})^{-1} = \frac{1}{11.04} \begin{bmatrix} 5.2 & -4 \\ -4 & 5.2 \end{bmatrix}$$

$$\tilde{\mathbf{W}} = \mathbf{H}^{H}(\mathbf{H}\mathbf{H}^{H}+0.2\mathbf{I})^{-1} = \frac{1}{11.04}\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} \begin{bmatrix} 5.2 & -4 \\ -4 & 5.2 \end{bmatrix} = \frac{1}{11.04}\begin{bmatrix} 6.4 & -2.8 \\ -2.8 & 6.4 \end{bmatrix}$$

Normalise so $\sum_k p_k\|\tilde{\mathbf{w}}_k\|^2 = P = 10$.

$\|\tilde{\mathbf{w}}_1\|^2 = (6.4^2 + 2.8^2)/11.04^2 = (40.96+7.84)/121.88 = 0.400$

With equal power split $p_1 = p_2 = 5$: Total power used: $5 \times 0.400 \times 2 = 4.0 < 10$. Scale up: $p_k = 10/(2 \times 0.400) = 12.5$.

Signal: $|\mathbf{h}_1^H\tilde{\mathbf{w}}_1|^2$, Interference: $|\mathbf{h}_1^H\tilde{\mathbf{w}}_2|^2$.

Computing numerically and finding the SINR for each user gives the RZF sum rate. $\blacksquare$

$\frac{df}{dw_k} = \frac{1}{w_k \ln 2} - e_k^{\text{MMSE}} = 0KATEXPLACEHOLDER0ENDw_k^* = \frac{1}{e_k^{\text{MMSE}} \ln 2} \cdot \frac{1}{\ln 2}$$Wait, more carefully:$f(w_k) = \log_2(w_k) - w_k e_k + 1$,$\frac{df}{dw_k} = \frac{1}{w_k \ln 2} - e_k = 0 \implies w_k^* = \frac{1}{e_k \ln 2}$Hmm, let us use natural log:$f(w_k) = \frac{\ln w_k}{\ln 2} - w_k e_k + 1$.$f'(w_k) = \frac{1}{w_k \ln 2} - e_k = 0 \implies w_k^* = \frac{1}{e_k \ln 2}$. Actually the standard formulation uses$\ln$:$f(w_k) = \ln(w_k) - w_k e_k + 1$,$f'(w_k) = 1/w_k - e_k = 0$, so$w_k^* = 1/e_k$.

With $w_k^* = 1/e_k^{\text{MMSE}} = 1 + \text{SINR}_k$:

$$f(w_k^*) = \ln(1 + \text{SINR}_k) - (1+\text{SINR}_k)\frac{1}{1+\text{SINR}_k} + 1$$

$$= \ln(1 + \text{SINR}_k) - 1 + 1 = \ln(1 + \text{SINR}_k)$$

Converting to $\log_2$: $f(w_k^*) = \log_2(1 + \text{SINR}_k) = R_k$. $\blacksquare$

$\mathcal{L} = \sum_{k=1}^K [\mu_k\ln(w_k) - \mu_k w_k e_k(u_k, \{\mathbf{w}_j\}) + \mu_k] - \lambda\!\left(\sum_k \|\mathbf{w}_k\|^2 - P\right)$$where$e_k = |1-u_k^*\mathbf{h}_k^H\mathbf{w}k|^2 + |u_k|^2(\sum{j\neq k}|\mathbf{h}_k^H\mathbf{w}_j|^2 + \sigma^2)$.

Step 1 ($u_k$): $\partial\mathcal{L}/\partial u_k^* = 0$ gives the MMSE receiver.

Step 2 ($w_k$): $\partial\mathcal{L}/\partial w_k = 0$ gives $w_k^* = 1/e_k^{\text{MMSE}}$.

Step 3 ($\mathbf{w}_k$): $\partial\mathcal{L}/\partial\mathbf{w}_k^* = 0$ gives the weighted MMSE precoder with $\lambda$ as the regulariser.

Each block update increases (or maintains) $\mathcal{L}$. Since at optimal $(u_k^*, w_k^*)$, $\mathcal{L} = \text{WSR}$, the WSR is non-decreasing across iterations. Boundedness above (by DPC capacity) ensures convergence. $\blacksquare$

$M + N = 2 + 2 = 4$, $(K+1)d = 4 \times 1 = 4$.

$4 \geq 4$: feasibility condition is satisfied (tight).

Alignment equations: $K(K-1)d^2 = 3 \times 2 \times 1 = 6$ complex equations.

But each $\mathbf{u}_k^H\mathbf{H}_{kj}\mathbf{v}_{j} = 0$ for $j \neq k$ gives $K(K-1) = 6$ scalar equations.

Design DoF: Each $\mathbf{v}_{k}$ has $M - d = 1$ complex DoF, each $\mathbf{u}_k$ has $N - d = 1$ complex DoF. Total: $K(M-d+N-d) = 3 \times 2 = 6$ DoF.

Equations = DoF: the system is critically determined, generically yielding a finite number of solutions. $\blacksquare$

Give receiver $k$ the messages of all users except user $k$ (genie information). Then receiver $k$ can cancel all interference and decode user $k$ at rate $\log_2(1 + P_k|h_{kk}|^2/\sigma^2)$, which has 1 DoF.

However, this genie bound gives each user 1 DoF, totalling $K$ DoF. A tighter bound is needed.

Consider users 1 and 2. Give user 2's message to receiver 1. Receiver 1 then has a 2-input, 1-output SISO channel: $y_1 = h_{11}x_1 + h_{12}x_2 + \text{cancelled} + n_1$

After subtracting $h_{12}x_2$ (known), it decodes $x_1$ with 1 DoF. But the total DoF of the pair $(R_1 + R_2)$ is bounded by:

$$R_1 + R_2 \leq \log_2(1 + (P_1|h_{11}|^2 + P_2|h_{12}|^2)/\sigma^2)$$

which has only 1 DoF.

For constant SISO channels, any pair of users shares at most 1 sum DoF. By repeated application of this pairwise bound and the submodularity of mutual information:

$$\text{DoF}_{\text{total}} \leq 1$$

for the constant $K$-user SISO IC. This contrasts with $K/2$ DoF for time-varying channels, proving that temporal variation (or frequency selectivity) is essential for interference alignment. $\blacksquare$

$\mathbb{E}[|h_k|^2] = 1$.

$R_{\text{random}} \approx \log_2(1 + 10 \times 1) = \log_2(11) \approx 3.46$ bits/s/Hz.

$\mathbb{E}[\max_k |h_k|^2] \approx \ln(100) + 0.577 \approx 5.18$.

$R_{\text{opp}} \approx \log_2(1 + 10 \times 5.18) = \log_2(52.8) \approx 5.72$ bits/s/Hz.

$\Delta R = 5.72 - 3.46 = 2.26$ bits/s/Hz.

This is a 65% throughput improvement from exploiting multi-user diversity, with no extra power or bandwidth. $\blacksquare$

Let $X_{(1)} \leq X_{(2)} \leq \cdots \leq X_{(K)}$ be the order statistics. Define spacings $D_k = X_{(k)} - X_{(k-1)}$ (with $X_{(0)} = 0$).

For i.i.d. Exp(1) variables, the spacings are independent with $D_k \sim \text{Exp}(K - k + 1)$, so $\mathbb{E}[D_k] = 1/(K-k+1)$.

$\mathbb{E}[X_{(K)}] = \sum_{k=1}^{K}\mathbb{E}[D_k] = \sum_{k=1}^{K}\frac{1}{K-k+1} = \sum_{j=1}^{K}\frac{1}{j} = H_K$$

By the Euler-Maclaurin formula:

$$H_K = \int_1^K \frac{1}{x}dx + \frac{1}{2}\!\left(1 + \frac{1}{K}\right) + O(1/K^2)$$

$$= \ln K + \gamma + O(1/K)$$

where $\gamma = \lim_{K\to\infty}(H_K - \ln K) \approx 0.5772$ is the Euler-Mascheroni constant. $\blacksquare$

With i.i.d. Rayleigh fading, all users have identical statistics. PF scheduling maximises $R_k(t)/\bar{R}_k(t)$, and by symmetry, all users have the same long-run average throughput $\bar{R}_k = \bar{R}$ for all $k$.

Therefore PF reduces to $k^* = \arg\max_k R_k(t)$ in steady state (since all $\bar{R}_k$ are equal), which is max-rate scheduling.

Each user is scheduled with probability $1/K$. When user $k$ is scheduled, its instantaneous rate is the maximum of $K$ i.i.d. rates: $R_k^{\text{sched}} = \log_2(1 + \text{SNR} \cdot X_{(K)})$ where $X_{(K)}$ is the maximum channel gain.

$\mathbb{E}[X_{(K)}] \approx \ln K + \gamma$.

$\bar{R} = \frac{1}{K}\mathbb{E}[R_k^{\text{sched}}] = \frac{1}{K}\mathbb{E}\!\left[\log_2(1 + \text{SNR}\cdot X_{(K)})\right]$$Sum throughput:$K\bar{R} = \mathbb{E}[\log_2(1 + \text{SNR} \cdot X_{(K)})] \approx \log_2(1 + \text{SNR} \cdot \ln K)$. This achieves the same$\log_2\ln K$scaling as max-rate scheduling. PF achieves multi-user diversity with equal long-run rates across users.$\blacksquare$

$R_{\text{TDMA}} = \frac{1}{K}\sum_{k=1}^K \log_2(1 + KP_k\|\mathbf{h}_k\|^2/\sigma^2) \approx \log_2(\text{SNR}) + O(1)$$DoF = 1, regardless of$N_t$and$K$.

$R_{\text{ZF}} = N_t\log_2(\text{SNR}) + N_t\mathbb{E}[\log_2(G_k)] + O(1)$$where$G_k \sim \chi^2_2$(1 DoF per user). DoF$= N_t$.

$R_{\text{DPC}} = N_t\log_2(\text{SNR}) + N_t\mathbb{E}[\log_2(\|\mathbf{h}_k\|^2)] + O(1)$$DoF$= N_t$. Gap to ZF is constant$\approx N_t\log_2(N_t)$ bits.

$R_{\text{ZF+SUS}} = N_t\log_2(\text{SNR}) + N_t\log_2(\ln(K/N_t)) + O(1)$$DoF$= N_t$, plus an additional$N_t\log_2\ln K$multi-user diversity gain. For$K \gg N_t$, this can exceed DPC with$K = N_t$users.$\blacksquare$

Each transmitter-receiver pair has an $M \times M$ MIMO channel $\mathbf{H}_{kj}$. User $k$ sends $d = M/2$ streams using precoder $\mathbf{V}_k \in \mathbb{C}^{M \times M/2}$.

At receiver $k$, the interference from user $j$ occupies subspace $\text{span}(\mathbf{H}_{kj}\mathbf{V}_j)$. IA requires:

$$\dim\!\left(\bigcup_{j \neq k}\text{span}(\mathbf{H}_{kj}\mathbf{V}_j)\right) \leq M/2$$

so that the remaining $M/2$ dimensions are free for the desired signal.

Using time extensions (as in the SISO case), the precoders are designed over $n$ symbol periods, with each user transmitting $nM/2$ streams in $nM$-dimensional space. The asymptotic alignment construction of Cadambe and Jafar extends: all interference is confined to $nM/2$ dimensions, leaving $nM/2$ dimensions for the desired signal.

Total DoF $= K \times M/2 = KM/2$.

This shows that MIMO provides a multiplicative DoF improvement: the MIMO IC DoF is $M$ times the SISO IC DoF ($K/2$). $\blacksquare$

(a) SUS selects at most $N_t = 4$ users.

(b) After selecting 3 users, if only 2 candidates pass the threshold but SUS can still pick the best one, it selects 4 users total (iteration 4 picks from the 2 remaining candidates). If zero candidates pass the threshold at some iteration, SUS terminates with fewer than $N_t$ users.

If 2 users pass the threshold after iteration 3, SUS picks the stronger one in iteration 4, serving 4 users total.

(c) Unserved users wait for the next scheduling slot. In a time-varying channel, they may be selected in future slots when their channels are more favourable. Fairness mechanisms (e.g., proportional fair scheduling) ensure all users are served over time. $\blacksquare$