Source author record

Nir Elkayam

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

ResearcherUnclaimed source record

Information Theory math.IT math.ST Statistics Theory

Catalog footprint

What is connected

6works

4topics

1close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2020arXiv

One shot approach to lossy source coding under average distortion constraints

This paper presents a one shot analysis of the lossy compression problem under average distortion constraints. We calculate the exact expected distortion of a random code. The result is given as an integral formula using a newly defined functional $\tilde{D}(z,Q_Y)$ where $Q_Y$ is the random coding distribution and $z\in [0,1]$. When we plug in the code distribution as $Q_Y$, this functional produces the average distortion of the code, thus provide a converse result utilizing the same functional. Two alternative formulas are provided for $\tilde{D}(z,Q_Y)$, the first involves a supremum over some auxiliary distribution $Q_X$ which has resemblance to the channel coding meta-converse and the other involves an infimum over channels which resemble the well known Shannon distortion-rate function.

preprint2016arXiv

On the calculation of the minimax-converse of the channel coding problem

A minimax-converse has been suggested for the general channel coding problem by Polyanskiy etal. This converse comes in two flavors. The first flavor is generally used for the analysis of the coding problem with non-vanishing error probability and provides an upper bound on the rate given the error probability. The second flavor fixes the rate and provides a lower bound on the error probability. Both converses are given as a min-max optimization problem of an appropriate binary hypothesis testing problem. The properties of the first converse were studies by Polyanskiy and a saddle point was proved. In this paper we study the properties of the second form and prove that it also admits a saddle point. Moreover, an algorithm for the computation of the saddle point, and hence the bound, is developed. In the DMC case, the algorithm runs in a polynomial time.

preprint2016arXiv

Variational formulas for the power of the binary hypothesis testing problem with applications

Two variational formulas for the power of the binary hypothesis testing problem are derived. The first is given as the Legendre transform of a certain function and the second, induced from the first, is given in terms of the Cumulative Distribution Function (CDF) of the log-likelihood ratio. One application of the first formula is an upper bound on the power of the binary hypothesis testing problem in terms of the Re'nyi divergence. The second formula provide a general framework for proving asymptotic and non-asymptotic expressions for the power of the test utilizing corresponding expressions for the CDF of the log-likelihood. The framework is demonstrated in the central limit regime (i.e., for non-vanishing type I error) and in the large deviations regime.

preprint2015arXiv

Achievable and Converse bounds over a general channel and general decoding metric

Achievable and converse bounds for general channels and mismatched decoding are derived. The direct (achievable) bound is derived using random coding and the analysis is tight up to factor 2. The converse is given in term of the achievable bound and the factor between them is given. This gives performance of the best rate-R code with possible mismatched decoding metric over a general channel, up to the factor that is identified. In the matched case we show that the converse equals the minimax meta-converse of Polyanskiy et al.

preprint2014arXiv

A Universal Decoder Relative to a Given Family of Metrics

Consider the following framework of universal decoding suggested in [MerhavUniversal]. Given a family of decoding metrics and random coding distribution (prior), a single, universal, decoder is optimal if for any possible channel the average error probability when using this decoder is better than the error probability attained by the best decoder in the family up to a subexponential multiplicative factor. We describe a general universal decoder in this framework. The penalty for using this universal decoder is computed. The universal metric is constructed as follows. For each metric, a canonical metric is defined and conditions for the given prior to be normal are given. A sub-exponential set of canonical metrics of normal prior can be merged to a single universal optimal metric. We provide an example where this decoder is optimal while the decoder of [MerhavUniversal] is not.

preprint2013arXiv

Information Spectrum Approach to the Source Channel Separation Theorem

A source-channel separation theorem for a general channel has recently been shown by Aggrawal et. al. This theorem states that if there exist a coding scheme that achieves a maximum distortion level d_{max} over a general channel W, then reliable communication can be accomplished over this channel at rates less then R(d_{max}), where R(.) is the rate distortion function of the source. The source, however, is essentially constrained to be discrete and memoryless (DMS). In this work we prove a stronger claim where the source is general, satisfying only a "sphere packing optimality" feature, and the channel is completely general. Furthermore, we show that if the channel satisfies the strong converse property as define by Han & verdu, then the same statement can be made with d_{avg}, the average distortion level, replacing d_{max}. Unlike the proofs there, we use information spectrum methods to prove the statements and the results can be quite easily extended to other situations.