BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Igal Sason

Igal Sason appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITmath.PRmath.STStatistics TheoryMachine Learningmath.CO

Catalog footprint

What is connected

29works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

29 published item(s)

preprint2022arXiv

Information Inequalities via Submodularity and a Problem in Extremal Graph Theory

The present paper offers, in its first part, a unified approach for the derivation of families of inequalities for set functions which satisfy sub/supermodularity properties. It applies this approach for the derivation of information inequalities with Shannon information measures. Connections of the considered approach to a generalized version of Shearer's lemma, and other related results in the literature are considered. Some of the derived information inequalities are new, and also known results (such as a generalized version of Han's inequality) are reproduced in a simple and unified way. In its second part, this paper applies the generalized Han's inequality to analyze a problem in extremal graph theory. This problem is motivated and analyzed from the perspective of information theory, and the analysis leads to generalized and refined bounds. The two parts of this paper are meant to be independently accessible to the reader.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Integral Representation of the Logarithmic Function with Applications in Information Theory

We explore a well-known integral representation of the logarithmic function, and demonstrate its usefulness in obtaining compact, easily-computable exact formulas for quantities that involve expectations and higher moments of the logarithm of a positive random variable (or the logarithm of a sum of positive random variables). The integral representation of the logarithm is proved useful in a variety of information-theoretic applications, including universal lossless data compression, entropy and differential entropy evaluations, and the calculation of the ergodic capacity of the single-input, multiple-output (SIMO) Gaussian channel with random parameters (known to both transmitter and receiver). This integral representation and its variants are anticipated to serve as a useful tool in additional applications, as a rigorous alternative to the popular (but non-rigorous) replica method (at least in some situations).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Relations Between the Relative entropy and $χ^2$-Divergence, Generalizations and Applications

The relative entropy and chi-squared divergence are fundamental divergence measures in information theory and statistics. This paper is focused on a study of integral relations between the two divergences, the implications of these relations, their information-theoretic applications, and some generalizations pertaining to the rich class of $f$-divergences. Applications that are studied in this paper refer to lossless compression, the method of types and large deviations, strong~data-processing inequalities, bounds on contraction coefficients and maximal correlation, and the convergence rate to stationarity of a type of discrete-time Markov chains.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Some Useful Integral Representations for Information-Theoretic Analyses

This work is an extension of our earlier article, where a well-known integral representation of the logarithmic function was explored, and was accompanied with demonstrations of its usefulness in obtaining compact, easily-calculable, exact formulas for quantities that involve expectations of the logarithm of a positive random variable. Here, in the same spirit, we derive an exact integral representation (in one or two dimensions) of the moment of a nonnegative random variable, or the sum of such independent random variables, where the moment order is a general positive noninteger real (also known as fractional moments). The proposed formula is applied to a variety of examples with an information-theoretic motivation, and it is shown how it facilitates their numerical evaluations. In particular, when applied to the calculation of a moment of the sum of a large number, $n$, of nonnegative random variables, it is clear that integration over one or two dimensions, as suggested by our proposed integral representation, is significantly easier than the alternative of integrating over $n$ dimensions, as needed in the direct calculation of the desired moment.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

On Data-Processing and Majorization Inequalities for $f$-Divergences with Applications

This paper is focused on derivations of data-processing and majorization inequalities for $f$-divergences, and their applications in information theory and statistics. For the accessibility of the material, the main results are first introduced without proofs, followed by exemplifications of the theorems with further related analytical results, interpretations, and information-theoretic applications. One application refers to the performance analysis of list decoding with either fixed or variable list sizes; some earlier bounds on the list decoding error probability are reproduced in a unified way, and new bounds are obtained and exemplified numerically. Another application is related to a study of the quality of approximating a probability mass function, induced by the leaves of a Tunstall tree, by an equiprobable distribution. The compression rates of finite-length Tunstall codes are further analyzed for asserting their closeness to the Shannon entropy of a memoryless and stationary discrete source. Almost all the analysis is relegated to the appendices, which form a major part of this manuscript.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

$f$-divergence Inequalities

This paper develops systematic approaches to obtain $f$-divergence inequalities, dealing with pairs of probability measures defined on arbitrary alphabets. Functional domination is one such approach, where special emphasis is placed on finding the best possible constant upper bounding a ratio of $f$-divergences. Another approach used for the derivation of bounds among $f$-divergences relies on moment inequalities and the logarithmic-convexity property, which results in tight bounds on the relative entropy and Bhattacharyya distance in terms of $χ^2$ divergences. A rich variety of bounds are shown to hold under boundedness assumptions on the relative information. Special attention is devoted to the total variation distance and its relation to the relative information and relative entropy, including "reverse Pinsker inequalities," as well as on the $E_γ$ divergence, which generalizes the total variation distance. Pinsker's inequality is extended for this type of $f$-divergence, a result which leads to an inequality linking the relative entropy and relative information spectrum. Integral expressions of the Rényi divergence in terms of the relative information spectrum are derived, leading to bounds on the Rényi divergence in terms of either the variational distance or relative entropy.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

$f$-Divergence Inequalities via Functional Domination

This paper considers derivation of $f$-divergence inequalities via the approach of functional domination. Bounds on an $f$-divergence based on one or several other $f$-divergences are introduced, dealing with pairs of probability measures defined on arbitrary alphabets. In addition, a variety of bounds are shown to hold under boundedness assumptions on the relative information. The journal paper, which includes more approaches for the derivation of f-divergence inequalities and proofs, is available on the arXiv at https://arxiv.org/abs/1508.00335, and it has been published in the IEEE Trans. on Information Theory, vol. 62, no. 11, pp. 5973-6006, November 2016.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Renyi Entropy Power Inequalities

This paper gives improved Rényi entropy power inequalities (R-EPIs). Consider a sum $S_n = \sum_{k=1}^n X_k$ of $n$ independent continuous random vectors taking values on $\mathbb{R}^d$, and let $α\in [1, \infty]$. An R-EPI provides a lower bound on the order-$α$ Rényi entropy power of $S_n$ that, up to a multiplicative constant (which may depend in general on $n, α, d$), is equal to the sum of the order-$α$ Rényi entropy powers of the $n$ random vectors $\{X_k\}_{k=1}^n$. For $α=1$, the R-EPI coincides with the well-known entropy power inequality by Shannon. The first improved R-EPI is obtained by tightening the recent R-EPI by Bobkov and Chistyakov which relies on the sharpened Young's inequality. A further improvement of the R-EPI also relies on convex optimization and results on rank-one modification of a real-valued diagonal matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Projection Theorems for the Rényi Divergence on $α$-Convex Sets

This paper studies forward and reverse projections for the Rényi divergence of order $α\in (0, \infty)$ on $α$-convex sets. The forward projection on such a set is motivated by some works of Tsallis {\em et al.} in statistical physics, and the reverse projection is motivated by robust statistics. In a recent work, van Erven and Harremoës proved a Pythagorean inequality for Rényi divergences on $α$-convex sets under the assumption that the forward projection exists. Continuing this study, a sufficient condition for the existence of forward projection is proved for probability measures on a general alphabet. For $α\in (1, \infty)$, the proof relies on a new Apollonius theorem for the Hellinger divergence, and for $α\in (0,1)$, the proof relies on the Banach-Alaoglu theorem from functional analysis. Further projection results are then obtained in the finite alphabet setting. These include a projection theorem on a specific $α$-convex set, which is termed an {\em $α$-linear family}, generalizing a result by Csiszár for $α\neq 1$. The solution to this problem yields a parametric family of probability measures which turns out to be an extension of the exponential family, and it is termed an {\em $α$-exponential family}. An orthogonality relationship between the $α$-exponential and $α$-linear families is established, and it is used to turn the reverse projection on an $α$-exponential family into a forward projection on a $α$-linear family. This paper also proves a convergence result of an iterative procedure used to calculate the forward projection on an intersection of a finite number of $α$-linear families.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Concentration of Measure Inequalities and Their Communication and Information-Theoretic Applications

During the last two decades, concentration of measure has been a subject of various exciting developments in convex geometry, functional analysis, statistical physics, high-dimensional statistics, probability theory, information theory, communications and coding theory, computer science, and learning theory. One common theme which emerges in these fields is probabilistic stability: complicated, nonlinear functions of a large number of independent or weakly dependent random variables often tend to concentrate sharply around their expected values. Information theory plays a key role in the derivation of concentration inequalities. Indeed, both the entropy method and the approach based on transportation-cost inequalities are two major information-theoretic paths toward proving concentration. This brief survey is based on a recent monograph of the authors in the Foundations and Trends in Communications and Information Theory (online available at http://arxiv.org/pdf/1212.4663v8.pdf), and a tutorial given by the authors at ISIT 2015. It introduces information theorists to three main techniques for deriving concentration inequalities: the martingale method, the entropy method, and the transportation-cost inequalities. Some applications in information theory, communications, and coding theory are used to illustrate the main ideas.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Concentration of Measure Inequalities in Information Theory, Communications and Coding (Second Edition)

During the last two decades, concentration inequalities have been the subject of exciting developments in various areas, including convex geometry, functional analysis, statistical physics, high-dimensional statistics, pure and applied probability theory, information theory, theoretical computer science, and learning theory. This monograph focuses on some of the key modern mathematical tools that are used for the derivation of concentration inequalities, on their links to information theory, and on their various applications to communications and coding. In addition to being a survey, this monograph also includes various new recent results derived by the authors. The first part of the monograph introduces classical concentration inequalities for martingales, as well as some recent refinements and extensions. The power and versatility of the martingale approach is exemplified in the context of codes defined on graphs and iterative decoding algorithms, as well as codes for wireless communication. The second part of the monograph introduces the entropy method, an information-theoretic technique for deriving concentration inequalities. The basic ingredients of the entropy method are discussed first in the context of logarithmic Sobolev inequalities, which underlie the so-called functional approach to concentration of measure, and then from a complementary information-theoretic viewpoint based on transportation-cost inequalities and probability in metric spaces. Some representative results on concentration for dependent random variables are briefly summarized, with emphasis on their connections to the entropy method. Finally, we discuss several applications of the entropy method to problems in communications and coding, including strong converses, empirical distributions of good channel codes, and an information-theoretic converse for concentration of measure.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Reverse Pinsker Inequalities

New upper bounds on the relative entropy are derived as a function of the total variation distance. One bound refines an inequality by Verdú for general probability measures. A second bound improves the tightness of an inequality by Csiszár and Talata for arbitrary probability measures that are defined on a common finite set. The latter result is further extended, for probability measures on a finite set, leading to an upper bound on the Rényi divergence of an arbitrary non-negative order (including $\infty$) as a function of the total variation distance. Another lower bound by Verdú on the total variation distance, expressed in terms of the distribution of the relative information, is tightened and it is attained under some conditions. The effect of these improvements is exemplified.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Corner Points of the Capacity Region of a Two-User Gaussian Interference Channel

This work considers the corner points of the capacity region of a two-user Gaussian interference channel (GIC). In a two-user GIC, the rate pairs where one user transmits its data at the single-user capacity (without interference), and the other at the largest rate for which reliable communication is still possible are called corner points. This paper relies on existing outer bounds on the capacity region of a two-user GIC that are used to derive informative bounds on the corner points of the capacity region. The new bounds refer to a weak two-user GIC (i.e., when both cross-link gains in standard form are positive and below 1), and a refinement of these bounds is obtained for the case where the transmission rate of one user is within $\varepsilon > 0$ of the single-user capacity. The bounds on the corner points are asymptotically tight as the transmitted powers tend to infinity, and they are also useful for the case of moderate SNR and INR. Upper and lower bounds on the gap (denoted by $Δ$) between the sum-rate and the maximal achievable total rate at the two corner points are derived. This is followed by an asymptotic analysis analogous to the study of the generalized degrees of freedom (where the SNR and INR scalings are coupled such that $\frac{\log(\text{INR})}{\log(\text{SNR})} = α\geq 0$), leading to an asymptotic characterization of this gap which is exact for the whole range of $α$. The upper and lower bounds on $Δ$ are asymptotically tight in the sense that they achieve the exact asymptotic characterization. Improved bounds on $Δ$ are derived for finite SNR and INR, and their improved tightness is exemplified numerically.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Renyi Divergence, Joint Range of Relative Entropies, and a Channel Coding Theorem

This paper starts by considering the minimization of the Renyi divergence subject to a constraint on the total variation distance. Based on the solution of this optimization problem, the exact locus of the points $\bigl( D(Q\|P_1), D(Q\|P_2) \bigr)$ is determined when $P_1, P_2, Q$ are arbitrary probability measures which are mutually absolutely continuous, and the total variation distance between $P_1$ and $P_2$ is not below a given value. It is further shown that all the points of this convex region are attained by probability measures which are defined on a binary alphabet. This characterization yields a geometric interpretation of the minimal Chernoff information subject to a constraint on the total variation distance. This paper also derives an exponential upper bound on the performance of binary linear block codes (or code ensembles) under maximum-likelihood decoding. Its derivation relies on the Gallager bounding technique, and it reproduces the Shulman-Feder bound as a special case. The bound is expressed in terms of the Renyi divergence from the normalized distance spectrum of the code (or the average distance spectrum of the ensemble) to the binomially distributed distance spectrum of the capacity-achieving ensemble of random block codes. This exponential bound provides a quantitative measure of the degradation in performance of binary linear block codes (or code ensembles) as a function of the deviation of their distance spectra from the binomial distribution. An efficient use of this bound is considered.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Universal Properties of Capacity-Approaching LDPC Ensembles

This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/ bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any sub-optimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Tight Bounds for Symmetric Divergence Measures and a New Inequality Relating $f$-Divergences

Tight bounds for several symmetric divergence measures are introduced, given in terms of the total variation distance. Each of these bounds is attained by a pair of 2 or 3-element probability distributions. An application of these bounds for lossless source coding is provided, refining and improving a certain bound by Csiszár. A new inequality relating $f$-divergences is derived, and its use is exemplified. The last section of this conference paper is not included in the recent journal paper that was published in the February 2015 issue of the IEEE Trans. on Information Theory (see arXiv:1403.7164), as well as some new paragraphs throughout the paper which are linked to new references.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Tight Bounds for Symmetric Divergence Measures and a Refined Bound for Lossless Source Coding

Tight bounds for several symmetric divergence measures are derived in terms of the total variation distance. It is shown that each of these bounds is attained by a pair of 2 or 3-element probability distributions. An application of these bounds for lossless source coding is provided, refining and improving a certain bound by Csiszár. Another application of these bounds has been recently introduced by Yardi. et al. for channel-code detection.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Upper Bounds on the Relative Entropy and Rényi Divergence as a Function of Total Variation Distance for Finite Alphabets

A new upper bound on the relative entropy is derived as a function of the total variation distance for probability measures defined on a common finite alphabet. The bound improves a previously reported bound by Csiszár and Talata. It is further extended to an upper bound on the Rényi divergence of an arbitrary non-negative order (including $\infty$) as a function of the total variation distance.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Achieving Marton's Region for Broadcast Channels Using Polar Codes

This paper presents polar coding schemes for the 2-user discrete memoryless broadcast channel (DM-BC) which achieve Marton's region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of 2-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as the binning strategy. By combining these two schemes, we obtain Marton's region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a super-polynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. In order to align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and the channel outputs. To remove these constraints, we consider the transmission of $k$ blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this work are quite general, and they can be adopted to many other multi-terminal scenarios whenever there polar indices need to be aligned.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Information-Theoretic Perspective of the Poisson Approximation via the Chen-Stein Method

The first part of this work considers the entropy of the sum of (possibly dependent and non-identically distributed) Bernoulli random variables. Upper bounds on the error that follows from an approximation of this entropy by the entropy of a Poisson random variable with the same mean are derived via the Chen-Stein method. The second part of this work derives new lower bounds on the total variation (TV) distance and relative entropy between the distribution of the sum of independent Bernoulli random variables and the Poisson distribution. The starting point of the derivation of the new bounds in the second part of this work is an introduction of a new lower bound on the total variation distance, whose derivation generalizes and refines the analysis by Barbour and Hall (1984), based on the Chen-Stein method for the Poisson approximation. A new lower bound on the relative entropy between these two distributions is introduced, and this lower bound is compared to a previously reported upper bound on the relative entropy by Kontoyiannis et al. (2005). The derivation of the new lower bound on the relative entropy follows from the new lower bound on the total variation distance, combined with a distribution-dependent refinement of Pinsker's inequality by Ordentlich and Weinberger (2005). Upper and lower bounds on the Bhattacharyya parameter, Chernoff information and Hellinger distance between the distribution of the sum of independent Bernoulli random variables and the Poisson distribution with the same mean are derived as well via some relations between these quantities with the total variation distance and the relative entropy. The analysis in this work combines elements of information theory with the Chen-Stein method for the Poisson approximation. The resulting bounds are easy to compute, and their applicability is exemplified.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Entropy Bounds for Discrete Random Variables via Maximal Coupling

This paper derives new bounds on the difference of the entropies of two discrete random variables in terms of the local and total variation distances between their probability mass functions. The derivation of the bounds relies on maximal coupling, and they apply to discrete random variables which are defined over finite or countably infinite alphabets. Loosened versions of these bounds are demonstrated to reproduce some previously reported results. The use of the new bounds is exemplified for the Poisson approximation, where bounds on the local and total variation distances follow from Stein's method.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improved Lower Bounds on the Total Variation Distance for the Poisson Approximation

New lower bounds on the total variation distance between the distribution of a sum of independent Bernoulli random variables and the Poisson random variable (with the same mean) are derived via the Chen-Stein method. The new bounds rely on a non-trivial modification of the analysis by Barbour and Hall (1984) which surprisingly gives a significant improvement. A use of the new lower bounds is addressed.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Moderate Deviations Analysis of Binary Hypothesis Testing

This paper is focused on the moderate-deviations analysis of binary hypothesis testing. The analysis relies on a concentration inequality for discrete-parameter martingales with bounded jumps, where this inequality forms a refinement to the Azuma-Hoeffding inequality. Relations of the analysis to the moderate deviations principle for i.i.d. random variables and to the relative entropy are considered.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Entropy of Sums of Bernoulli Random Variables via the Chen-Stein Method

This paper considers the entropy of the sum of (possibly dependent and non-identically distributed) Bernoulli random variables. Upper bounds on the error that follows from an approximation of this entropy by the entropy of a Poisson random variable with the same mean are derived. The derivation of these bounds combines elements of information theory with the Chen-Stein method for Poisson approximation. The resulting bounds are easy to compute, and their applicability is exemplified. This conference paper presents in part the first half of the paper entitled "An information-theoretic perspective of the Poisson approximation via the Chen-Stein method" (see:arxiv:1206.6811). A generalization of the bounds that considers the accuracy of the Poisson approximation for the entropy of a sum of non-negative, integer-valued and bounded random variables is introduced in the full paper. It also derives lower bounds on the total variation distance, relative entropy and other measures that are not considered in this conference paper.

0 citations0 reviewsNo code linkedOpen access