Communication, Control and Signal Processing Seminar 

Abstracts of talks

Spring 2014

2/20 Behtash Babadi (UMD), Asymptotic achievability of the Cramér-Rao bound and a compound channel-type universal sufficiency condition for noisy sparse support recovery

ABSTRACT: We consider the problem of asymptotically reliable recovery of a sparse vector from noisy incomplete measurements. First, we characterize the Cramér-Rao bound (CRB) for genie-aided sparse recovery (support known by the decoder) as a performance benchmark. Next, by analyzing a joint-typicality decoder, we show that the genie-aided CRB is asymptotically achievable under certain sufficiency conditions with no knowledge of the support by the decoder. Finally, we prove the universality of Gaussian measurement matrices for asymptotically reliable sparse support recovery under similar sufficiency conditions. In an analogy to the achievability of channel capacity, our approach in the latter is analogous to that of Blackwell-Breiman-Thomasian and Wolfowitz in proving the achievability of the compound channel capacity, whereas existing results are in the vein of Shannon’s methodology in establishing the achievability of a single channel capacity.

3/6,3/25 Piya Pal (UMD), Sub-Nyquist Sampling for Wideband Signals

ABSTRACT: We consider the problem of sampling and reconstruction of wideband signals. A central question that arises in such problems is: “How to sample the signal so that its spectrum can be estimated perfectly?” A necessary condition on the minimum sampling frequency (irrespective of the sampling scheme) was provided by Landau which shows that the sampling frequency can be much smaller than the highest frequency contained in the wideband spectrum, provided the spectrum exhibits sparsity. Recent advances in compressive sensing have demonstrated how to attain the Landau rate by providing practical sampling and reconstruction schemes based on $l_{1}$-norm minimization.
We will revisit these recent results on wideband sampling in the context of signals that are Wide-Sense Stationary. By designing suitable non uniform sampling schemes, we will show that the sampling rate can be made much smaller than the Nyquist rate, even without assuming the spectrum to be sparse. Such sampling schemes will be shown to universal (i.e. they work for any spectrum) and the reconstruction can be blind (i.e. it does not assume the spectral support to be known). Depending on the application of interest, this can lead to design of low power A/D converters, or deployment of far fewer sensors for array processing applications. When the spectrum is sparse, it can be estimated by solving a suitable linear program with a positive constraint. The optimality conditions of this linear program will provide additional insights into the design of good samplers.

3/11 Isaak Mayergoyz (UMD), Mathematical Models of Hysteresis

ABSTRACT: In the talk, mathematical models of hysteresis with "non-local (non-markovian) memories" will be discussed with special emphasis on their generality and applicability to the description of hysteresis of any origin. Stochastic aspects of hysteresis modelling will be presented and stressed. Some engineering applications of these hysteresis models will be outlined as well.

4/1 Talha Cihad Gulcu (UMD), Interactive Function Computation via Polar Coding

ABSTRACT: In a series of papers N. Ma and P. Ishwar (2011-13) considered a range of distributed source coding problems that arise in the context of iterative computation of functions, characterizing the region of achievable communication rates. We consider the problems of interactive computation of functions by two terminals and interactive computation in a collocated network, showing that the rate regions for both these problems can be achieved using several rounds of polar-coded transmissions.

4/8 William J. Martin (WPI), Promise, Progress, and Problems in Homomorphic Encryption

ABSTRACT: Recent excitement about homomorphic encryption is tempered with appropriate caution when the discussion turns to actual implementation of such powerful systems. Ever since Gentry's proposal of the first credible fully homomorphic encryption scheme in 2009, two conversations have raged away, each not seeming to hear the other.
On the one hand, the promise for such schemes is great. Cloud computing, private information retrieval, data aggregation, and many other applications await encryption strategies that allow one to compute directly on ciphertexts. The power of such schemes has both companies and universities scrambling to develop the first practical implementations.
Meanwhile, current proposals for fully homomorphic encryption have key lengths in the gigabyte range, single encryptions take minutes or hours, and encrypted data is millions of times as big as the corresponding plaintext. Talking to Forbes magazine in 2011, Lampson said ``I don’t think we’ll see anyone using Gentry’s solution in our lifetimes''. The obstacles to secure practical implementation seem insurmountable.
Our research community is made for exactly this sort of challenge!
In this talk, I will introduce very basic ideas of encryption, describe a few homomorphic schemes and their shortcomings. Then I will try to convince you that there is reason to be optimistic. We will discuss partially homomorphic schemes, conversion between schemes, implementation results from WPI's Vernam Group, and I will survey a number of open problems.

4/15,4/22 Praneeth Boda, Itzahak Tamo (UMD), Analysis of Boolean Functions

ABSTRACT: Boolean functions are central objects in combinatorics, complexity theory, probability theory and other areas of mathematics and computer science. In this talk, we will introduce Boolean functions, look at the Fourier analysis of Boolean functions and some applications. We will look at some basic tests such as BLR test, local testing.

4/29 Min Ye (UMD), Polar Codes for Distributed Hierarchical Source Coding

ABSTRACT: We show that polar codes can be used to achieve the rate-distortion functions in the problem of hierarchical source coding also known as the successive refinement problem. We also analyze the distributed version of this problem, constructing a polar coding scheme that achieves the rate distortion functions for successive refinement with side information.