Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices

Introduction

Of complementary interest are the information-theoretic limits of the sparsity recovery problem, which apply to the performance of any procedure regardless of its computational complexity. Such analysis has two purposes: first, to demonstrate where known polynomial-time methods achieve the information-theoretic bounds, and second, to reveal situations in which current methods are sub-optimal. An interesting question which arises in this context is the effect of the choice of measurement matrix on the information-theoretic limits of sparsity recovery. As we will see, the standard Gaussian measurement ensemble is an optimal choice in terms of minimizing the number of observations required for recovery. However, this choice produces highly dense measurement matrices, which may lead to prohibitively high computational complexity and storage requirements. Sparse matrices can reduce this complexity, and also lower communication cost and latency in distributed network and streaming applications. On the other hand, such measurement sparsity, though beneficial from the computational standpoint, may reduce statistical efficiency by requiring more observations to decode. Therefore, an important issue is to characterize the trade-off between measurement sparsity and statistical efficiency.

With this motivation, this paper makes two contributions. First, we derive sharper necessary conditions for exact support recovery, applicable to a general class of dense measurement matrices (including non-Gaussian ensembles). In conjunction with the sufficient conditions from previous work , this analysis provides a sharp characterization of necessary and sufficient conditions for various sparsity regimes. Our second contribution is to address the effect of measurement sparsity, meaning the fraction $\gamma\in(0,1]$ of non-zeros per row in the matrices used to collect measurements. We derive lower bounds on the number of observations required for exact sparsity recovery, as a function of the signal dimension $p$, signal sparsity $k$, and measurement sparsity $\gamma$. This analysis highlights a trade-off between the statistical efficiency of a measurement ensemble and the computational complexity associated with storing and manipulating it.

The remainder of the paper is organized as follows. We first define our problem formulation in Section 1.1, and then discuss our contributions and some connections to related work in Section 1.2. Section 2 provides precise statements of our main results, as well as a discussion of their consequences. Section 3 provides proofs of the necessary conditions for various classes of measurement matrices, while proofs of more technical lemmas are given in the appendices. Finally, we conclude and discuss open problems in Section 4.

Our goal is to perform exact recovery of the support set $S$, which corresponds to a standard model selection error criterion. More precisely, we measure the error between the estimate $\widehat{\beta}$ and the true signal $\beta$ using the $\{0,1\}$-valued loss function:

We say that sparsity recovery is asymptotically reliable if $p_{err}\rightarrow 0$ as $n\rightarrow\infty$. Since we are trying to recover the support exactly from noisy measurements, our results necessarily involve the minimum value of $\beta$ on its support,

In particular, our results apply to decoders that operate over the signal class

With this set-up, our goal is to find necessary conditions on the parameters $(n,p,k,\beta_{min},\gamma)$ that any decoder, regardless of its computational complexity, must satisfy for asymptotically reliable recovery to be possible. We are interested in lower bounds on the number of measurements $n$, in general settings where both the signal sparsity $k$ and the measurement sparsity $\gamma$ are allowed to scale with the signal dimension $p$. As our analysis shows, the appropriate notion of rate for this problem is $R=\frac{\log{p\choose k}}{n}$.

2 Our contributions

The paper was the first to consider the information-theoretic limits of exact subset recovery using dense Gaussian measurement ensembles, explicitly identifying the minimum value $\beta_{min}$ as the key parameter. This analysis yielded necessary and sufficient conditions on general quadruples $(n,p,k,\beta_{min})$ for asymptotically reliable recovery. Subsequent work has extended this type of analysis to the criterion of partial support recovery. In this paper, we consider only exact support recovery, but provide results for general dense measurement ensembles, thereby extending previous results. In conjunction with known sufficient conditions , one consequence of our first main result (Theorem 1, below) is a set of sharp necessary and sufficient conditions for the optimal decoder to recover the support of a signal with linear sparsity ($k=\Theta(p)$), using only a linear fraction of observations ($n=\Theta(p)$). Moreover, for the special case of the standard Gaussian ensemble, Theorem 1 also recovers some results independently obtained in concurrent work by Reeves , and Fletcher et al. .

Main results and consequences

Note that when $\gamma=1$, $X$ is exactly the standard Gaussian ensemble. We refer to the sparsification parameter $0\leq\gamma\leq 1$ as the measurement sparsity. Our analysis allows this parameter to vary as a function of $(n,p,k)$.

We begin by noting an analogy to the Gaussian channel coding problem that yields a straightforward but loose set of necessary conditions. Support recovery can be viewed as a channel coding problem, in which there are $N={p\choose k}$ possible support sets of $\beta$, corresponding to messages to be sent over a Gaussian channel with noise variance $1$. The effective code rate is then $R=\frac{\log{p\choose k}}{n}$. If each support set $S$ is encoded as the codeword $c(S)=X\beta$, where $X$ has i.i.d. Gaussian entries, then by standard Gaussian channel capacity results, we immediately obtain a lower bound on the number of observations $n$ necessary for asymptotically reliable recovery,

This bound is tight for $k=1$ and Gaussian measurements, but loose in general. As Theorem 1 clarifies, there are additional elements in the support recovery problem that distinguish it from a standard Gaussian coding problem: first, the signal power $\|\beta\|_{2}^{2}$ does not capture the inherent problem difficulty for $k>1$, and second, there is overlap between support sets for $k>1$. The following result provides sharper conditions on subset recovery.

The proof of Theorem 1, given in Section 3, uses Fano’s inequality to bound the probability of error of any recovery method. In addition to the standard Gaussian ensemble ($X_{ij}\sim N(0,1)$), this result also covers matrices from other common ensembles (e.g., Bernoulli $X_{ij}\in\,\{-1,+1\}$). It generalizes and strengthens earlier results on subset recovery . Note that $\|\beta\|_{2}^{2}\geq k\beta_{min}^{2}$ (with equality in the case when $|\beta_{i}|=\beta_{min}$ for all indices $i\in S$), so that this bound is strictly tighter than the intuitive bound (11). Moreover, by fixing the value of $\beta$ at $(k-1)$ indices to $\beta_{min}$ and allowing the last component of $\beta$ to tend to infinity, we can drive the power $\|\beta\|_{2}^{2}$ to infinity, while still having the minimum enter the lower bound.

Theorem 1 has some consequences related to results proved in concurrent work. Reeves and Gastpar have shown that in the regime of linear sparsity $k/p=\alpha>0$, if any decoder is given only a linear fraction sample size (meaning that $n=\Theta(p)$), then in order to recover the support exactly, one must have $k\beta_{min}^{2}\rightarrow+\infty$. This result is one corollary of Theorem 1, since if $\beta_{min}^{2}=\Theta(1/k)$, then we have

so that the scaling $n=\Theta(p)$ is precluded. In other concurrent work, Fletcher et al. used direct methods to show that for the special case of the standard Gaussian ensemble, the number of observations must satisfy $n>\Omega\left(\frac{\log(p-k)}{\beta_{min}^{2}}\right)$. This bound is a consequence of our lower bound $f_{2}(p,k,\beta_{min})$; moreover, Theorem 1 implies the same lower bound for general (non-Gaussian) ensembles as well.

In the regime of linear sparsity, Wainwright showed, by direct analysis of the optimal decoder, that the scaling $\beta_{min}^{2}=\Omega(\log(k)/k)$ is sufficient for exact support recovery using a linear fraction $n=\Theta(p)$ of observations. Combined with the necessary condition in Theorem 1, we obtain the following corollary that provides a sharp characterization of the linear-linear regime:

Consider the regime of linear sparsity, meaning that $k/p=\alpha\in(0,1)$, and suppose that a linear fraction $n=\Theta(p)$ of observations are made. Then the optimal decoder can recover the support exactly if and only if $\beta_{min}^{2}=\Omega(\log k/k)$.

2 Effect of measurement sparsity

Furthermore, let $H(\cdot)$ denote the entropy functional. With this notation, we have the following result.

The proof of Theorem 2, given in Section 3, again uses Fano’s inequality, but explicitly analyzes the effect of measurement sparsification on the distribution of the observations. The necessary condition in Theorem 2 is plotted in Figure 1, showing distinct regimes of behavior depending on how the quantity $\gamma k$ scales, where $\gamma\in$ is the measurement sparsification parameter and $k$ is the signal sparsity index. In order to characterize the thresholds at which measurement sparsity begins to degrade the performance of any decoder, Corollary 2 below further bounds the necessary conditions in Theorem 2 in three cases. For any scalar $\gamma$, let $H_{binary}(\gamma)$ denote the entropy of a $\operatorname{Ber}(\gamma)$ variate.

The necessary conditions in Theorem 2 can be simplified as follows.

If $\gamma k=\tau$ for some constant $\tau$, then

Corollary 2 reveals three regimes of behavior, defined by the scaling of the measurement sparsity $\gamma$ and the signal sparsity $k$. If $\gamma k\rightarrow\infty$ as $p\rightarrow\infty$, then the recovery threshold (18) is of the same order as the threshold for dense measurement ensembles. In this regime, sparsifying the measurement ensemble has no asymptotic effect on performance. In sharp contrast, if $\gamma k\rightarrow 0$ sufficiently fast as $p\rightarrow\infty$, then the recovery threshold (20) changes fundamentally compared to the dense case. Finally, if $\gamma k=\Theta(1)$, then the recovery threshold (19) transitions between the two extremes. Using the bounds in Corollary 2, the necessary conditions in Theorem 2 are shown in Table 2 under different scalings of the parameters $(n,p,k,\beta_{min},\gamma)$. In particular, if $\gamma=o(\frac{1}{k\log{k}})$ and the minimum value $\beta_{min}^{2}$ does not increase with $k$, then the denominator $\gamma k\log\frac{1}{\gamma}$ goes to zero. Hence, the number of measurements that any decoder needs in order to recover reliably increases dramatically in this regime.

Proofs of our main results

If a decoder can recover the support of any $p$-dimensional $k$-sparse vector $\beta$, then it must be able to recover a $k$-sparse vector that is constant on its support. Furthermore, having knowledge of the value $\beta_{min}$ at the decoder cannot increase the probability of error. Finally, we assume that $\beta_{j}=\beta_{min}$ for all $j\in S$ to construct the most difficult possible instance within our ensemble. Thus, we can apply Fano’s inequality to lower bound the probability of error in the restricted problem, and so obtain a lower bound on the probability of error for the general problem. This procedure yields the lower bounds $f_{1}(p,k,\beta_{min})$ and $g_{1}(p,k,\beta_{min},\gamma)$ in Theorems 1 and 2 respectively.

Restricted ensemble B: The second restricted ensemble is designed to capture the confusable effects of the relatively small number $(p-k+1)$ of very close-by subsets (see Figure 2b). This restricted ensemble is defined as follows. Suppose that the decoder is given the locations of all but the smallest non-zero value of the vector $\beta$, as well as the values of $\beta$ on its support. More precisely, let $j^{\star}$ denote the unknown location of the smallest non-zero value of $\beta$, which we assume achieves the minimum (i.e., $\beta_{j^{\star}}=\beta_{min}$), and let $T=S\setminus\{j^{\star}\}$. Given knowledge of $(T,\beta_{T},\beta_{min})$, the decoder may simply subtract $X_{T}\beta_{T}=\sum_{j\in T}X_{j}\beta_{j}$ from $Y$, so that it is left with the modified $n$-vector of observations

By re-ordering indices as need be, we may assume without loss of generality that $T=\{p-k+2,\ldots,p\}$, so that $j^{\star}\in\{1,\ldots,p-k+1\}$. The remaining sub-problem is to determine, given the observations $\widetilde{Y}$, the location of the single non-zero. Note that when we assume that the support of $\beta$ is uniformly chosen over all ${p\choose k}$ possible subsets of size $k$, then given $T$, the location of the remaining non-zero is uniformly distributed over $\{1,\ldots,p-k+1\}$.

In this section, we derive the necessary conditions $f_{1}(p,k,\beta_{min})$ and $f_{2}(p,k,\beta_{min})$ in Theorem 1 for the general class of measurement matrices, by applying Fano’s inequality to bound the probability of decoding error in restricted problems A and B, respectively.

We first perform our analysis of the error probability for a particular instance of the random measurement matrix $X$, and subsequently average over the ensemble of matrices. Let $\Omega$ denote a random subset chosen uniformly at random over all ${p\choose k}$ subsets $S\subset\{1,\ldots,p\}$ of size $k$. The probability of decoding error, for a given $X$, can be lower bounded by Fano’s inequality as

where we have used the fact that $H(\Omega|Y)=H(\Omega)-I(\Omega;Y)=\log{p\choose k}-I(\Omega;Y)$. Thus the problem is reduced to upper bounding the mutual information $I(\Omega;Y)$ between the random subset $\Omega$ and the noisy observations $Y$. Since both $X$ and $\beta_{min}$ are known and fixed, the mutual information can be expanded as

We first bound the entropy of the observation vector $H(Y)$, using the fact that differential entropy is maximized by the Gaussian distribution with a matched variance. More specifically, for a given $X$, let $\Lambda(X)$ denote the covariance matrix of $Y$ conditioned on $X$. (Hence entry $\Lambda_{ii}(X)$ on the diagonal represents the variance of $Y_{i}$.) With this notation, the entropy of $Y$ can be bounded as

With this bound on the mutual information, we now average the probability of error over the ensemble of measurement matrices $X$. Exploiting the concavity of the logarithm and applying Jensen’s inequality, the average probability of error can be bounded as

Given i.i.d. $X_{ij}$ with zero-mean and unit variance, the average covariance is given by

Finally, combining Lemma 1 with equation (23), we obtain that the average probability of error is bounded away from zero if

1.2 Applying Fano to restricted ensemble B

The analysis of restricted ensemble B is completely analogous to the proof for restricted ensemble A, so we will only outline the key steps below. Let $\Omega$ denote a random variable with uniform distribution over the indices $\{1,\ldots,p-k+1\}$. The probability of decoding error, for a given measurement matrix $X$, can be lower bounded by Fano’s inequality as

As before, the key problem of bounding the mutual information $I(\Omega;\widetilde{Y})$ between the random index $\Omega$ and the modified observation vector $\widetilde{Y}$, can be reduced to bounding the entropy $H(\widetilde{Y})$. For each fixed $X$, let $\Lambda(X)$ denote the covariance matrix of $\widetilde{Y}$. Since the differential entropy of $\widetilde{Y}_{i}$ is upper bounded by the entropy of a Gaussian distribution with variance $\Lambda_{ii}(X)$, we obtain the following bound on the mutual information

Applying Jensen’s inequality, we can then bound the average probability of error, averaged over the ensemble of measurement matrices $X$, as

The proof of Lemma 2 below follows the same steps as the derivation of Lemma 1, and is omitted.

Given i.i.d. $X_{ij}$ with zero-mean and unit variance, the average covariance is given by

Finally, combining Lemma 2 with the Fano bound (25), we obtain that the average probability of error is bounded away from zero if

2 Proof of Theorem 2

This section contains proofs of the necessary conditions in Theorem 2 for the $\gamma$-sparsified Gaussian measurement ensemble (10). We proceed as before, applying Fano’s inequality to restricted problems A and B, in order to derive the conditions $g_{1}(p,k,\beta_{min},\gamma)$ and $g_{2}(p,k,\beta_{min},\gamma)$, respectively.

In analyzing the probability of error in restricted ensemble A, the initial steps proceed as in the proof of Theorem 1, first bounding the probability of error for a fixed instance of the measurement matrix $X$, and later averaging over the $\gamma$-sparsified Gaussian ensemble (10). Let $\Omega$ denote a random subset uniformly distributed over the ${p\choose k}$ possible subsets $S\subset\{1,\ldots,p\}$ of size $k$. As before, the probability of decoding error, for each fixed $X$, can be lower bounded by Fano’s inequality as

We can similarly bound the mutual information

using the Gaussian entropy for $W\sim N(0,I_{n\times n})$.

From this point, the key subproblem is to compute the entropy of $Y_{i}=\sum_{j\in S}X_{ij}\beta_{min}+W_{i}$. To characterize the limiting behavior of the random variable $Y_{i}$, note that $Y_{i}$ is distributed according to the density defined as

For each fixed matrix $X$, this density is a mixture of Gaussians with unit variances and means that depend on the values of $\{X_{i1},\ldots,X_{ip}\}$, summed over subsets $S\subset\{1,\ldots,p\}$ with $|S|=k$. At a high-level, our immediate goal is to characterize the entropy $H(\psi_{1})$.

Note that as $X$ varies over the ensemble (10), the sequence $\{\psi_{1}(\cdot\,;X)\}_{p}$, indexed by the signal dimension $p$, is actually a sequence of random densities. As an intermediate step, the following lemma characterizes the average pointwise behavior of this random sequence of densities, and is proven in Appendix B.

is a mixture of Gaussians with binomial weights $L\sim\operatorname{Bin}(k,\gamma)$.

For certain scalings, we can use concentration results for $U$-statistics to prove that $\psi_{1}$ converges uniformly to $\overline{\psi}_{1}$, and from there that $H(\psi_{1})\stackrel{{\scriptstyle p}}{{\rightarrow}}H(\overline{\psi}_{1})$. In general, however, we always have an upper bound, which is sufficient for our purposes. Indeed, since differential entropy $H(\psi_{1})$ is a concave function of $\psi_{1}$, by Jensen’s inequality and Lemma 3, we have

With these ingredients, we conclude that the average error probability of any decoder, averaged over the sparsified Gaussian measurement ensemble, is lower bounded by

Therefore, the probability of decoding error is bounded away from zero if

2.2 Analyzing restricted ensemble B

The analysis of restricted ensemble B mirrors exactly the derivation of restricted ensemble A. Hence we only outline the key steps in this section. Letting $\Omega\sim\operatorname{Uni}\{1,\ldots,p-k+1\}$, we again apply Fano’s inequality to restricted problem B, using the sparse measurement ensemble (10):

In order to upper bound $I(\Omega;\widetilde{Y})$, we need to upper bound the entropy $H(\widetilde{Y})$. The sequence of densities associated with $\widetilde{Y}_{i}$ becomes

Lemma 4 below characterizes the average pointwise behavior of these densities, and follows from the proof of Lemma 3, with $S$ taken to be subsets of the indices $\{1,\ldots,p-k+1\}$ of size $|S|=1$.

is a mixture of Gaussians with Bernoulli weights $B\sim\operatorname{Ber}(\gamma)$.

As before, we can apply Jensen’s inequality to obtain the bound

The necessary condition then follows by the Fano bound on the probability of error.

3 Proof of Corollary 2

In this section, we derive bounds on the expressions $g_{1}(p,k,\beta_{min},\gamma)$ and $g_{2}(p,k,\beta_{min},\gamma)$ in Theorem 2. We begin by noting that the Gaussian mixture distribution $\overline{\psi}_{1}$ defined in (14) is a strict generalization of the distribution $\overline{\psi}_{2}$ defined in (15); moreover, setting the parameter $k=1$ in $\overline{\psi}_{1}$ recovers $\overline{\psi}_{2}$. The variance associated with the mixture distribution $\overline{\psi}_{1}$ is equal to $\sigma_{1}^{2}=1+k\beta_{min}^{2}$, and so the entropy of $\overline{\psi}_{1}$ is always bounded by the entropy of a Gaussian distribution with variance $\sigma_{1}^{2}$, as

Similarly, the mixture distribution $\overline{\psi}_{2}$ has variance equal to $1+\beta_{min}^{2}$, so that the entropy associated with $\overline{\psi}_{2}$ can in general be bounded as

This yields the first set of bounds in (18).

Next, to derive more refined bounds which capture the effects of measurement sparsity, we will make use of the following lemma (which is proven in Appendix C) to bound the entropy associated with the mixture distribution $\overline{\psi}_{1}$:

For the Gaussian mixture distribution $\overline{\psi}_{1}$ defined in (14),

where $L\sim\operatorname{Bin}(k,\gamma)$.

We can further bound the expression in Lemma 5 in three cases, delineated by the quantity $\gamma k$. The proof of the following claim in given in Appendix D.

If $\gamma k=\tau$ for some constant $\tau$, then

Finally, combining Lemmas 5 and 6 with some simple bounds on the entropy of the binomial variate $L$ (given in Appendix E), we obtain the bounds on $g_{1}(p,k,\beta_{min},\gamma)$ in (19) and (20).

We can similarly bound the entropy associated with the Gaussian mixture distribution $\overline{\psi}_{2}$. Since the density $\overline{\psi}_{2}$ is a special case of the density $\overline{\psi}_{1}$ with $k$ set to $1$, we can again apply Lemma 5 to obtain

We have thus obtained the bounds on $g_{2}(p,k,\beta_{min},\gamma)$ in equations (19) and (20).

Discussion

In this paper, we have studied the information-theoretic limits of exact support recovery for general scalings of the parameters $(n,p,k,\beta_{min},\gamma)$. Our first result (Theorem 1) applies generally to measurement matrices with zero-mean and unit variance entries. It strengthens previously known bounds, and combined with known sufficient conditions , yields a sharp characterization of recovering signals with linear sparsity with a linear fraction of observations (Corollary 2). Our second result (Theorem 2) applies to $\gamma$-sparsified Gaussian measurement ensembles, and reveals three different regimes of measurement sparsity, depending on how significantly they impair statistical efficiency. For linear signal sparsity, Theorem 2 is not a sharp result (by comparison to Theorem 1 in the dense case); however, its tightness for sublinear signal sparsity is an interesting open problem. Finally, Theorem 1 implies that the standard Gaussian ensemble is an information-theoretically optimal choice for the measurement matrix: no other zero-mean unit variance distribution can reduce the number of observations necessary for recovery, and in fact the standard Gaussian distribution achieves matching sufficient bounds . This fact raises an interesting open question on the design of other, more computationally friendly, measurement matrices which are optimal in the information-theoretic sense.

The work of WW and KR was supported by NSF grant CCF-0635114. The work of MJW was supported by NSF grants CAREER-CCF-0545862 and DMS-0605165.

Appendix A Proof of Lemma 1

From here, note that there are ${p\choose k}$ possible subsets $S$. For each $S$, a counting argument reveals that there are ${k\choose\lambda}{p-k\choose k-\lambda}$ subsets $U$ of size $k$ which have $\lambda=|S\cap U|$ overlaps with $S$. Thus the scalar multiplicative factor above can be written as

Finally, using a substitution of variables (by setting $\lambda^{\prime}=\lambda-1$) and applying Vandermonde’s identity , we have

Appendix B Proof of Lemma 3

Consider the following sequences of densities,

Appendix C Proof of Lemma 5

Let $Z$ be a random variable distributed according to the density

where $L\sim Bin(k,\gamma)$. To compute the entropy of $Z$, we can expand the following mutual information in two ways, $I(Z;L)=H(Z)-H(Z|L)=H(L)-H(L|Z)$, and obtain

Furthermore, we can bound the conditional entropy of $L$ given $Z$ as $0\leq H(L|Z)\leq H(L)$. This gives upper and lower bounds on the entropy of $Z$ as

Appendix D Proof of Lemma 6

We first derive upper and lower bounds in the case when $\gamma k\leq 1$. We can rewrite the binomial distribution as

Next, we examine the case when $\gamma k=\tau$ for some constant $\tau$. The derivation of the upper bound in the case when $\gamma k\leq 1$ holds for the $\gamma k=\tau$ case as well. The proof of the lower bound follows the same steps as in the $\gamma k\leq 1$ case, except that we stop before applying the last inequality $(a)$.

Finally, we derive bounds in the case when $\gamma k>3$. Since the mean of a $L\sim\operatorname{Bin}(k,\gamma)$ random variable is $\gamma k$, by Jensen’s inequality the following bound always holds,

To derive a matching lower bound, we use the fact that the median of a $\operatorname{Bin}(k,\gamma)$ distribution is one of $\{\lfloor\gamma k\rfloor-1,\lfloor\gamma k\rfloor,\lfloor\gamma k\rfloor+1\}$. This allows us to bound

Appendix E Bounds on binomial entropy

Let $L\sim\operatorname{Bin}(k,\gamma)$. Then

Furthermore, if $\gamma=o\left(\frac{1}{k\log{k}}\right)$, then $kH_{binary}(\gamma)\rightarrow 0$ as $k\rightarrow\infty$.

We can express the binomial variate as $L=\sum_{i=1}^{k}Z_{i}$, where $Z_{i}\sim$ $\operatorname{Ber}$($\gamma$) i.i.d. Since $H(g(Z_{1},\ldots,Z_{k}))\leq H(Z_{1},\ldots,Z_{k})$, we have

Next we find the limit of $kH_{binary}(\gamma)=k\gamma\log\frac{1}{\gamma}+k(1-\gamma)\log\frac{1}{1-\gamma}$. Let $\gamma=\frac{1}{kf(k)}$, and assume that $f(k)\rightarrow\infty$ as $k\rightarrow\infty$. Hence the first term can be written as

and so $k\gamma\log\frac{1}{\gamma}\rightarrow 0$ if $f(k)=\omega(\log k)$. The second term can also be expanded as

If $f(k)\rightarrow\infty$ as $k\rightarrow\infty$, then we have the limits

Let $L\sim\operatorname{Bin}(k,\gamma)$, then

We immediately obtain this bound by applying the differential entropy bound on discrete entropy . ∎

References