BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Oliver Johnson

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

ResearcherUnclaimed source record
Information Theorymath.ITmath.PRmath.STStatistics Theorymath-phmath.MPmath.COmath.FAMethodologyquant-ph

Catalog footprint

Research overview

26works
11topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

26 publications

preprint2024arXiv

Relative entropy bounds for sampling with and without replacement

Sharp, nonasymptotic bounds are obtained for the relative entropy between the distributions of sampling with and without replacement from an urn with balls of c≥2c\geq 2 colors. Our bounds are asymptotically tight in certain regimes and, unlike previous results, they depend on the number of balls of each colour in the urn. The connection of these results with finite de Finetti-style theorems is explored, and it is observed that a sampling bound due to Stam (1978) combined with the convexity of relative entropy yield a new finite de Finetti bound in relative entropy, which achieves the optimal asymptotic convergence rate.

Open access
preprint2016arXiv

Discrete versions of the transport equation and the Shepp-Olkin conjecture

We introduce a framework to consider transport problems for integer-valued random variables. We introduce weighting coefficients which allow us to characterize transport problems in a gradient flow setting, and form the basis of our introduction of a discrete version of the Benamou-Brenier formula. Further, we use these coefficients to state a new form of weighted log-concavity. These results are applied to prove the monotone case of the Shepp-Olkin entropy concavity conjecture.

Open access
preprint2016arXiv

Improved group testing rates with constant column weight designs

We consider nonadaptive group testing where each item is placed in a constant number of tests. The tests are chosen uniformly at random with replacement, so the testing matrix has (almost) constant column weights. We show that performance is improved compared to Bernoulli designs, where each item is placed in each test independently with a fixed probability. In particular, we show that the rate of the practical COMP detection algorithm is increased by 31% in all sparsity regimes. In dense cases, this beats the best possible algorithm with Bernoulli tests, and in sparse cases is the best proven performance of any practical algorithm. We also give an algorithm-independent upper bound for the constant column weight case; for dense cases this is again a 31% increase over the analogous Bernoulli result.

Open access
preprint2016arXiv

Interference Management in Heterogeneous Networks with Blind Transmitters

Future multi-tier communication networks will require enhanced network capacity and reduced overhead. In the absence of Channel State Information (CSI) at the transmitters, Blind Interference Alignment (BIA) and Topological Interference Management (TIM) can achieve optimal Degrees of Freedom (DoF), minimising network's overhead. In addition, Non-Orthogonal Multiple Access (NOMA) can increase the sum rate of the network, compared to orthogonal radio access techniques currently adopted by 4G networks. Our contribution is two interference management schemes, BIA and a hybrid TIM-NOMA scheme, employed in heterogeneous networks by applying user-pairing and Kronecker Product representation. BIA manages inter- and intra-cell interference by antenna selection and appropriate message scheduling. The hybrid scheme manages intra-cell interference based on NOMA and inter-cell interference based on TIM. We show that both schemes achieve at least double the rate of TDMA. The hybrid scheme always outperforms TDMA and BIA in terms of Degrees of Freedom (DoF). Comparing the two proposed schemes, BIA achieves more DoF than TDMA under certain restrictions, and provides better Bit-Error-Rate (BER) and sum rate performance to macrocell users, whereas the hybrid scheme improves the performance of femtocell users.

Open access
preprint2016arXiv

Thinning and Information Projections

In this paper we establish lower bounds on information divergence of a distribution on the integers from a Poisson distribution. These lower bounds are tight and in the cases where a rate of convergence in the Law of Thin Numbers can be computed the rate is determined by the lower bounds proved in this paper. General techniques for getting lower bounds in terms of moments are developed. The results about lower bound in the Law of Thin Numbers are used to derive similar results for the Central Limit Theorem.

Open access
preprint2015arXiv

A hybrid TIM-NOMA scheme for the SISO Broadcast Channel

Future mobile communication networks will require enhanced network efficiency and reduced system overhead due to their user density and high data rate demanding applications of the mobile devices. Research on Blind Interference Alignment (BIA) and Topological Interference Management (TIM) has shown that optimal Degrees of Freedom (DoF) can be achieved, in the absence of Channel State Information (CSI) at the transmitters, reducing the network's overhead. Moreover, the recently emerged Non-Orthogonal Multiple Access (NOMA) scheme suggests a different multiple access approach, compared to the current orthogonal methods employed in 4G networks, resulting in high capacity gains. Our contribution is a hybrid TIM-NOMA scheme in Single-Input-Single-Output (SISO) K-user cells, in which users are divided into T groups, and 1/T DoF is achieved for each user. By superimposing users in the power domain, we introduce a two-stage decoding process, managing 'inter-group' interference based on the TIM principles, and 'intra-group' interference based on Successful Interference Cancellation (SIC), as proposed by NOMA. We show that for high SNR values the hybrid scheme can improve the sum rate by at least 100% when compared to Time Division Multiple Access (TDMA).

Open access
preprint2014arXiv

Blind Interference Alignment in General Heterogeneous Networks

Heterogeneous networks have a key role in the design of future mobile communication networks, since the employment of small cells around a macrocell enhances the network's efficiency and decreases complexity and power demand. Moreover, research on Blind Interference Alignment (BIA) has shown that optimal Degrees of Freedom (DoF) can be achieved in certain network architectures, with no requirement of Channel State Information (CSI) at the transmitters. Our contribution is a generalised model of BIA in a heterogeneous network with one macrocell with K users and K femtocells each with one user, by using Kronecker (Tensor) Product representation. We introduce a solution on how to vary beamforming vectors under power constraints to maximize the sum rate of the network and how optimal DoF can be achieved over K+1 time slots.

Open access
preprint2014arXiv

The capacity of non-identical adaptive group testing

We consider the group testing problem, in the case where the items are defective independently but with non-constant probability. We introduce and analyse an algorithm to solve this problem by grouping items together appropriately. We give conditions under which the algorithm performs essentially optimally in the sense of information-theoretic capacity. We use concentration of measure results to bound the probability that this algorithm requires many more tests than the expected number. This has applications to the allocation of spectrum to cognitive radios, in the case where a database gives prior information that a particular band will be occupied.

Open access
preprint2013arXiv

A de Bruijn identity for symmetric stable laws

We show how some attractive information--theoretic properties of Gaussians pass over to more general families of stable densities. We define a new score function for symmetric stable laws, and use it to give a stable version of the heat equation. Using this, we derive a version of the de Bruijn identity, allowing us to write the derivative of relative entropy as an inner product of score functions. We discuss maximum entropy properties of symmetric stable densities.

Open access
preprint2013arXiv

Group testing algorithms: bounds and simulations

We consider the problem of non-adaptive noiseless group testing of NN items of which KK are defective. We describe four detection algorithms: the COMP algorithm of Chan et al.; two new algorithms, DD and SCOMP, which require stronger evidence to declare an item defective; and an essentially optimal but computationally difficult algorithm called SSS. By considering the asymptotic rate of these algorithms with Bernoulli designs we see that DD outperforms COMP, that DD is essentially optimal in regimes where K≥NK \geq \sqrt N, and that no algorithm with a nonadaptive Bernoulli design can perform as well as the best non-random adaptive designs when K>N0.35K > N^{0.35}. In simulations, we see that DD and SCOMP far outperform COMP, with SCOMP very close to the optimal SSS, especially in cases with larger KK.

Open access
preprint2012arXiv

Bounds on the Poincare constant under negative dependence

We give bounds on the Poincare (inverse spectral gap) constant of a non-negative, integer-valued random variable W, under negative dependence assumptions such as ultra log-concavity and total negative dependence. We show that the bounds obtained compare well to others in the literature. Examples treated include some occupancy and urn models, a random graph model and small spacings on the circumference of a circle. Applications to Poisson convergence theorems are considered.

Open access
preprint2011arXiv

A natural derivative on [0,n] and a binomial Poincaré inequality

We consider probability measures supported on a finite discrete interval [0,n][0,n]. We introduce a new finitedifference operator ∇n\nabla_n, defined as a linear combination of left and right finite differences. We show that this operator ∇n\nabla_n plays a key role in a new Poincaré (spectral gap) inequality with respect to binomial weights, with the orthogonal Krawtchouk polynomials acting as eigenfunctions of the relevant operator. We briefly discuss the relationship of this operator to the problem of optimal transport of probability measures.

Open access
preprint2011arXiv

Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures

Sufficient conditions are developed, under which the compound Poisson distribution has maximal entropy within a natural class of probability measures on the nonnegative integers. Recently, one of the authors [O. Johnson, {\em Stoch. Proc. Appl.}, 2007] used a semigroup approach to show that the Poisson has maximal entropy among all ultra-log-concave distributions with fixed mean. We show via a non-trivial extension of this semigroup approach that the natural analog of the Poisson maximum entropy property remains valid if the compound Poisson distributions under consideration are log-concave, but that it fails in general. A parallel maximum entropy result is established for the family of compound binomial measures. Sufficient conditions for compound distributions to be log-concave are discussed and applications to combinatorics are examined; new bounds are derived on the entropy of the cardinality of a random independent set in a claw-free graph, and a connection is drawn to Mason's conjecture for matroids. The present results are primarily motivated by the desire to provide an information-theoretic foundation for compound Poisson approximation and associated limit theorems, analogous to the corresponding developments for the central limit theorem and for Poisson approximation. Our results also demonstrate new links between some probabilistic methods and the combinatorial notions of log-concavity and ultra-log-concavity, and they add to the growing body of work exploring the applications of maximum entropy characterizations to problems in discrete mathematics.

Open access
preprint2011arXiv

Non-parametric change-point detection using string matching algorithms

Given the output of a data source taking values in a finite alphabet, we wish to detect change-points, that is times when the statistical properties of the source change. Motivated by ideas of match lengths in information theory, we introduce a novel non-parametric estimator which we call CRECHE (CRossings Enumeration CHange Estimator). We present simulation evidence that this estimator performs well, both for simulated sources and for real data formed by concatenating text sources. For example, we show that we can accurately detect the point at which a source changes from a Markov chain to an IID source with the same stationary distribution. Our estimator requires no assumptions about the form of the source distribution, and avoids the need to estimate its probabilities. Further, we establish consistency of the CRECHE estimator under a related toy model, by establishing a fluid limit and using martingale arguments.

Open access
preprint2010arXiv

Asymptotic Sum-Capacity of Random Gaussian Interference Networks Using Interference Alignment

We consider a dense n-user Gaussian interference network formed by paired transmitters and receivers placed independently at random in Euclidean space. Under natural conditions on the node position distributions and signal attenuation, we prove convergence in probability of the average per-user capacity C_Sigma/n to 1/2 E log(1 + 2SNR). The achievability result follows directly from results based on an interference alignment scheme presented in recent work of Nazer et al. Our main contribution comes through the converse result, motivated by ideas of `bottleneck links' developed in recent work of Jafar. An information theoretic argument gives a capacity bound on such bottleneck links, and probabilistic counting arguments show there are sufficiently many such links to tightly bound the sum-capacity of the whole network.

Open access
preprint2010arXiv

Monotonicity, thinning and discrete versions of the Entropy Power Inequality

We consider the entropy of sums of independent discrete random variables, in analogy with Shannon's Entropy Power Inequality, where equality holds for normals. In our case, infinite divisibility suggests that equality should hold for Poisson variables. We show that some natural analogues of the Entropy Power Inequality do not in fact hold, but propose an alternative formulation which does always hold. The key to many proofs of Shannon's Entropy Power Inequality is the behaviour of entropy on scaling of continuous random variables. We believe that Rényi's operation of thinning discrete random variables plays a similar role to scaling, and give a sharp bound on how the entropy of ultra log-concave random variables behaves on thinning. In the spirit of the monotonicity results established by Artstein, Ball, Barthe and Naor, we prove a stronger version of concavity of entropy, which implies a strengthened form of our discrete Entropy Power Inequality.

Open access
preprint2010arXiv

Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction

An information theoretic perspective on group testing problems has recently been proposed by Atia and Saligrama, in order to characterise the optimal number of tests. Their results hold in the noiseless case, where only false positives occur, and where only false negatives occur. We extend their results to a model containing both false positives and false negatives, developing simple information theoretic bounds on the number of tests required. Based on these bounds, we obtain an improved order of convergence in the case of false negatives only. Since these results are based on (computationally infeasible) joint typicality decoding, we propose a belief propagation algorithm for the detection of defective items and compare its actual performance to the theoretical bounds.

Open access
preprint2009arXiv

Interference alignment-based sum capacity bounds for random dense Gaussian interference networks

We consider a dense KK user Gaussian interference network formed by paired transmitters and receivers placed independently at random in a fixed spatial region. Under natural conditions on the node position distributions and signal attenuation, we prove convergence in probability of the average per-user capacity $\csum/K$ to $\half \ep \log(1 + 2 \SNR)$. The achievability result follows directly from results based on an interference alignment scheme presented in recent work of Nazer et al. Our main contribution comes through an upper bound, motivated by ideas of `bottleneck capacity' developed in recent work of Jafar. By controlling the physical location of transmitter--receiver pairs, we can match a large proportion of these pairs to form so-called εε-bottleneck links, with consequent control of the sum capacity.

Open access
preprint2009arXiv

Thinning, Entropy and the Law of Thin Numbers

Renyi's "thinning" operation on a discrete random variable is a natural discrete analog of the scaling operation for continuous random variables. The properties of thinning are investigated in an information-theoretic context, especially in connection with information-theoretic inequalities related to Poisson approximation results. The classical Binomial-to-Poisson convergence (sometimes referred to as the "law of small numbers" is seen to be a special case of a thinning limit theorem for convolutions of discrete distributions. A rate of convergence is provided for this limit, and nonasymptotic bounds are also established. This development parallels, in part, the development of Gaussian inequalities leading to the information-theoretic version of the central limit theorem. In particular, a "thinning Markov chain" is introduced, and it is shown to play a role analogous to that of the Ornstein-Uhlenbeck process in connection to the entropy power inequality.

Open access
preprint2008arXiv

On the entropy and log-concavity of compound Poisson measures

Motivated, in part, by the desire to develop an information-theoretic foundation for compound Poisson approximation limit theorems (analogous to the corresponding developments for the central limit theorem and for simple Poisson approximation), this work examines sufficient conditions under which the compound Poisson distribution has maximal entropy within a natural class of probability measures on the nonnegative integers. We show that the natural analog of the Poisson maximum entropy property remains valid if the measures under consideration are log-concave, but that it fails in general. A parallel maximum entropy result is established for the family of compound binomial measures. The proofs are largely based on ideas related to the semigroup approach introduced in recent work by Johnson for the Poisson family. Sufficient conditions are given for compound distributions to be log-concave, and specific examples are presented illustrating all the above results.

Open access
preprint2006arXiv

Some results concerning maximum Renyi entropy distributions

We consider the Student-t and Student-r distributions, which maximise Renyi entropy under a covariance condition. We show that they have information-theoretic properties which mirror those of the Gaussian distributions, which maximise Shannon entropy under the same condition. We introduce a convolution which preserves the Renyi maximising family, and show that the Renyi maximisers are the case of equality in a version of the Entropy Power Inequality. Further, we show that the Renyi maximisers satisfy a version of the heat equation, motivating the definition of a generalized Fisher information.

Open access
preprint2004arXiv

Entropy and the Law of Small Numbers

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when Sn=∑i=1nXiS_n=\sum_{i=1}^nX_i is the sum of the (possibly dependent) binary random variables X1,X2,...,XnX_1,X_2,...,X_n, with E(Xi)=piE(X_i)=p_i and $E(S_n)=\la$, then \ben D(P_{S_n}\|\Pol)\leq \sum_{i=1}^n p_i^2 + \Big[\sum_{i=1}^nH(X_i) - H(X_1,X_2,..., X_n)\Big], \een where $D(P_{S_n}\|{Po}(\la))$ is the relative entropy between the distribution of SnS_n and the Poisson($\la$) distribution. The first term in this bound measures the individual smallness of the XiX_i and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the XiX_i are independent, the following sharper bound is established, \ben D(P_{S_n}\|\Pol)\leq \frac{1}λ \sum_{i=1}^n \frac{p_i^3}{1-p_i}, % \label{eq:abs2} \een and it is also generalized to the case when the XiX_i are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.

Open access
preprint2003arXiv

The von Neumann entropy and information rate for integrable quantum Gibbs ensembles, 2

This paper considers the problem of data compression for dependent quantum systems. It is the second in a series under the same title. As in the previous paper, we are interested in Lempel--Ziv encoding for quantum Gibbs ensembles. Here, we consider the canonical ideal lattice Bose- and Fermi-ensembles. We prove that as in the case of the grand canonical ensemble, the (limiting) von Neumann entropy rate hh can be assessed, via the classical Lempel--Ziv universal coding algorithm, from a single eigenvector of the density matrix.

Open access

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.