Abstracts of talks, Spring 2016

Communication, Control and Signal Processing Seminar

Abstracts of talks

Fall 2016

09/08 Prashanth L. A. (UMD), Model-free optimization of human preferences in stochastic systems

ABSTRACT:In several real-world systems involving humans, traditional expected value cannot explain the observed behavior and incorporating distortions in the underlying probabilities of the system can alleviate this problem. Cumulative prospect theory (CPT) is a very popular approach that is based on probabilistic distortions and is more general than the expected value. We bring this idea to a stochastic optimization framework and propose algorithms for both estimation and optimization of the CPT-value objective. We propose an empirical distribution function based scheme to estimate the CPT-value and then use this scheme in the inner loop of a CPT-value optimization procedure. We propose both gradient-based as well as gradient-free CPT-value optimization algorithms, that are based on two well-known simulation optimization ideas: simultaneous perturbation stochastic approximation (SPSA) and model-based parameter search (MPS), respectively. We provide theoretical convergence guarantees for all the proposed algorithms and also illustrate the usefulness of CPT-based criteria in a traffic signal control application.

The majority of the talk will be accessible to a broad audience.
** Joint work with Cheng Jie, Michael Fu, Steve Marcus and Csaba Szepesvari.

09/15 Alborz Alavian (UMD), Polynomial Algorithms for Lower-Bounds on the k-th Singular Value of a Polynomial Matrix

ABSTRACT: This talk is on the minimization of the k-th singular value of a general polynomial matrix. We will discuss an equivalent optimization problem that is composed of a polynomial objective subjected to polynomial constraints, and a further rank constraint. We will then discuss two methods on the rank constraint to write this problem as a polynomial optimization problem. This can be used in conjunction with Sum-of-Squares (SOS) techniques to derive a lower-bound on the k-th singular value of a polynomial matrix. Time allowing, we will discuss applications of this problem in deriving bounds on how far an LTI dynamic system is from loosing decentralized controllability.

09/29 Zitan Chen (UMD), The Capacity of Online (Causal) q-ary Error-Erasure Channels

ABSTRACT: In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword ${\bf x} =(x_1,...,x_n)$ symbol-by-symbol via a channel limited to at most np errors (symbol changes) and np* erasures. The channel is ``online'' (i.e., ``causal") in the sense that at the i-th step of communication the channel decides whether to corrupt the i-th symbol or not only based on its view of the symbols $(x_1,...,x_i)$. This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword ${\bf x}$. The capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels have been characterized recently.
In this work we extend prior results in two important ways. First, we obtain the capacity of q-ary online channels for general $q$ (rather than just $q$=2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries.

10/6 P. Vijay Kumar (IISc), Binary Codes with Locality for Multiple Erasures Having Short Block Length

ABSTRACT: This paper considers linear, binary codes having locality parameter $r$, that are capable of recovering from $t$ greater than or equal to $2$ erasures and which additionally, possess short block length. The focus is mostly on codes which can recover from multiple erasures in a sequential manner. The case of recovery from multiple erasures in parallel will be discussed, in the restricted setting where the column and row weight of the parity-check matrix are fixed, and where the parity checks on a code symbol are pairwise orthogonal.

This is joint work with S. B. Balaji and K. P. Prasanth.

10/13 Zitan Chen, continued (UMD) , The Capacity of Online (Causal) q-ary Error-Erasure Channels

10/20 Vinay Praneeth Boda (UMD), Sampling Rate Distortion

ABSTRACT: In this talk, we consider a discrete memoryless multiple source with $m$ components of which $k \leq m$ possibly different sources are sampled at each time instant and jointly compressed in order to reconstruct all the $m$ sources under a given distortion criterion. A new notion of sampling rate distortion function(SRDf) is introduced, and is characterized first for the case of fixed-set sampling.
Next, different forms of randomized sampling in their increasing order of complexity are introduced and their corresponding SRDfs are characterized. For independent random sampling performed without knowledge of the source outputs, it is shown that the SRDf is the same regardless of whether or not the decoder is informed of the sequence of sampled sets. Next, for memoryless random sampling, where the sampling can depend on the source outputs, it is shown that deterministic sampling, characterized by a conditional point-mass, is optimal and suffices to achieve the sampling rate distortion function.

This is joint work with Prof. Prakash Narayan.

10/27 Yingquan Wu (Micron Technology), LDPC for flash - from theory to practice

ABSTRACT: This talk first presents the challenges of error-correcting coding in flash memories. It then gives the practical overview of LDPC codes. Finally, it reveals some insights of LDPC optimization for flash memories.

11/3 Paul Cuff (Princeton University), Part I: Wiretap Channels with Random States
Part II: Differential Privacy as a Mutual Information Constraint

ABSTRACT: In the first part, we propose a new encoding scheme for the wiretap channel setting where a random state is known non-causally to the encoder but not necessarily to the decoder (the Gelfand-Pinsker setting). This setting combines two scenarios with celebrated results in information theory--the wiretap channel and the Gelfand-Pinsker channel--and it so happens that essentially the same encoding scheme is optimal for both scenarios individually. A decade ago, Chen and Han Vinck analyzed the secrecy rates achieved by that same encoding scheme. Quite surprisingly, Chia and El Gamal more recently showed that a different encoding scheme which explicitly extracts a key from the state to be used for encryption can sometimes outperform that scheme. In this work, we show a simple superposition code design which performs at least as well as both of these competing schemes, accomplishing the key agreement concept in a more subtle way through the selection of the auxiliary random variables.

In the second part, an information theoretic notion of differential privacy will be presented, which establishes an equivalence between differential privacy and a mutual information constraint. This intuitive definition in terms of mutual information admits very simple proofs of several important properties of differential privacy.

11/10 Dipankar Maity (UMD), Optimal Strategies for Stochastic Linear Quadratic Differential Games with Costly Information

ABSTRACT: A two player stochastic differential game is considered with a given cost function. The players engage in a noncooperative game where one tries to minimize and the other tries to maximize the cost. The players are given a dynamical system and their actions serve as the control inputs to the dynamical system. Their goal is to control the state of this dynamical system to optimize the given objective function. We use the term “state of the game” to describe the state of this dynamical system. The challenge is that none of the players have access to the state of the game for all time, rather they can access the state intermittently and only after paying some information cost. Thus the cost structure is non-classical for a linear-quadratic game and it incorporates the value of information. We provide the Nash equilibrium strategy for the players under full state information access at no cost, as well as under costly state information access. The optimal instances for accessing the state information are also explicitly computed for the players.

11/17 Ahmed Arafa (UMD), Optimal Policies for Wireless Networks with Energy Harvesting Transmitters and Receivers: Effects of Decoding Costs

ABSTRACT: We consider the effects of decoding costs in energy harvesting communication systems. In our setting, receivers, in addition to transmitters, rely solely on energy harvested from nature, and need to spend some energy in order to decode their intended packets. We model the decoding energy as an increasing convex function of the rate of the incoming data. In this setting, in addition to the traditional energy causality constraints at the transmitters, we have the decoding causality constraints at the receivers, where energy spent by the receiver for decoding cannot exceed its harvested energy. We first consider the point-to-point single-user problem where the goal is to maximize the total throughput by a given deadline subject to both energy and decoding causality constraints. We show that decoding costs at the receiver can be represented as generalized data arrivals at the transmitter, and thereby moving all system constraints to the transmitter side. Then, we consider several multi-user settings. We start with a two-hop network where the relay and the destination have decoding costs, and show that separable policies, where the transmitter’s throughput is maximized irrespective of the relay’s transmission energy profile, are optimal. Next, we consider the multiple access channel (MAC) and the broadcast channel (BC) where the transmitters and the receivers harvest energy from nature, and characterize the maximum departure region. In all multi-user settings considered, we decompose our problems into inner and outer problems. We solve the inner problems by exploiting the structure of the particular model, and solve the outer problems by water-filling algorithms. In this talk, we focus on the single-user and the BC settings. Time permitting, we will discuss the MAC scenario afterwards.

12/1 Aditya Ramamoorthy (Iowa State), Combinatorial designs for distributed storage, function computation and coded caching

ABSTRACT: Combinatorial design theory has its roots in recreational mathematics and is concerned with the arrangement of the elements of a finite set into subsets, such that the collection of subsets has certain "nice" properties. In this talk we shall demonstrate that interpreting designs in the right manner yields improved solutions for distributed storage and content caching and novel impossibility results for distributed function computation.

Regenerating codes have been proposed as an efficient mechanism for dealing with the problem of reliability in large scale distributed storage systems. These systems also have additional requirements pertaining to repair. When nodes fail, the system needs to be repaired in a speedy manner by consuming as few resources (number of drives accessed, energy etc.) as possible. We will demonstrate that combinatorial designs allow us to design efficient systems that upon failure can be repaired by simply downloading packets from the surviving nodes.

Next, we will show that designs can be used to construct a family of directed acyclic networks that have several interesting properties. In particular, our work shows that the computation rate of such networks depends significantly on the source alphabets. This is in stark contrast with multiple unicast networks where the rate is independent of the source alphabet. We will conclude with an overview of the role of coding in content caching networks and our recent results on how combinatorial designs can play a central role in making coded caching more practical.

The talk will be self-contained; no background in combinatorial designs and/or network coding will be assumed.

12/8 Himanshu Tyagi/ Shun Watanabe (IISc/TUAT), Interactive Data Exchange

ABSTRACT: An interactive communication protocol for data exchange enables multiple parties observing correlated data to recover each other's data and attain omniscience. When the data is generated from a known distribution, a non-interactive communication protocol is known to be asymptotically rate optimal. In the first part of this talk, we present an interactive protocol for data exchange for two parties that can outperform the best non-interactive one for finite data lengths and is asymptotically optimal even up to the second order term. We also present a universal variant of this interactive protocol which does not require the knowledge of the probability distribution of the data. In the second part of the talk, we present a multiparty universal protocol for data exchange which performs reasonably well for any given data sequence (and not only on average for randomly generated data). In our proposed protocol, the parties communicate in the order of randomness in their local data and enable data exchange recursively. A key technical step in the analysis of our protocol is establishing its recursive nature, namely when a subset of parties recover each other's data, their rates appear as if this subset of parties were collocated and have been executing the protocol as a single party.