Information and Coding Theory Seminar
Abstracts of talks
Fall 2010
09/23 Dr. Maxim Raginsky (Duke University), Empirical Processes, Typical Sequences and Coordinated Actions in Standard Borel Spaces
ABSTRACT:
Recent work by Cuff, Permuter and Cover on coordination via
communication has revealed a fascinating aspect of strongly typical
sequences --- they can be thought of as a means of reproducing
relative frequencies of symbols emitted by stationary memoryless
sources using finite communication resources. This viewpoint has a
number of useful and far-reaching implications in such settings as
distributed control and decision-making, network security, and
statistical learning. However, strong typicality, as it pertains to
approximating source distributions by relative frequencies in the
sense of total variation, is not appropriate for continuous alphabet
sources. In this talk, I will present a generalization of typicality
that works for a wide class of abstract alphabets (so-called standard
Borel spaces, which include all conceivable alphabets of practical
interest). This new notion makes fundamental use of an object known in
modern mathematical statistics as the empirical process, which is used
to characterize the fluctuations of sample averages of functions in a
given class around their true expectations. The proposed new notion of
typicality possesses a minimal set of properties that make it useful
in the context of abstract alphabets. To show this, I will use it to
derive single-letter expressions for the minimal achievable rates in
two source coding scenarios that can be viewed as generation of
coordinated actions in a two-node network. One feature of note is that
the achievability proofs are as transparent as in the finite-alphabet
case.
10/07 Arya Mazumdar (UMD), Codes for High Density Magnetic Recording on a 1-d Granular Medium
ABSTRACT:
In terabit-density magnetic recording, several bits
of data can be replaced by the values of their neighbors in the
storage medium. As a result, errors in the medium are dependent
on each other and also on the data written.Here
we study a simple one-dimensional model of this situation. In
our model binary data is sequentially written on the medium and
a bit can erroneously change to the immediately preceding value.
We define a probabilistic finite-state channel model of the
storage medium and derive estimates of its capacity. To derive a
lower bound we consider a uniform input distribution, and find
an exact expression of the symmetric capacity of the channel. An
upper bound is found by showing that the original channel is a
stochastic degradation of another, related channel model whose
capacity we compute explicitly.
This is a joint work with Alexander Barg and Navin Kashyap.
10/28 Woomyoung Park (UMD), Linear Ordered Codes, Shape Enumerators, and Parallel Channels
ABSTRACT:
We consider linear codes in Hamming-like metric spaces with
the metric derived from a partial order of coordinates of codewords.
In the first part, we will discuss a matroid-theoretic perspective of linear
ordered codes; introducing the (multivariate) Tutte polynomial and extending
the Greene's theorem for an ordered metric. The relation between the higher
weight distributions and the Tutte polynomial is presented.
The ordered metric is known to describe the noise process in a wireless
fading system studied by Tavildar and Viswanath (2006). We define a
probabilistic model of the channel in the system termed by the ordered
symmetric channel. As an application of these results, the extension of
Wyner's wire-tap channel I and Ozarow-Wyner's wire-tap channel II model
are discussed.
This is a joint work with Alexander Barg.
11/04 Ersen Ekrem (UMD), An Alternative Proof for the Capacity Region of the Degraded Gaussian MIMO Broadcast Channel (I)
ABSTRACT:
We provide an alternative proof for the capacity region of
the
degraded Gaussian multiple-input multiple-output (MIMO) broadcast
channel. Our proof does not use the channel enhancement technique
as opposed to the original proof of Weingertan et. al and
the alternative proof of Liu {\it et. al}. Our proof starts with
the single-letter description of the capacity region of the
degraded broadcast channel, and directly evaluates it for the
degraded Gaussian MIMO broadcast channel by using two main
technical tools. The first one is the generalized de Bruijn
identity due to Palomar~\emph{et. al.} which provides a connection
between the differential entropy and the Fisher information
matrix. The second tool we use is an inequality due to Dembo which
lower bounds the differential entropy in terms of the Fisher
information matrix.
This is joint work with Sennur Ulukus.
11/11 Ersen Ekrem (UMD), An Alternative Proof for the Capacity Region of the Degraded Gaussian MIMO Broadcast Channel (II)
12/02 Anna Pantelidou (University of Oulu, Finland), Single-hop Versus Multi-hop Transmission for Energy-efficient Multicasting
ABSTRACT:
In this talk we will consider the problem of multicasting
from a
single source to a set of destinations. We will assume that the source
can either reach the destinations directly or forward its traffic
through a set of assisting relays. Due to the non-linear attenuation
of the signal with distance, employing the relays can help to improve
the signal quality at the destinations. Meanwhile, relays also consume
energy for retransmission of the received information and can decrease
the rate of communication due to the multi-hop transmission. Under the
performance objective of maximizing the common amount of information
(number of bits) that the source sends to all destinations per Joule
of the total energy spent, we wish to identify whether direct
transmission from the source to the destinations is preferable as
opposed to multi-hop forwarding through the relays. In the latter
case, we also wish to identify a) which subset of the relays should be
activated, b) for how long, and c) the respective destinations that
each relay has to serve.
This is a joint work with the Ph.D. student,
Q. Xue, at the University of Oulu, Finland.
12/09 Arya Mazumdar (UMD), Combinatorial Non-Adaptive Group Testing
ABSTRACT:
Suppose we have a set U of n elements and among them
there are d defectives, d << n. The objective is to identify the
defective items. A test is performed on a subset T1 of U, with a
positive
output if and only if there exists at least one defective item in T1.
We would like
to know the minimum number of tests required such that the objective
is achieved.
We will discuss only the non-adaptive setting where all the tests are
done
simultaneously.
This problem and its variations form an area of research, that is active
for at least past sixty years. In this talk I will summarize the best
known
lower and upper (constructions) bounds on this Group Testing problem.
In the process we will review superimposed codes, disjunct matrices and
concatenated codes among other topics.