Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1707.00810

Rényi Resolvability and Its Applications to the Wiretap Channel

Lei Yu, Vincent Y. F. Tan

Published Jul 4, 2017• 0 citations
arXivHTMLPDF

Abstract

The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in $[0,2]\cup\{\infty\}$) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to $1$ as well as (lower and upper) bounds for the case when the same parameter is smaller than $1$. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than~$1$, consistent with the traditional case where the Rényi parameter is equal to~$1$, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than $1$ the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d.\ random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence.

DOI
10.48550/arxiv.1707.00810

Related papers

Rényi Resolvability and Its Applications to the Wiretap Channel

Lei Yu, Vincent Y. F. Tan

The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in[0, 2] U {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.

IEEE Transactions on Information Theory•Dec 7, 2018•42 citations

$E_{\gamma}$-Resolvability

Jingbo Liu, Paul Cuff, Sergio Verdú

The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper, we study Eγ-resolvability, in which total variation is replaced by the more general Eγdistance. A general one-shot achievability bound for the precision of such an approximation is developed. Let QX|Ube a random transformation, n be an integer, and E ∈ (0, +∞). We show that in the asymptotic setting where γ = exp(nE), a (nonnegative) randomness rate above inf QU:D(QXIIπX)≤E{D(QXIIπX) + I(QU, QX|U) - E} is sufficient to approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX, and is also necessary in the case of finite U and X . In particular, a randomness rate of inf QUI(QU, QX|U) - E is always sufficient. We also study the convergence of the approximation error under the high-probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating Eγand other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive: 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d. setting; 2) a one-shot version of the mutual covering lemma; and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.

arXiv:1511.07829•IEEE Transactions on Information Theory•Jan 1, 2016•22 citations

Wyner's Common Information under Rényi Divergence Measures

Lei Yu, Vincent Y. F. Tan

We study a generalized version of Wyner's common information problem (also coined the distributed source simulation problem). The original common information problem consists in understanding the minimum rate of the common input to independent processors to generate an approximation of a joint distribution when the distance measure used to quantify the discrepancy between the synthesized and target distributions is the normalized relative entropy. Our generalization involves changing the distance measure to the unnormalized and normalized Rényi divergences of order $α=1+s\in[0,2]$. We show that the minimum rate needed to ensure the Rényi divergences between the distribution induced by a code and the target distribution vanishes remains the same as the one in Wyner's setting, except when the order $α=1+s=0$. This implies that Wyner's common information is rather robust to the choice of distance measure employed. As a byproduct of the proofs used to the establish the above results, the exponential strong converse for the common information problem under the total variation distance measure is established.

arXiv:1709.02168•Sep 7, 2017•0 citations

Large Deviation Analysis for the Reverse Shannon Theorem

Shi-Bing Li, Ke Li, Lei Yu

We consider the problem of simulating a noisy channel using noiseless channels with unlimited shared randomness. This can be interpreted as the reverse problem of Shannon’s noisy channel coding theorem. In contrast to previous works, we employ Rényi divergence (with the parameter α ∈ [0,∞]) to measure the level of approximation, and we obtain the reverse Shannon theorem under this measure, which characterizes the Rényi simulation rate, the minimum communication rate required for the Rényi divergence vanishing asymptotically. Our derivation is done by a precise large-deviation analysis. When the communication rate is above the Rényi simulation rate, we provide a complete characterization of the convergence exponent for the Rényi divergence, called the reliability function. When the communication rate is below the Rényi simulation rate, we determine the linear increasing rate for the Rényi divergence, which implies the strong converse exponent for the order-α fidelity.

arXiv:2410.07984•IEEE Transactions on Information Theory•May 25, 2026•1 citation

A Note on Channel Resolvability Rate with Subclass of $f$-Divergences

Ryo Nomura, Hideki Yagi

This paper investigates the channel resolvability problem in a general setting. Previous studies have primarily focused on the channel resolvability problem with respect to the variational distance. In this study, we extend this analysis to a subclass of$f$-divergences. The$f$-divergence is a general non-negative measure between two probability distributions, encompassing several important measures including the variational distance, KL divergence, and Hellinger distance. Given this generality, analyzing the channel resolvability problem with respect to$f$-divergence provides valuable insights. We derive both upper and lower bounds for the optimal achievable rate for a specific subclass of$f$-divergence. These bounds enable us to determine the exact$\varepsilon$-optimal rate for the variational distance, while also establishing the exact 0 -optimal rate for various$f$-divergences such as the Hellinger distance, JensenShannon divergence, and other measures within this framework.

Asia Pacific Workshop on Data Science and Information Theory (APWDSIT)•Oct 20, 2025•0 citations

Variable-Length Resolvability for General Sources and Channels

Hideki Yagi, Te Sun Han

We introduce the problem of variable-length (VL) source resolvability, in which a given target probability distribution is approximated by encoding a VL uniform random number, and the asymptotically minimum average length rate of the uniform random number, called the VL resolvability, is investigated. We first analyze the VL resolvability with the variational distance as an approximation measure. Next, we investigate the case under the divergence as an approximation measure. When the asymptotically exact approximation is required, it is shown that the resolvability under two kinds of approximation measures coincides. We then extend the analysis to the case of channel resolvability, where the target distribution is the output distribution via a general channel due to a fixed general source as an input. The obtained characterization of channel resolvability is fully general in the sense that, when the channel is just an identity mapping, it reduces to general formulas for source resolvability. We also analyze the second-order VL resolvability.

arXiv:1701.08712•Entropy•Oct 19, 2023•7 citations
The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in [0,2]∪{∞}[0,2]\cup\{\infty\}[0,2]∪{∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 111 as well as (lower and upper) bounds for the case when the same parameter is smaller than 111. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than~111, consistent with the traditional case where the Rényi parameter is equal to~111, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 111 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d.\ random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence.
The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in[0, 2] U {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.
EγE_{\gamma}Eγ​-Resolvability
The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper, we study Eγ-resolvability, in which total variation is replaced by the more general Eγdistance. A general one-shot achievability bound for the precision of such an approximation is developed. Let QX|Ube a random transformation, n be an integer, and E ∈ (0, +∞). We show that in the asymptotic setting where γ = exp(nE), a (nonnegative) randomness rate above inf QU:D(QXIIπX)≤E{D(QXIIπX) + I(QU, QX|U) - E} is sufficient to approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX, and is also necessary in the case of finite U and X . In particular, a randomness rate of inf QUI(QU, QX|U) - E is always sufficient. We also study the convergence of the approximation error under the high-probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating Eγand other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive: 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d. setting; 2) a one-shot version of the mutual covering lemma; and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.
We study a generalized version of Wyner's common information problem (also coined the distributed source simulation problem). The original common information problem consists in understanding the minimum rate of the common input to independent processors to generate an approximation of a joint distribution when the distance measure used to quantify the discrepancy between the synthesized and target distributions is the normalized relative entropy. Our generalization involves changing the distance measure to the unnormalized and normalized Rényi divergences of order α=1+s∈[0,2]α=1+s\in[0,2]α=1+s∈[0,2]. We show that the minimum rate needed to ensure the Rényi divergences between the distribution induced by a code and the target distribution vanishes remains the same as the one in Wyner's setting, except when the order α=1+s=0α=1+s=0α=1+s=0. This implies that Wyner's common information is rather robust to the choice of distance measure employed. As a byproduct of the proofs used to the establish the above results, the exponential strong converse for the common information problem under the total variation distance measure is established.
We consider the problem of simulating a noisy channel using noiseless channels with unlimited shared randomness. This can be interpreted as the reverse problem of Shannon’s noisy channel coding theorem. In contrast to previous works, we employ Rényi divergence (with the parameter α ∈ [0,∞]) to measure the level of approximation, and we obtain the reverse Shannon theorem under this measure, which characterizes the Rényi simulation rate, the minimum communication rate required for the Rényi divergence vanishing asymptotically. Our derivation is done by a precise large-deviation analysis. When the communication rate is above the Rényi simulation rate, we provide a complete characterization of the convergence exponent for the Rényi divergence, called the reliability function. When the communication rate is below the Rényi simulation rate, we determine the linear increasing rate for the Rényi divergence, which implies the strong converse exponent for the order-α fidelity.
A Note on Channel Resolvability Rate with Subclass of fff-Divergences
This paper investigates the channel resolvability problem in a general setting. Previous studies have primarily focused on the channel resolvability problem with respect to the variational distance. In this study, we extend this analysis to a subclass offff-divergences. Thefff-divergence is a general non-negative measure between two probability distributions, encompassing several important measures including the variational distance, KL divergence, and Hellinger distance. Given this generality, analyzing the channel resolvability problem with respect tofff-divergence provides valuable insights. We derive both upper and lower bounds for the optimal achievable rate for a specific subclass offff-divergence. These bounds enable us to determine the exactε\varepsilonε-optimal rate for the variational distance, while also establishing the exact 0 -optimal rate for variousfff-divergences such as the Hellinger distance, JensenShannon divergence, and other measures within this framework.
We introduce the problem of variable-length (VL) source resolvability, in which a given target probability distribution is approximated by encoding a VL uniform random number, and the asymptotically minimum average length rate of the uniform random number, called the VL resolvability, is investigated. We first analyze the VL resolvability with the variational distance as an approximation measure. Next, we investigate the case under the divergence as an approximation measure. When the asymptotically exact approximation is required, it is shown that the resolvability under two kinds of approximation measures coincides. We then extend the analysis to the case of channel resolvability, where the target distribution is the output distribution via a general channel due to a fixed general source as an input. The obtained characterization of channel resolvability is fully general in the sense that, when the channel is just an identity mapping, it reduces to general formulas for source resolvability. We also analyze the second-order VL resolvability.