Sergio Verdu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Sergio Verdu has a total of 53 co-authors. Here are the top co-authors by number of shared publications:
- Jingbo Liu
Dept. of Electrical Eng Princeton University 08544 NJ
9 shared publications - Paul Cuff
Dept. of Electrical Eng Princeton University 08544 NJ
9 shared publications - Igal Sason
Department of Electrical and Computer Engineering, Technion—Israel Institute of Technology, Haifa 3200003, Israel
7 shared publications - Sanjeev R. Kulkarni
Princeton University
7 shared publications - Shlomo Shamai
Department of Electrical and Computer Engineering, Technion—Israel Institute of Technology, Haifa 3200003, Israel
6 shared publications - Thomas A. Courtade
Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA, USA
4 shared publications
Latest Publications
- Open Access
Improved Bounds on Lossless Source Coding and Guessing Moments via Rényi Measures
This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan's bounds, they are expressed in terms of the Arimoto-R\'enyi conditional entropy. Although Arikan's bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth R\'enyi entropy, for source codes that allow decoding errors.
Open AccessImproved Bounds on Lossless Source Coding and Guessing Moments via Rényi Measures
This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan's bounds, they are expressed in terms of the Arimoto-R\'enyi conditional entropy. Although Arikan's bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth R\'enyi entropy, for source codes that allow decoding errors.
- Open Access
A Forward-Reverse Brascamp-Lieb Inequality: Entropic Duality and Gaussian Optimality
Inspired by the forward and the reverse channels from the image-size characterization problem in network information theory, we introduce a functional inequality that unifies both the Brascamp-Lieb inequality and Barthe’s inequality, which is a reverse form of the Brascamp-Lieb inequality. For Polish spaces, we prove its equivalent entropic formulation using the Legendre-Fenchel duality theory. Capitalizing on the entropic formulation, we elaborate on a “doubling trick” used by Lieb and Geng-Nair to prove the Gaussian optimality in this inequality for the case of Gaussian reference measures.
Open AccessA Forward-Reverse Brascamp-Lieb Inequality: Entropic Duality and Gaussian Optimality
Inspired by the forward and the reverse channels from the image-size characterization problem in network information theory, we introduce a functional inequality that unifies both the Brascamp-Lieb inequality and Barthe’s inequality, which is a reverse form of the Brascamp-Lieb inequality. For Polish spaces, we prove its equivalent entropic formulation using the Legendre-Fenchel duality theory. Capitalizing on the entropic formulation, we elaborate on a “doubling trick” used by Lieb and Geng-Nair to prove the Gaussian optimality in this inequality for the case of Gaussian reference measures.
- Open Access
- 2 April 2018
- Published by MDPI AG in Preprints.org
A Forward-Reverse Brascamp-Lieb Inequality: Entropic Duality and Gaussian Optimality
Inspired by the forward and the reverse channels from the image-size characterization problem in network information theory, we introduce a functional inequality which unifies both the Brascamp-Lieb inequality and Barthe's inequality, which is a reverse form of the Brascamp-Lieb inequality. For Polish spaces, we prove its equivalent entropic formulation using the Legendre-Fenchel duality theory. Capitalizing on the entropic formulation, we elaborate on a "doubling trick" used by Lieb and Geng-Nair to prove the Gaussian optimality in this inequality for the case of Gaussian reference measures.
- 2 April 2018
- Published by MDPI AG in Preprints.org
Open AccessA Forward-Reverse Brascamp-Lieb Inequality: Entropic Duality and Gaussian Optimality
Inspired by the forward and the reverse channels from the image-size characterization problem in network information theory, we introduce a functional inequality which unifies both the Brascamp-Lieb inequality and Barthe's inequality, which is a reverse form of the Brascamp-Lieb inequality. For Polish spaces, we prove its equivalent entropic formulation using the Legendre-Fenchel duality theory. Capitalizing on the entropic formulation, we elaborate on a "doubling trick" used by Lieb and Geng-Nair to prove the Gaussian optimality in this inequality for the case of Gaussian reference measures.
- Open Access
A Coding Theorem for f-Separable Distortion Measures
In this work we relax the usual separability assumption made in rate-distortion literature and propose -separable distortion measures, which are well suited to model non-linear penalties. The main insight behind -separable distortion measures is to define an n-letter distortion measure to be an -mean of single-letter distortions. We prove a rate-distortion coding theorem for stationary ergodic sources with -separable distortion measures, and provide some illustrative examples of the resulting rate-distortion functions. Finally, we discuss connections between -separable distortion measures, and the subadditive distortion measure previously proposed in literature.Open AccessA Coding Theorem for f-Separable Distortion Measures
In this work we relax the usual separability assumption made in rate-distortion literature and propose -separable distortion measures, which are well suited to model non-linear penalties. The main insight behind -separable distortion measures is to define an n-letter distortion measure to be an -mean of single-letter distortions. We prove a rate-distortion coding theorem for stationary ergodic sources with -separable distortion measures, and provide some illustrative examples of the resulting rate-distortion functions. Finally, we discuss connections between -separable distortion measures, and the subadditive distortion measure previously proposed in literature. - 7 February 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (6) , 4323-4346
Improved Bounds on Lossless Source Coding and Guessing Moments via Rényi Measures
This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan’s bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan’s bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors.
- 7 February 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (6) , 4323-4346
Improved Bounds on Lossless Source Coding and Guessing Moments via Rényi Measures
This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan’s bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan’s bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors.
- 6 February 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (5) , 3715-3733
Minimax Rényi Redundancy
The redundancy for universal lossless compression of discrete memoryless sources in Campbell’s setting is characterized as a minimax Rényi divergence, which is shown to be equal to the maximal α-mutual information via a generalized redundancy-capacity theorem. Special attention is placed on the analysis of the asymptotics of minimax Rényi divergence, which is determined up to a term vanishing in blocklength.
- 6 February 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (5) , 3715-3733
Minimax Rényi Redundancy
The redundancy for universal lossless compression of discrete memoryless sources in Campbell’s setting is characterized as a minimax Rényi divergence, which is shown to be equal to the maximal α-mutual information via a generalized redundancy-capacity theorem. Special attention is placed on the analysis of the asymptotics of minimax Rényi divergence, which is determined up to a term vanishing in blocklength.
- Open Access
Minimax Rényi Redundancy
The redundancy for universal lossless compression of discrete memoryless sources in Campbell's setting is characterized as a minimax R\'enyi divergence, which is shown to be equal to the maximal $\alpha$-mutual information via a generalized redundancy-capacity theorem. Special attention is placed on the analysis of the asymptotics of minimax R\'enyi divergence, which is determined up to a term vanishing in blocklength.
Open AccessMinimax Rényi Redundancy
The redundancy for universal lossless compression of discrete memoryless sources in Campbell's setting is characterized as a minimax R\'enyi divergence, which is shown to be equal to the maximal $\alpha$-mutual information via a generalized redundancy-capacity theorem. Special attention is placed on the analysis of the asymptotics of minimax R\'enyi divergence, which is determined up to a term vanishing in blocklength.
- Open Access
Arimoto-Rényi Conditional Entropy and Bayesian $M$-ary Hypothesis Testing
This paper gives upper and lower bounds on the minimum error probability of Bayesian $M$-ary hypothesis testing in terms of the Arimoto-R\'enyi conditional entropy of an arbitrary order $\alpha$. The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy ($\alpha=1$) is demonstrated. In particular, in the case where $M$ is finite, we show how to generalize Fano's inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano's inequality, allowing $M$ to be infinite, a lower bound on the Arimoto-R\'enyi conditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto-R\'enyi conditional entropy for both positive and negative $\alpha$. Furthermore, we give upper bounds on the minimum error probability as functions of the R\'enyi divergence. In the setup of discrete memoryless channels, we analyze the exponentially vanishing decay of the Arimoto-R\'enyi conditional entropy of the transmitted codeword given the channel output when averaged over a random coding ensemble.Open AccessArimoto-Rényi Conditional Entropy and Bayesian $M$-ary Hypothesis Testing
This paper gives upper and lower bounds on the minimum error probability of Bayesian $M$-ary hypothesis testing in terms of the Arimoto-R\'enyi conditional entropy of an arbitrary order $\alpha$. The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy ($\alpha=1$) is demonstrated. In particular, in the case where $M$ is finite, we show how to generalize Fano's inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano's inequality, allowing $M$ to be infinite, a lower bound on the Arimoto-R\'enyi conditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto-R\'enyi conditional entropy for both positive and negative $\alpha$. Furthermore, we give upper bounds on the minimum error probability as functions of the R\'enyi divergence. In the setup of discrete memoryless channels, we analyze the exponentially vanishing decay of the Arimoto-R\'enyi conditional entropy of the transmitted codeword given the channel output when averaged over a random coding ensemble. - Open Access
Information-Theoretic Perspectives on Brascamp-Lieb Inequality and Its Reverse
We introduce an inequality which may be viewed as a generalization of both the Brascamp-Lieb inequality and its reverse (Barthe's inequality), and prove its information-theoretic (i.e.\ entropic) formulation. This result leads to a unified approach to functional inequalities such as the variational formula of R\'enyi entropy, hypercontractivity and its reverse, strong data processing inequalities, and transportation-cost inequalities, whose utility in the proofs of various coding theorems has gained growing popularity recently. We show that our information-theoretic setting is convenient for proving properties such as data processing, tensorization, convexity (Riesz-Thorin interpolation) and Gaussian optimality. In particular, we elaborate on a "doubling trick" used by Lieb and Geng-Nair to prove several results on Gaussian optimality. Several applications are discussed, including a generalization of the Brascamp-Lieb inequality involving Gaussian random transformations, the determination of Wyner's common information of vector Gaussian sources, and the achievable rate region of certain key generation problems in the case of vector Gaussian sources.
Open AccessInformation-Theoretic Perspectives on Brascamp-Lieb Inequality and Its Reverse
We introduce an inequality which may be viewed as a generalization of both the Brascamp-Lieb inequality and its reverse (Barthe's inequality), and prove its information-theoretic (i.e.\ entropic) formulation. This result leads to a unified approach to functional inequalities such as the variational formula of R\'enyi entropy, hypercontractivity and its reverse, strong data processing inequalities, and transportation-cost inequalities, whose utility in the proofs of various coding theorems has gained growing popularity recently. We show that our information-theoretic setting is convenient for proving properties such as data processing, tensorization, convexity (Riesz-Thorin interpolation) and Gaussian optimality. In particular, we elaborate on a "doubling trick" used by Lieb and Geng-Nair to prove several results on Gaussian optimality. Several applications are discussed, including a generalization of the Brascamp-Lieb inequality involving Gaussian random transformations, the determination of Wyner's common information of vector Gaussian sources, and the achievable rate region of certain key generation problems in the case of vector Gaussian sources.
- Open Access
- 28 September 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (1) , 4-25
Arimoto–Rényi Conditional Entropy and Bayesian $M$ -Ary Hypothesis TestingThis paper gives upper and lower bounds on the minimum error probability of Bayesian M-ary hypothesis testing in terms of the Arimoto-Rényi conditional entropy of an arbitrary order α. The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy ( α= 1) is demonstrated. In particular, in the case where M is finite, we show how to generalize Fano’s inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano’s inequality, allowing M to be infinite, a lower bound on the Arimoto-Rényi cconditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto-Rényi conditional entropy for both positive and negative α. Furthermore, we give upper bounds on the minimum error probability as functions of the Rényi divergence. In the setup of discrete memoryless channels, we analyze the exponentially vanishing decay of the Arimoto- Rényi conditional entropy of the transmitted codeword given the channel output when averaged over a random-coding ensemble.
- 28 September 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (1) , 4-25
Open AccessArimoto–Rényi Conditional Entropy and Bayesian $M$ -Ary Hypothesis TestingThis paper gives upper and lower bounds on the minimum error probability of Bayesian M-ary hypothesis testing in terms of the Arimoto-Rényi conditional entropy of an arbitrary order α. The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy ( α= 1) is demonstrated. In particular, in the case where M is finite, we show how to generalize Fano’s inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano’s inequality, allowing M to be infinite, a lower bound on the Arimoto-Rényi cconditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto-Rényi conditional entropy for both positive and negative α. Furthermore, we give upper bounds on the minimum error probability as functions of the Rényi divergence. In the setup of discrete memoryless channels, we analyze the exponentially vanishing decay of the Arimoto- Rényi conditional entropy of the transmitted codeword given the channel output when averaged over a random-coding ensemble.