2
2.0

Jun 30, 2018
06/18

by
Matthew Aldridge; Leonardo Baldassini; Karen Gunderson

texts

#
eye 2

#
favorite 0

#
comment 0

An $m \times n$ matrix $\mathsf{A}$ with column supports $\{S_i\}$ is $k$-separable if the disjunctions $\bigcup_{i \in \mathcal{K}} S_i$ are all distinct over all sets $\mathcal{K}$ of cardinality $k$. While a simple counting bound shows that $m > k \log_2 n/k$ rows are required for a separable matrix to exist, in fact it is necessary for $m$ to be about a factor of $k$ more than this. In this paper, we consider a weaker definition of `almost $k$-separability', which requires that the...

Topics: Mathematics, Combinatorics, Information Theory, Computing Research Repository

Source: http://arxiv.org/abs/1410.1826

38
38

Sep 21, 2013
09/13

by
Leonardo Baldassini; Oliver Johnson; Matthew Aldridge

texts

#
eye 38

#
favorite 0

#
comment 0

We define capacity for group testing problems and deduce bounds for the capacity of a variety of noisy models, based on the capacity of equivalent noisy communication channels. For noiseless adaptive group testing we prove an information-theoretic lower bound which tightens a bound of Chan et al. This can be combined with a performance analysis of a version of Hwang's adaptive group testing algorithm, in order to deduce the capacity of noiseless and erasure group testing models.

Source: http://arxiv.org/abs/1301.7023v2

4
4.0

Jun 28, 2018
06/18

by
Matthew Aldridge

texts

#
eye 4

#
favorite 0

#
comment 0

We consider nonadaptive group testing with Bernoulli tests, where each item is placed in each test independently with some fixed probability. We give a tight threshold on the maximum number of tests required to find the defective set under optimal Bernoulli testing. Achievability is given by a result of Scarlett and Cevher; here we give a converse bound showing that this result is best possible. Our new converse requires three parts: a typicality bound generalising the trivial counting bound, a...

Topics: Statistics Theory, Information Theory, Statistics, Computing Research Repository, Mathematics

Source: http://arxiv.org/abs/1511.05201

4
4.0

Jun 29, 2018
06/18

by
Matthew Aldridge; Oliver Johnson; Jonathan Scarlett

texts

#
eye 4

#
favorite 0

#
comment 0

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...

Topics: Statistics Theory, Statistics, Information Theory, Computing Research Repository, Mathematics

Source: http://arxiv.org/abs/1602.03471

3
3.0

Jun 29, 2018
06/18

by
Oliver Johnson; Matthew Aldridge; Jonathan Scarlett

texts

#
eye 3

#
favorite 0

#
comment 0

We consider the nonadaptive group testing problem in the case that each item appears in a constant number of tests, chosen uniformly at random with replacement, so that the testing matrix has (almost) constant column weights. We analyse the performance of simple and practical algorithms in a range of sparsity regimes, showing that the performance is consistently improved in comparison with more standard Bernoulli designs. In particular, using a constant-column weight design, the DD algorithm is...

Topics: Probability, Information Theory, Computing Research Repository, Mathematics

Source: http://arxiv.org/abs/1612.07122

35
35

Sep 20, 2013
09/13

by
Matthew Aldridge; Oliver Johnson; Robert Piechocki

texts

#
eye 35

#
favorite 0

#
comment 0

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...

Source: http://arxiv.org/abs/1002.0235v2

43
43

Sep 22, 2013
09/13

by
Oliver Johnson; Matthew Aldridge; Robert Piechocki

texts

#
eye 43

#
favorite 0

#
comment 0

Ergodic interference alignment, as introduced by Nazer et al (NGJV), is a technique that allows high-rate communication in n-user interference networks with fast fading. It works by splitting communication across a pair of fading matrices. However, it comes with the overhead of a long time delay until matchable matrices occur: the delay is q^n^2 for field size q. In this paper, we outline two new families of schemes, called JAP and JAP-B, that reduce the expected delay, sometimes at the cost of...

Source: http://arxiv.org/abs/1004.0208v3

59
59

Sep 23, 2013
09/13

by
Matthew Aldridge

texts

#
eye 59

#
favorite 0

#
comment 0

A central problem in the operation of large wireless networks is how to deal with interference -- the unwanted signals being sent by transmitters that a receiver is not interested in. This thesis looks at ways of combating such interference. In Chapters 1 and 2, we outline the necessary information and communication theory background, including the concept of capacity. We also include an overview of a new set of schemes for dealing with interference known as interference alignment, paying...

Source: http://arxiv.org/abs/1109.1255v1

37
37

Jul 20, 2013
07/13

by
Matthew Aldridge

texts

#
eye 37

#
favorite 0

#
comment 0

Group testing is the combinatorial problem of identifying the defective items in a population by grouping items into test pools. Recently, nonadaptive group testing - where all the test pools must be decided on at the start - has been studied from an information theory point of view. Using techniques from channel coding, upper and lower bounds have been given on the number of tests required to accurately recover the defective set, even when the test outcomes can be noisy. In this paper, we give...

Source: http://arxiv.org/abs/1203.5927v1