Communication, Control and Signal Processing Seminar 

Abstracts of talks

Fall 2015

09/10 Netanel Raviv (Technion/MIT), Construction of high-rate MSR codes over small fields

ABSTRACT: Three constructions of minimum storage regenerating (MSR) codes are presented. The first two constructions provide access-optimal MSR codes, with two and three parities, respectively, which attain the sub-packetization bound for access-optimal codes. The third construction provides larger MSR codes with three parities, which are not access-optimal, and do not necessarily attain the sub-packetization bound. In addition to a minimum storage in a node, these codes have the following two important properties: first, given storage in each node, the entire stored data can be recovered from any (any ) for 2 parity nodes (for 3 parity nodes, respectively); second, for the first two constructions, a helper node accesses the minimum number of its symbols for repair of a failed node (access-optimality). The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. The field size required for our construction is significantly smaller when compared to previously known codes. Joint work with Natalia Silberstein and Tuvi Etzion.

09/17 Vinay Praneeth Boda (UMD), Non-Asymptotic Achievability Bounds in Information Theory

ABSTRACT: Abstract: Standard achievability results in Information theory are obtained by using typical sequences and their asymptotic properties. Non-asymptotic achievability results are obtained by using random coding but not typical sequences. These do not require any assumptions on the source/channel such as memorylessness or discreteness.
Simple non-asymptotic counterparts of the conventional packing and covering lemmas which underlie the achievability proofs are discussed. We will also discuss the extensions of such underlying properties to multiuser settings such as the well known Wyner-Ziv problem.
This talk is based on `Non-Asymptotic Achievability Bounds in Multiuser Information Theory' by Sergio Verdu.

09/24 Itzhak Tamo (Tel-Aviv University), Explicit [n,k] Minimum-Storage Regenerating Code for all d's in the range {k, k+1,...n-1} simultaneously.

ABSTRACT: Abstract: Minimum Storage Regenerating (MSR) codes (a.k.a. maximum-distance-separable codes with optimal repair bandwidth) have recently emerged as an efficient solution for distributed data-storage systems. Under this model an [n,k,d] MSR code minimizes the amount of data stored in each node, while allowing to reconstruct the entire data by contacting any k of the n nodes in the system. Moreover, during a single node failure, any d helper nodes (where k-1 < d < n) suffice to successfully perform the repair process and recover the lost data. During this process, each helper node transmits the smallest possible amount of data that suffice to repair. This quantity of data equals to a 1/(d-k+1) fraction of the amount of data each node stores.
Previous code constructions focused on constructing MSR codes for a specific value of the parameter d. More specifically, in the low rate regime (rate k/n < 1/2) explicit MSR codes are known for a specific value of d as long as d>2k-2, and in the high rate regime only for d=n-1.
In this talk we take a different route and ask the the following question: does there exist a single [n,k] MSR code that repair optimally for all the parameters d in the range d=k,k+1,...,n-1? We resolve this question in the affirmative, by providing an explicit code construction together with an efficient encoding and decoding algorithms.
This is a Joint work with Dr. Eyal En-Gad from University of Southern California.

10/8 Yuval Kochman (Hebrew University), Finite-blocklength lossy compression of infinite sequences.

ABSTRACT: The problem of finite-blocklength lossy compression under an excess-distortion constraint is considered. If the blocklength constraint comes from the length of the source sequence itself, the excess rate needed above the rate-distortion function decays inversely proportional to the square root of the blocklength, according to second-order (dispersion) analysis. We consider a different case, where the source emits a long sequence, but shorter sub-sequences are considered for reasons such as delay, complexity and smoothness of the reconstruction fidelity. We analyze the redundancy of the rate with respect to different constraints. We show that the rate redundancy with respect to the processing blocklength, i.e. the dimension of the quantizer used, decays much faster than the dispersion analysis suggests. Thus, one may use much shorter source codes without sacrificing second-order performance.
This is joint work with Gregory Wornell (MIT).

10/15 Alborz Alavian (UMD), Measures of Decentralized Controllability and Observability.

ABSTRACT: In this talk, we will discuss the controllability of linear time-invariant (LTI) systems with decentralized controllers. Whether an LTI system is controllable (by LTI controllers) with respect to a given information structure can be determined by testing for fixed modes, but this gives a binary answer with no information about robustness.
First, we summarize the controllability and observability notions, and their connection to the Hankel operator which provides an in-depth perspective on how far a centralized system is from losing controllability or observability.
We will then review an existing measure that focuses on how far a decentralized system is from having a fixed mode, in particular the decentralized assignability measure of Vaz and Davison in 1988.
However, since the aforementioned measure cannot actually be computed in most cases, we thus discuss alternative approaches regarding an easily computable, non-binary measure of controllability for LTI systems with decentralized controllers of arbitrary information structure.

10/22 Pritam Mukherjee (UMD), Real interference alignment in multiple access wiretap channels.

ABSTRACT: In this talk, we will discuss the Gaussian multiple access wiretap channel with and without eavesdropper channel state information from a secure degrees of freedom perspective. We will review the real interference alignment technique and show how it can be used to achieve the optimal secure degrees of freedom for the multiple access wiretap channel with fixed channel gains. Time permitting, we will also discuss the converse proofs.

10/29 Min Ye (UMD), Cyclic equivalence relation of polar codes under addition modulo q operation.

ABSTRACT: In this work we study the addition modulo q operation in Arıkan transformation. We will prove that if the conditional probability vectors of y1 and y2 are cyclic shifts of each other, then we can merge the symbols y1 and y2 without changing the symmetric capacity of the channel itself and any of its descendants under iterated Arıkan transformations. We can use this observation to show that if two channels are the same after merging all the output symbols whose conditional probability vectors are cyclic shifts of each other, then the symmetric capacities of virtual channels will converge to the same random variable for these two channels. This result is also very useful in the polar code construction procedure since we can use it to shrink the output alphabet size without corrupting any useful information.

11/05 Zitan Chen (UMD), Capacity of binary causal adversarial channels.

ABSTRACT: In the binary causal adversarial channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $x=(x1,. . .,xn) \in {0,1}^n$ bit by bit via a channel limited to at most pn corruptions. The channel is causal in the sense that at the i-th step of communication the channel decides whether to corrupt the i-th bit or not based on its view so far, i.e., its decision depends only on the transmitted bits (x1,. . . ,xi). This is in contrast to the classical adversarial channel in which the error is chosen by a channel that has a full knowledge on the sent codeword x.
In this talk I will present the capacity of binary causal channels for the bit-flip corruption model in which the channel may flip at most pn bits of the transmitted codeword.

11/12 Prashanth L. A (UMD), Concentration bounds for TD(0) with function approximation.

ABSTRACT: We provide non-asymptotic bounds for the well-known temporal difference learning algorithm TD(0) with linear function approximators. These include high-probability bounds as well as bounds in expectation. Our analysis suggests that a step-size inversely proportional to the number of iterations cannot guarantee optimal rate of convergence unless we assume (partial) knowledge of the stationary distribution for the Markov chain underlying the policy considered. We also provide bounds for the iterate averaged TD(0) variant, which gets rid of the step-size dependency while exhibiting the optimal rate of convergence.

11/19 Abbas Kazemipour (UMD), Robust Estimation of Self-Exciting Point Process with Application to Neuronal Modeling (part II)

ABSTRACT: Binary data can be used to model spontaneous activities in many real-world applications. Applications include neural spiking activities, seismology, criminology, psychology, finance etc. Modeling, robust estimation and prediction of such data then becomes a problem of interest. It turns out that most of the time, future evolution of real-world data depends highly on their history. In this talk, the performance of \ell_1-regularized maximum likelihood estimator is investigated for sparse estimation of self-exciting point processes with highly dependent samples, including the Hawkes process. As we will show such estimation will overcome the shortcomings of standard maximum likelihood method. Non-asymptotic error bounds and convergence rates will be given as well as statistical tests of goodness-of-fit. A significant gap in mean squared error of the regularized and maximum likelihood estimates is observed. Application of the regularized estimator to the LGN neuron spiking data will be given where we successfully recovered their intrinsic oscillatory properties.

12/03 Heng Qiao (UMD), Structured Phase Retrieval with Partial Nested Fourier Sampler

ABSTRACT: In this talk, we will consider the problem of phase retrieval, where the goal is to recover a (possibly complex) signal from its magnitude measurements. Phase retrieval is a classical problem that arises in many areas of engineering and applied physics such optical imaging, X-ray crystallography, astronomical imaging, molecular imaging and so forth. We will consider the specific class of uniform Fourier samplers and discuss their roles and limitations in sparse phase retrieval. A new class of non-uniform Fourier sampler, namely the “Partial Nested Fourier Sampler” (PNFS) will be introduced to overcome the limitations of traditional Fourier samplers. It will be shown that PNFS enables sparse phase retrieval with near-minimal number of magnitude measurements, and leads to a computationally simpler algorithm. We will also address the question of injectivity in complex phase retrieval, and introduce the so-called 4N-4 conjecture. The structure of the PNFS will serve as a constructive counterexample to disprove the 4N-4 conjecture under appropriate assumptions.