Finite Blocklength Converses in Point-to-Point and Network Information Theory: A Convex Analytic Perspective

Thursday, May 17, 2018 - 3:00pm

Event Calendar Category

LIDS Thesis Defense

Speaker Name

Ankur Kulkarni

Affiliation

Indian Institute of Technology. Bombay

Building and Room Number

32-D677

Abstract

The finite blocklength coding problem is a highly complex combinatorial optimization over functions, and one of its traditional challenges has been getting lower bounds or converses. While several finite blocklength converses have been discovered for several loss criteria using a variety of arguments, what is perhaps unsatisfactory is the absence of a common framework using which converses can be found for any loss criterion. We present a linear programming basedframework for obtaining converses for finite blocklength lossy joint source-channel coding problems. The framework applies for any loss criterion, generalizes previously known converses, and also extends to multi-terminal settings. The finite blocklength problem is posed equivalently as a nonconvex optimization problem and using a lift-and-project-like method, a close but tractable LP relaxation of this problem is derived. Lower bounds on the original problem are obtained by the construction of feasible points for the dual of this LP relaxation. A particular application of this approach leads to new converses that improve on the converses of Kostina and Verdu ́ for joint source-channel coding and lossy source-coding, and imply the converse of Polyanksiy, Poor and Verdu for channel coding. Another construction leads to a new general converse for finite blocklength joint source-channel coding that shows that the LP is tight for all blocklengths for the “matched setting” of minimization of the expected average bit-wise Hamming distortion of a q-ary uniform source over a q-ary symmetric memoryless channel.

The tightness of the LP relaxation for canonical problems in information theory shows that optimal coding in these problems shows that the finite blocklength problem is really a LP in disguise. Moreover, it has an associated “dual” viewpoint: namely, the optimal packing of “source flows” and “channel flows” that are throttled by an error density bottleneck. In the multi-terminal setting, using the language of these flows we derive improvements to converses of Miyake and Kanaya for Slepian-Wolf coding, the converse of Zhou et al for the successive refinement problem, new tight converses for compound and averaged channels and the asymmetric multiple access channel. These results provide a unified convex-analytic understanding of tractability of stochastic control problems with various information structures.

This is joint work with Ph.D. student Sharu Theresa Jose.

Biography

Ankur is an Assistant Professor (since 2013) with the Systems and Control Engineering group at Indian Institute of Technology Bombay (IITB). He received his B.Tech. in Aerospace Engineering from IITB in 2006, M.S. in 2008 and Ph.D. in 2010, both from the University of Illinois at Urbana-Champaign (UIUC). From 2010-2012 he was a post-doctoral researcher at the Coordinated Science Laboratory at UIUC. His research interests include the role of information in stochastic control, game theory, information theory, combinatorial coding theory problems, optimization and variational inequalities, and operations research. He is an Associate (from 2015--2018) of the Indian Academy of Sciences, Bangalore, a recipient of the INSPIRE Faculty Award of the Department of Science and Technology, Government of India, 2013, Best paper awards at the National Conference on Communications in Chennai, 2017, and the Indian Control Conference, 2018, and the William A. Chittenden Award, 2008 at UIUC. He is a consultant to the Securities and Exchange Board of India on the regulation of high frequency trading.