A Proof of the Water-Filling Theorem

Author: phy-东西
Reviewer: 时光

Problem Statement

  The water-filling theorem solves a fundamental problem in information theory: how should power be allocated across AWGN channels to maximize their total capacity? Suppose there are $K$ parallel AWGN channels with mutually independent noise processes and noise powers $σ^2_1,σ^2_2,··· ,σ^2_K$. Given a total power budget $P$, we seek the allocation that maximizes the combined capacity of the $K$ channels.

  As an optimization problem, this becomes:

$\begin{aligned} &\max_{p_1, \dots , p_K}\sum^{K}_{k=1} \log_2 \left(1 + \frac{p_k}{\sigma ^2_k}\right)\\ \mathrm{s.t.}&\sum^K_{k = 1}p_k \le P\\ &p_k \ge 0, \ \ \ k = 1, 2, \dots , K\end{aligned} \tag{1.1}$

An Intuitive Proof

  We begin with a relatively intuitive derivation.

  At first, it may seem best to assign all available power to the channel with the least noise. But a channel’s capacity is $C_k = \log_2 (1 + p_k / σ^2_k)$, so the marginal gain in capacity decreases as its allocated power increases. Each additional increment of power should therefore go to the channel that currently provides the largest marginal gain.

  Assume an initial allocation $p^{(0)}_1 ,p^{(0)}_2 , \dots ,p^{(0)}_K$ satisfying:

$\sum^K_{k = 1}p^{(0)}_k < P, \ \ \ p^{(0)}_{k} \ge 0, \ \ \ k = 1, 2, \dots , K$

  Clearly, $p^{(0)}_1 = p^{(0)}_2 = \dots = p^{(0)}_K = 0$ is a valid starting point. Let a positive quantity $(P - \sum^K_{k=1}p^{(0)}_k) \ge \delta > 0$ be the next increment of power to allocate. Assigning $\delta$ to channel $k$ increases its capacity by:

$\Delta C = \log_2 \left( 1 + \frac{p^{(0)}_k + \delta}{\sigma^2_k}\right) - \log_2 \left(1 + \frac{p^{(0)}_k}{\sigma^2_k}\right) = \log_2 \left(1 + \frac{\delta}{p^{(0)}_k + \sigma^2_k}\right)\tag{2.1}$

  The increment should plainly go to the channel with the smallest $p^{(0)}_k + \sigma^2_k$. If $\delta$ is made arbitrarily small at each step, then once all the power has been allocated, every active channel will have the same value of $\sigma^2_k +p_k$. Channels whose noise power $σ^2_k$ exceeds this level receive no power. Thus:

$p_k = \max \{0, p^* - \sigma^2_k\}\tag{2.2}$

  Here $p^⋆$ is chosen so that $\sum^K_{k = 1}p_k = P$.

  Consider any allocation for which $p_i + \sigma^2_i > p_j + \sigma^2_j$, and set $\delta = \min\{p_i, (p_i + \sigma^2_i - p_j - \sigma^2_j)/2\}$. Beginning with $p^{(0)}_i = p_i - \delta, p^{(0)}_j = p_j$, the argument above shows that assigning $\delta$ to channel $j$ produces more capacity than assigning it to channel $i$. After this reallocation, either $p_i + \sigma^2_i = p_j + \sigma^2_j$ or $p_i = 0$; in the latter case, $\sigma_i^2 \ge p_j + \sigma^2_j$.

A Rigorous Proof

  Rewrite $(1.1)$ as:

$\begin{aligned}&\min_{p_1, \dots, p_K} - \sum^K_{k = 1}\ln\left( 1 + \frac{p_k}{\sigma^2_k}\right)\\ \mathrm{s.t.}&\sum^K_{k = 1}p_k - P \le 0\\ &-p_k \le 0, \ \ \ k = 1, 2, \dots, K \end{aligned}\tag{3.1}$

  Because $−\ln(·)$ is convex, the objective function is convex. The feasible region $(p_1, p_2, \dots, p_K)\in \mathcal{P}$ is also readily shown to be convex. This is therefore a convex optimization problem, whose Lagrangian is:

$\begin{aligned} &\mathcal{L}(p_1, p_2, \dots, p_K; \lambda_0, \lambda_1, \dots, \lambda_K) \\ &= -\sum^K_{k = 1} \ln \left(1 + \frac{p_k}{\sigma^2_k}\right) + \lambda_0 \left( \sum^K_{k = 1} p_k - P \right) - \sum^K_{k = 1}\lambda_k p_k \end{aligned} \tag{3.2}$

  Its KKT conditions are:

$\frac{\partial \mathcal{L}}{\partial p_k} = - \frac{1}{\sigma^2_k + p_k} + \lambda_0 - \lambda_k = 0, \ \ \ k = 1, 2, \dots, K \tag{3.3a}$

$\lambda_k \ge 0, \ \ \ k = 0, 1, 2, \dots, K\tag{3.3b}$

$\sum^K_{k = 1}p_k \le P\tag{3.3c}$

$\lambda_0 \left( \sum^K_{k = 1}p_k - P\right) = 0\tag{3.3d}$

$p_k \ge 0, \ \ \ k = 1, 2, \dots, K\tag{3.3e}$

$\lambda_k p_k = 0, \ \ \ k = 1, 2, \dots, K\tag{3.3f}$

  Equation $(3.3\mathrm{a})$ can be rewritten as:

$\begin{aligned}\lambda_k = \lambda_0 - \frac{1}{\sigma^2_k + p_k} \\ p_k = \frac{1}{\lambda_0 - \lambda_k} - \sigma^2_k \end{aligned}\tag{3.4}$

  If $\sum^K_{k=1} p_k < P$, then $\lambda_0 = 0, \lambda_k = -1/(\sigma^2_k + p_k)<0$, contradicting $(3.3\mathrm{b})$. Therefore $\sum^K_{k = 1} p_k = P$. Because each $p_k$ is nonnegative, they cannot all be zero.

  Without loss of generality, suppose $\sigma^2_1 \le \sigma^2_2 \le \dots \le \sigma^2_K$. Because the $p_k$ cannot all vanish, at least one $p_k$ is positive, and its corresponding $λ_k$ is zero. For channels with $p_k > 0, λ_k = 0$:

$p_k = \frac{1}{\lambda_0 - \lambda_k} - \sigma^2_k = \frac{1}{\lambda_0} - \sigma^2_k \tag{3.5}$

  If $λ_k > 0$, then $p_k = 0$, and:

$\lambda_k = \lambda_0 - \frac{1}{\sigma^2_k + p_k} = \lambda_0 - \frac{1}{\sigma^2_k} \tag{3.6}$

  Because $σ^2_k$ increases monotonically:

$\lambda_K \ge \lambda_{K-1} \ge \dots \ge \lambda_k > 0, \ \ \ p_K = p_{K-1} = \dots = p_k = 0 \tag{3.7}$

  This is exactly the result obtained above. For active channels ($λ_k = 0$), the allocated powers $p_k$ satisfy $p_k +σ^2_k = 1/\lambda_0$, a constant. Inactive channels receive no power ($\lambda_k > 0$; equation $(3.7)$ shows that if a channel with noise power $\sigma_k$ is inactive, every channel with still greater noise power is inactive as well). Power is allocated in this way until the entire budget has been used. The quantity $1 / \lambda_0$ is the $p^⋆$ introduced above.

Water-Filling for Continuous Parallel Channels

  For colored noise $σ^2 (f)$ in a transform domain such as the frequency domain, the water-filling problem can be written:

$\begin{aligned} &\min_{p(f)} - \int^{f_h}_{f_l}\log_2 \left( 1 + \frac{p(f)}{\sigma^2 (f)}\right) \mathrm{d}f\\ \mathrm{s.t.}&\int^{f_h}_{f_l}p(f)\mathrm{d}f\le P\\ &p(f)\ge 0, \ \ \ f_l \le f \le f_h \end{aligned}\tag{4.1}$

  Construct the Lagrangian functional:

$\begin{aligned}&\mathcal{L}[p(f),\lambda_0 ,\lambda_1 (f)] \\ = &-\int^{f_h}_{f_l} \ln \left( 1 + \frac{p(f)}{\sigma^2 (f)}\right) \mathrm{d}f + \lambda_0 \left( \int^{f_h}_{f_l} p(f)\mathrm{d}f\right) - \lambda_1 (f)p(f) \end{aligned}\tag{4.2}$

  Its KKT conditions are:

$\delta \mathcal{L} = \int^{f_h}_{f_l}\left(\lambda_0 - \frac{1}{\sigma^2 (f) + p(f)}\right) \delta p(f)\mathrm{d}f - \lambda_1 (f)\delta p(f) = 0, \ \ \ \forall \delta p(f) \tag{4.3a}$

$\int^{f_h}_{f_l} p(f)\mathrm{d}f \le P \tag{4.3b}$

$\lambda_0 \ge 0,\lambda_1 (f)\ge 0, \ \ \ f_l\le f \le f_h \tag{4.3c}$

$\lambda_0 \left(\int^{f_h}_{f_l} p(f) \mathrm{d}f-P\right) = 0 \tag{4.3d}$

$p(f)\ge 0, \ \ \ f_l\le f \le f_h \tag{4.3e}$

$\lambda_1 (f)p(f) = 0, \ \ \ f_l\le f \le f_h \tag{4.3f}$

  Here $\delta p(f)$ is the variation of $p(f)$.

  When $\lambda_1 (f) > 0$, corresponding to an inactive channel above, $p(f) ≡ 0$, and hence $\delta p(f) = 0$. Conversely, when $p(f) > 0$, $\lambda_1 (f) ≡ 0$, corresponding to an active channel, and $p(f) = \frac{1}{\lambda} − σ^2 (f)$. Therefore:

$p(f) = \max \{0,p^* - \sigma^2 (f)\}\tag{4.4}$

  where $p^⋆$ satisfies:

$\int^{f_h}_{f_l} p(f)\mathrm{d}f = P\tag{4.5}$

  Why is this called “water-filling”? Picture $σ^2 (f)$ as the bottom of a bowl and the available power as water poured into it. Wherever power is allocated, the sum of the noise and signal power rises to the same flat “water level.” Any noise floor above that level represents a channel that receives no power.