Source author record

Yuta Sakai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT

Catalog footprint

Research overview

12works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Asymptotic Expansions of Smooth Rényi Entropies and Their Applications

This study considers the unconditional smooth Rényi entropy, the smooth conditional Rényi entropy proposed by Kuzuoka [\emph{IEEE Trans.\ Inf.\ Theory}, vol.~66, no.~3, pp.~1674--1690, 2020], and a new quantity which we term the conditional smooth Rényi entropy. In particular, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Using these smooth Rényi entropies, we establish one-shot coding theorems of several information-theoretic problems: Campbell's source coding, guessing problems, and task encoding problems, all allowing errors. In each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information of the source. Applying our asymptotic expansions to the derived one-shot coding theorems, we derive various asymptotic fundamental limits for these problems when their error probabilities are allowed to be non-vanishing. We show that, in non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors (for variable-length conditional source coding allowing errors) in which the first-order terms are identical but the second-order terms are different under these criteria.

preprint2020arXiv

Generalizations of Fano's Inequality for Conditional Information Measures via Majorization Theory

Fano's inequality is one of the most elementary, ubiquitous, and important tools in information theory. Using majorization theory, Fano's inequality is generalized to a broad class of information measures, which contains those of Shannon and Rényi. When specialized to these measures, it recovers and generalizes the classical inequalities. Key to the derivation is the construction of an appropriate conditional distribution inducing a desired marginal distribution on a countably infinite alphabet. The construction is based on the infinite-dimensional version of Birkhoff's theorem proven by Révész [Acta Math. Hungar. 1962, 3, 188{\textendash}198], and the constraint of maintaining a desired marginal distribution is similar to coupling in probability theory. Using our Fano-type inequalities for Shannon's and Rényi's information measures, we also investigate the asymptotic behavior of the sequence of Shannon's and Rényi's equivocations when the error probabilities vanish. This asymptotic behavior provides a novel characterization of the asymptotic equipartition property (AEP) via Fano's inequality.

preprint2020arXiv

Modular Arithmetic Erasure Channels and Their Multilevel Channel Polarization

This study proposes \emph{modular arithmetic erasure channels} (MAECs), a novel class of erasure-like channels with an input alphabet that need not be binary. This class contains the binary erasure channel (BEC) and some other known erasure-like channels as special cases. For MAECs, we provide recursive formulas of Arıkan-like polar transform to simulate channel polarization. In other words, we show that the synthetic channels of MAECs are equivalent to other MAECs. This is a generalization of well-known recursive formulas of the polar transform for BECs. Using our recursive formulas, we also show that a recursive application of the polar transform for MAECs results in \emph{multilevel channel polarization,} which is an asymptotic phenomenon that is characteristic of non-binary polar codes. Specifically, we establish a method to calculate the limiting proportions of the partially noiseless and noisy channels that are generated as a result of multilevel channel polarization for MAECs. In the particular case of MAECs, this calculation method solves an open problem posed by Nasser (2017) in the study of non-binary polar codes.

preprint2020arXiv

Second- and Third-Order Asymptotics of the Continuous-Time Poisson Channel

The paper derives the optimal second-order coding rate for the continuous-time Poisson channel. We also obtain bounds on the third-order coding rate. This is the first instance of a second-order result for a continuous-time channel. The converse proof hinges on a novel construction of an output distribution induced by Wyner's discretized channel and the construction of an appropriate $ε$ -net of the input probability simplex. While the achievability proof follows the general program to prove the third-order term for non-singular discrete memoryless channels put forth by Polyanskiy, several non-standard techniques -- such as new definitions and bounds on the probabilities of typical sets using logarithmic Sobolev inequalities -- are employed to handle the continuous nature of the channel.

preprint2020arXiv

Variable-Length Source Dispersions Differ under Maximum and Average Error Criteria

Variable-length compression without prefix-free constraints and with side-information available at both encoder and decoder is considered. Instead of requiring the code to be error-free, we allow for it to have a non-vanishing error probability. We derive one-shot bounds on the optimal average codeword length by proposing two new information quantities; namely, the conditional and unconditional $\varepsilon$ -cutoff entropies. Using these one-shot bounds, we obtain the second-order asymptotics of the problem under two different formalisms---the average and maximum probabilities of error over the realization of the side-information. While the first-order terms in the asymptotic expansions for both formalisms are identical, we find that the source dispersion under the average error formalism is, in most cases, strictly smaller than its maximum error counterpart. Applications to a certain class of guessing problems, previously studied by Kuzuoka [\emph{{IEEE} Trans.\ Inf.\ Theory}, vol.~66, no.~3, pp.~1674--1690, 2020], are also discussed.

preprint2019arXiv

Countably Infinite Multilevel Source Polarization for Non-Stationary Erasure Distributions

Polar transforms are central operations in the study of polar codes. This paper examines polar transforms for non-stationary memoryless sources on possibly infinite source alphabets. This is the first attempt of source polarization analysis over infinite alphabets. The source alphabet is defined to be a Polish group, and we handle the Arıkan-style two-by-two polar transform based on the group. Defining erasure distributions based on the normal subgroup structure, we give recursive formulas of the polar transform for our proposed erasure distributions. As a result, the recursive formulas lead to concrete examples of multilevel source polarization with countably infinite levels when the group is locally cyclic. We derive this result via elementary techniques in lattice theory.

preprint2018arXiv

Asymptotic Distribution of Multilevel Channel Polarization for a Certain Class of Erasure Channels

This study examines multilevel channel polarization for a certain class of erasure channels that the input alphabet size is an arbitrary composite number. We derive limiting proportions of partially noiseless channels for such a class. The results of this study are proved by an argument of convergent sequences, inspired by Alsan and Telatar's simple proof of polarization, and without martingale convergence theorems for polarization process.

preprint2017arXiv

Sharp Bounds on Arimoto's Conditional Rényi Entropies Between Two Distinct Orders

This study examines sharp bounds on Arimoto's conditional Rényi entropy of order $β$ with a fixed another one of distinct order $α\neq β$ . Arimoto inspired the relation between the Rényi entropy and the $\ell_{r}$ -norm of probability distributions, and he introduced a conditional version of the Rényi entropy. From this perspective, we analyze the $\ell_{r}$ -norms of particular distributions. As results, we identify specific probability distributions whose achieve our sharp bounds on the conditional Rényi entropy. The sharp bounds derived in this study can be applicable to other information measures, e.g., the minimum average probability of error, the Bhattacharyya parameter, Gallager's reliability function $E_{0}$ , and Sibson's $α$ -mutual information, whose are strictly monotone functions of the conditional Rényi entropy.

preprint2016arXiv

A Generalized Erasure Channel in the Sense of Polarization for Binary Erasure Channels

The polar transformation of a binary erasure channel (BEC) can be exactly approximated by other BECs. Arıkan proposed that polar codes for a BEC can be efficiently constructed by using its useful property. This study proposes a new class of arbitrary input generalized erasure channels, which can be exactly approximated the polar transformation by other same channel models, as with the BEC. One of the main results is the recursive formulas of the polar transformation of the proposed channel. In the study, we evaluate the polar transformation by using the $α$ -mutual information. Particularly, when the input alphabet size is a prime power, we examines the following: (i) inequalities for the average of the $α$ -mutual information of the proposed channel after the one-step polar transformation, and (ii) the exact proportion of polarizations of the $α$ -mutual information of proposed channels in infinite number of polar transformations.

preprint2016arXiv

Extremal Relations Between Shannon Entropy and $\ell_α$ -Norm

The paper examines relationships between the Shannon entropy and the $\ell_α$ -norm for $n$ -ary probability vectors, $n \ge 2$ . More precisely, we investigate the tight bounds of the $\ell_α$ -norm with a fixed Shannon entropy, and vice versa. As applications of the results, we derive the tight bounds between the Shannon entropy and several information measures which are determined by the $\ell_α$ -norm, e.g., Rényi entropy, Tsallis entropy, the $R$ -norm information, and some diversity indices. Moreover, we apply these results to uniformly focusing channels. Then, we show the tight bounds of Gallager's $E_{0}$ functions with a fixed mutual information under a uniform input distribution.

preprint2016arXiv

Relations Between Conditional Shannon Entropy and Expectation of $\ell_α$ -Norm

The paper examines relationships between the conditional Shannon entropy and the expectation of $\ell_α$ -norm for joint probability distributions. More precisely, we investigate the tight bounds of the expectation of $\ell_α$ -norm with a fixed conditional Shannon entropy, and vice versa. As applications of the results, we derive the tight bounds between the conditional Shannon entropy and several information measures which are determined by the expectation of $\ell_α$ -norm, e.g., the conditional Rényi entropy and the conditional $R$ -norm information. Moreover, we apply these results to discrete memoryless channels under a uniform input distribution. Then, we show the tight bounds of Gallager's $E_{0}$ functions with a fixed mutual information under a uniform input distribution.

preprint2016arXiv

Sharp Bounds Between Two Rényi Entropies of Distinct Positive Orders

Many axiomatic definitions of entropy, such as the Rényi entropy, of a random variable are closely related to the $\ell_α$ -norm of its probability distribution. This study considers probability distributions on finite sets, and examines the sharp bounds of the $\ell_β$ -norm with a fixed $\ell_α$ -norm, $α\neq β$ , for $n$ -dimensional probability vectors with an integer $n \ge 2$ . From the results, we derive the sharp bounds of the Rényi entropy of positive order $β$ with a fixed Rényi entropy of another positive order $α$ . As applications, we investigate sharp bounds of Ariomoto's mutual information of order $α$ and Gallager's random coding exponents for uniformly focusing channels under the uniform input distribution.

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.

Yuta Sakai

Research overview

Is this your work?

12 publications

Asymptotic Expansions of Smooth Rényi Entropies and Their Applications

Generalizations of Fano's Inequality for Conditional Information Measures via Majorization Theory

Modular Arithmetic Erasure Channels and Their Multilevel Channel Polarization

Second- and Third-Order Asymptotics of the Continuous-Time Poisson Channel

Variable-Length Source Dispersions Differ under Maximum and Average Error Criteria

Countably Infinite Multilevel Source Polarization for Non-Stationary Erasure Distributions

Asymptotic Distribution of Multilevel Channel Polarization for a Certain Class of Erasure Channels

Sharp Bounds on Arimoto's Conditional Rényi Entropies Between Two Distinct Orders

A Generalized Erasure Channel in the Sense of Polarization for Binary Erasure Channels

Extremal Relations Between Shannon Entropy and $\ell_α$ -Norm

Relations Between Conditional Shannon Entropy and Expectation of $\ell_α$ -Norm

Sharp Bounds Between Two Rényi Entropies of Distinct Positive Orders

See the researcher in context

Building this map preview

Yuta Sakai

Research overview

Is this your work?

12 publications

Asymptotic Expansions of Smooth Rényi Entropies and Their Applications

Generalizations of Fano's Inequality for Conditional Information Measures via Majorization Theory

Modular Arithmetic Erasure Channels and Their Multilevel Channel Polarization

Second- and Third-Order Asymptotics of the Continuous-Time Poisson Channel

Variable-Length Source Dispersions Differ under Maximum and Average Error Criteria

Countably Infinite Multilevel Source Polarization for Non-Stationary Erasure Distributions

Asymptotic Distribution of Multilevel Channel Polarization for a Certain Class of Erasure Channels

Sharp Bounds on Arimoto's Conditional Rényi Entropies Between Two Distinct Orders

A Generalized Erasure Channel in the Sense of Polarization for Binary Erasure Channels

Extremal Relations Between Shannon Entropy and ℓα\ell_αℓα​-Norm

Relations Between Conditional Shannon Entropy and Expectation of ℓα\ell_αℓα​-Norm

Sharp Bounds Between Two Rényi Entropies of Distinct Positive Orders

See the researcher in context

Building this map preview

Extremal Relations Between Shannon Entropy and $\ell_α$ -Norm

Relations Between Conditional Shannon Entropy and Expectation of $\ell_α$ -Norm