Communication, Control and Signal Processing Seminar
Abstracts of talks
Fall 2013
08/23 Ioannis Lambadaris (Carleton University, Canada), Stability Analysis and Delay Optimality in Multi-Queue Multi-Server (MQMS) Systems
ABSTRACT:
The first part of the talk presents an explicit characterization of the
stability region of stationary Multi-Queue Multi-Server (MQMS) queuing systems
by means of a finite set of linear inequalities. More specifically, we compute
the coefficients of the linear inequalities describing the facet-defining hyperplanes
of the stability region polytope. Such a characterization is useful for performance
evaluation of certain scheduling algorithms such as Maximum Weight (MW) policy.
Our results can be used for studying the asymptotic behavior of the MW policy and
computing bounds for the average queuing delay, as well as limiting moments of the
queue sizes in heavy traffic regime.
In the second part of the talk we consider symmetric MQMS systems. We study
the problem of assigning K identical servers to a set of N parallel queues
in a time-slotted system. The connectivity of each queue to each server is assumed to be
i.i.d Bernoulli process; each server can serve at most one queue and each queue
can be served by at most one server during each time slot. It has been previously proven
that Maximum Weighted Matching (MWM) is a throughput optimal server assignment policy for such a system.
We prove that for a symmetric system with i.i.d. Bernoulli arrivals and connectivities,
MWM minimizes, in stochastic ordering sense, a range of cost functions of the queue lengths
such as total queue occupancy (which implies minimization of average queuing delay).
09/18 Sirin Nitinawarat (UIUC), Controlled Sensing for Sequential Multihypothesis Testing
ABSTRACT:
The problem of multiple hypothesis testing with observation control is considered in the sequential setting.
In the case of uniform sensing cost, a sequential test is proposed generalizing the one studied
in earlier work by Chernoff for binary hypothesis testing. Using the notion of decision making risk
in place of the overall probability of error, the proposed test is shown to be first-order asymptotically
optimal for multihypothesis testing {\em in a strong sense.} Another test is also proposed to meet
{\em distinctly predefined} constraints on the various decision risks {\em non-asymptotically,}
while retaining asymptotic optimality. Then a new model for controlled sensing for sequential
multihypothesis testing is proposed. This new model generalizes the existing one in two aspects.
First, it includes a more complicated memory structure in the controlled observations.
Second, it allows for a general cost structure which entails accumulating up to the final decision
time the total control cost with respect to an arbitrary cost function. Consequently,
this new model is relevant to a wider class of applications, particularly in distributed and mobile
sensor networks. A sequential test is proposed for this new model and is shown to
be strongly asymptotically optimal. Interestingly, it is shown that the optimal
causal control policy for the controlled sensing problem is {\em self-tuning,} i.e.,
maximizing an inherent "inferential" reward simultaneously under every hypothesis, with the
maximal value being the best possible, even when the true hypothesis is known at the outset.
Joint work with Dr. George Atia and Professor Venugopal V. Veeravalli.
09/26 Itzhak Tamo (UMD), Non-linear index coding outperforming the linear optimum
ABSTRACT:
In the seminar I will present the paper: Non-linear index coding outperforming
the linear optimum, by Eyal Lebetzky and Uri Stav from 2007.
The paper talks about the following source coding problem:
A sender holds a binary word of length n, and wishes to broadcast a codeword
(which is a function of the binary word) to n receivers. The i-th receiver is interested
in the i-th bit of the length n binary word, and he has prior side information
comprising some subset of the n bits.
An index code for this problem is an encoding scheme which enables each receiver
to always reconstruct his desired bit, given his side information. The minimal codeword
length of an index code was studied by Bar-Yossef, Birk, Jayram and Kol, and
conjectured that linear index coding is in fact always optimal.
In the seminar I will present the result in the paper which disproves this conjecture.
This is achieved by an explicit construction of an index coding problem.
No prior knowledge will be assumed.
10/07 Shlomo Shamai (Technion—Israel Institute of Technology), Cloud Radio Access Downlinks, with Backhaul Constrained Oblivious Processing
ABSTRACT:
The talk considers the downlink of cloud radio access networks,
in which a central encoder is connected to multiple multi-antenna base
stations (BSs) via finite-capacity backhaul links. The processing is done
at the central encoder, while the distributed BSs employ only oblivious
(robust) processing. We first review state-of-the-art approaches, where
the signals intended for different BSs are compressed independently,
or alternatively the recently introduced structured coding ideas
(reverse compute-and-forward) are employed. We propose to leverage
joint compression, also referred to as multivariate compression, of the
signals of different BSs in order to better control the effect of the additive
quantization noises at the mobile stations. We address the maximization of
a weighted sum rate. For joint compression this is associated with the
optimization of the precoding matrix and the joint correlation matrix of
the quantization noises, subject to power and backhaul capacity constraints.
An iterative algorithm is described that achieves a stationary point, and a
practically appealing architecture is proposed based on successive steps of
minimum mean-squared error estimation and per-BS compression. We conclude by
comparing different processing techniques, discussing a robust design
concerning the available accuracy of the channel state information and
overviewing aspects for future research. Joint work with S.-H. Park,
O. Simeone (NJIT), and O. Sahin (InterDigital).
10/08 Amos Lapidoth (ETH, Switzerland) , Source Coding with Lists and Rényi Entropy
ABSTRACT:
It is generally accepted that Rényi entropy is fundamental to
Information Theory, even if its operational meaning is not as
compelling as that of Shannon entropy. In this talk I shall discuss a
variation on the source-coding problem whose solution is the source's
Rényi entropy. This problem, which may also be of interest in its own
right, will allow us to derive many of the properties of Rényi entropy
using information-theoretic arguments. The problem will also provide
an operational meaning to the lesser-known conditional Rényi
entropy. I shall conclude with extensions to lossy source-coding.
Based on joint work with Christoph Bunte.
10/17 Talha Cihad Gulcu (UMD), Polar codes: Speed of polarization and polynomial gap to capacity
ABSTRACT:
In the seminar I will present the paper: Polar codes: Speed of polarization
and polynomial gap to capacity, by Venkatesan Guruswami and Patrick Xia,
submitted to arXiv in April 2013.
Shannon's channel coding theorem implies that for every memoryless
binary input channel W, there exists a constant a_W such that
for any N > a_W/\eps^2, there exists a binary code of length N
and rate I(W)-\eps which enables reliable communication on W.
One might wonder what the corresponding situation is when it comes
to polar codes. Guruswami-Xia answers this question as follows:
There exists a constant \mu (indpt of channel) such that
the statement in the previous paragraph remains to be true,
if "N>a_W/\eps^2" is replaced by "N>a_W/\eps^(\mu)" and
if "there exists a binary code" is replaced by "there exists a
polar code".
The authors also give a concrete poly(N) time construction
having N*poly(log N) decoding complexity.
10/24 Raef Bassily (Pennsylvania State University), Causal Erasure Channels
ABSTRACT:
We consider the communication problem over binary causal adversarial erasure channels.
Such a channel maps n input bits to n output symbols in {0, 1, ^}, where ^ denotes erasure.
The channel is causal if, for every i, the channel adversarially decides whether to erase
the i-th bit of its input based on inputs 1, ..., i, before it observes bits i+1 to n.
Such a channel is p-bounded if it can erase at most a p fraction of the input bits over
the whole transmission duration. Causal channels provide a natural model for channels that
obey basic physical restrictions but are otherwise unpredictable or highly variable.
For a given erasure rate p, our goal is to understand the capacity at which a randomized
(stochastic) encoder/decoder can transmit reliably across all causal p- bounded erasure channels.
In this talk, I will present the causal erasure model and give new upper bounds and lower bounds
on the achievable rate. Our bounds separate the capacity in the causal erasures setting from the
capacity in two related models: random erasure channels (strictly weaker) and fully adversarial
erasure channels (strictly stronger). Specifically, we show:
-A strict separation between random and causal erasures for all constant erasure rates p \in (0, 1).
In particular, we show that the capacity of causal erasure channels is 0 for p \geq 1/2
(while it is nonzero for random erasures).
-A strict separation between causal and fully adversarial erasures for p \in (0, \phi) where \phi \approxeq 0.348.
-For p \in [\phi, 1/2), we show existence of codes for causal erasures that achieve higher rate than
the best known constructions for fully adversarial channels.
Our results contrast with existing results on correcting causal bit-flip errors (as opposed to erasures)
[Dey et. al 08, 09], [Haviv-Langberg 11] . For the separations we provide, the analogous separations
for bit-flip models are either not known at all or much weaker.
This talk is based on a joint work with Adam Smith (Pennsylvania State University). It is to appear
in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014.
10/31,11/21 Itzhak Tamo (UMD), A Family of Locally Recoverable Codes
ABSTRACT:
In today's information era, data centers are facing challenging tasks of managing,
analyzing, and storing enormous amounts of data. One such task is recovery, namely,
the problem of storing information with added redundancy in order to provide resiliency
to erasures. The key requirement of the problem is the locality property, which assumes
that it is possible to recover each element of the information by accessing a small
of amount of other information blocks. Clearly, the property of local recovery translates
to a faster recovery of lost data.
The more formal definition is as follows: A code over a finite alphabet is called locally
recoverable (LRC) if every symbol in the encoding is afunction of a small number other symbols.
In the talk I will present a family of LRC codes that attain the maximum possible value
of the distance for a given locality parameter and code cardinality.
This is a joint work with Alexander Barg.
11/07,11/14 Shun Watanabe (UMD), Non-Asymptotic and Second-Order Achievability Bounds for Source Coding with Side-Information
ABSTRACT:
We present a novel achievability bound for the Wyner-Ahlswede-Korner (WAK) problem of lossless
source coding with rate-limited side-information. This bound is proved using ideas from channel
simulation and channel resolvability. The bound improves on all previous non-asymptotic bounds
on the error probability of WAK problem. We also present achievable second-order rates by
applying the multidimensional Berry-Esseen theorem to our new non-asymptotic bound.
In this talk, I will review some backgrounds on the non-asymptotic and second-order analyses,
and present our results and ideas of proofs. This talk is based on a joint work with Shigeaki
Kuzuoka and Vincent Y. F. Tan, which was presented at ISIT 2013 (see also
http://arxiv.org/abs/1301.6467
).
12/5 Praneeth Boda (UMD), Source Coding Problem for Sources with Additional Outputs to Keep Secret from the Receiver or Wiretappers
ABSTRACT:
In the seminar I will present a work of H.Yamamoto and some related problems.
A source coding problem is considered for a communication system with correlated source outputs.
One of the source outputs must be transmitted to the receiver within a prescribed distortion tolerance,
and the other source output has to be kept as secret as possible from the receiver or wiretappers.
For this case, the equivocation-distortion function and the rate-distortion-equivocation function are
defined and evaluated. Some applications and related problems will be looked at.