2017 AusITS
2017 IEEE Australian Information Theory School (AusITS)

Australian National University, Canberra — 16–17 January 2017


Program Structure

Nonconvex Methods for High Dimensional Estimation - Prof. Yingbin Liang

Back to Top

Abstract: High dimensional estimation problems, such as phase retrieval, low rank matrix estimation, and blind deconvolution, attracted intensive attention recently due to their wide applications in medical image, signal processing, social networks, etc. Traditional approaches to solving these problems are either empirical, which work well but lack theoretic guarantee; or via convex formulations, which come with performance guarantee but are computationally costly in large dimensions. Nonconvex approaches are recently emerging as a powerful method to such problems, which come with provable performance guarantee and are computationally efficient.

In this talk, I will first introduce a number of high dimensional estimation problems and their conventional solutions, in particular, convex approaches. I will then describe recent advance in using nonconvex methods towards solving these problems and their advantages over convex approaches. In particular, I will use phase retrieval problem as an example to illustrate the central idea to develop nonconvex algorithms and various techniques to further improve sample complexity, robustness, and computational efficiency. I will also discuss the insights that such solutions bring to general nonconvex optimization. I will finally talk about open problems and future directions.

Lecturer’s Bio: Dr. Yingbin Liang received the Ph.D. degree in Electrical Engineering from the University of Illinois at Urbana-Champaign in 2005. In 2005-2007, she was working as a postdoctoral research associate at Princeton University. In 2008-2009, she was an assistant professor at the University of Hawaii. Since December 2009, she has been on the faculty at Syracuse University, where she is an associate professor. Dr. Liang’s research interests include information theory, statistical learning theory, optimization for large scale machine learning, and wireless communication and networks.

Dr. Liang was a Vodafone Fellow at the University of Illinois at Urbana-Champaign during 2003-2005, and received the Vodafone-U.S. Foundation Fellows Initiative Research Merit Award in 2005. She also received the M. E. Van Valkenburg Graduate Research Award from the ECE department, University of Illinois at Urbana-Champaign, in 2005. In 2009, she received the National Science Foundation CAREER Award, and the State of Hawaii Governor Innovation Award. In 2014, she received EURASIP Best Paper Award for the EURASIP Journal on Wireless Communications and Networking. She served as an Associate Editor for the Shannon Theory of the IEEE Transactions on Information Theory during 2013-2015.

The Peeling Decoder : Theory and Applications - Prof. Krishna Narayanan

Back to Top

Abstract: The peeling decoder is a simple greedy decoder that can be used to decode classes of codes defined on graphs, such as low density parity check (LDPC) codes and low density generator matrix codes, on the erasure channel. This deceptively simple decoder suffices to design capacity achieving coding schemes for the erasure channel. In addition, the peeling decoder can also be used to design optimal universal rateless codes as shown by Luby in the design of LT codes. In part I of this two-part tutorial, we will explain the main theoretical ideas behind the analysis of the peeling decoder and the design of optimal fixed rate and rateless codes for the erasure channel. We will also discuss how the peeling decoder can be used to decode generalized LDPC codes and product codes when used with non-erasure channels. We will conclude part I with a discussion of the relationship between channel coding and syndrome source coding for the compression of sparse sources.

The peeling decoder has been applied successfully not only to decoding codes on the erasure channel, but also in a variety of applications outside of main stream coding theory. In Part II of this tutorial, we will discuss applications of the peeling decoder to massive uncoordinated multiple access schemes, sparse Fourier transform computation and if time permits, to compressed sensing and group testing problems. Remarkably, the peeling decoder can be used to design optimal multiple access schemes in some cases and order-optimal algorithms for sparse transform computation and some sparse support recovery problems.

Lecturer’s Bio: Krishna Narayanan received the B.E. degree from Coimbatore Institute of Technology in 1992, M.S. degree from Iowa State University in 1994 and the Ph.D. degree in Electrical Engineering from Georgia Institute of Technology in 1998. Since 1998, he has been with the Department of Electrical and Computer Engineering at Texas A&M University, where he is currently the Eric D. Rubin professor. He has held visiting appointments at the University of Illinois at Urbana Champaign, Institut Eurecom, Indian Institute of Science and the University of California at Berkeley. His research interests are in coding theory, information theory, joint source-channel coding and signal processing with applications to wireless networks and data storage. His current research interests are in understanding the role of structured codes in multi-terminal information theory, universal codes for multi-user communication, spatially-coupled codes, polar codes, product codes and their variants, design of uncoordinated multiple access schemes and in exploring connections between sparse signal recovery and coding theory. He is passionate about technology-enabled teaching and innovative pedagogical approaches.

He was the recipient of the NSF career award in 2001. He also received the 2006 best paper award from the IEEE technical committee for signal processing for data storage for his work on soft decision decoding of Reed Solomon codes. He currently serves as an associate editor for coding techniques for the IEEE Transactions on Information Theory. He served as the area editor (and as an editor) for the coding theory and applications area of the IEEE Transactions on Communications from 2007 until 2011. In 2014, he received the Professional Progress in Engineering award given to one outstanding alumnus of Iowa State University each year under the age of 44. He was elected as Fellow of the IEEE for contributions to coding for wireless communications and data storage. He has won several awards within Texas A&M university including the 2012 college level teaching award.

Elements of index coding - Prof. Young-Han Kim

Back to Top

Abstract: Originally introduced to minimize the number of transmissions in satellite communication, the index coding problem provides a simple yet rich model for several important engineering problems in network communication, such as content broadcasting, peer-to-peer communication, distributed caching, device-to-device relaying, and interference management.

This lecture aims to provide a broad overview of this fascinating problem – arguably one of the most important open problems in network information theory – in four parts. First, we give a mathematical description of the problem and introduce basic properties of optimal index codes. Second, we discuss several coding schemes based on algebraic, graph-theoretic, and information-theoretic tools. Third, we establish performance bounds and discuss their implications in network information theory. Fourth, we explore the relationship between index coding and other problems such as network coding, distributed storage, and guessing games.

Lecturer’s Bio: Young-Han Kim received his B.S. degree with honors in electrical engineering from Seoul National University, Korea, in 1996 and his M.S. degrees in electrical engineering and in statistics, and his Ph.D. degree in electrical engineering from Stanford University in 2001, 2006, and 2006, respectively. In 2006, he joined the University of California, San Diego, where he is currently an Associate Professor in the Department of Electrical and Computer Engineering. His research interests are in information theory, communication engineering, and data science. He coauthored the book Network Information Theory (Cambridge Press 2011). He is a recipient of the 2008 NSF Faculty Early Career Development (CAREER) Award, the 2009 US-Israel Binational Science Foundation Bergmann Memorial Award, the 2012 IEEE Information Theory Paper Award, and the 2015 IEEE Information Theory Society James L. Massey Research and Teaching Award for Young Scholars. He served as an Associate Editor of the IEEE Transactions on Information Theory and a Distinguished Lecturer for the IEEE Information Theory Society. He is a Fellow of the IEEE.

Codes for Big Data: Error-Correction for Distributed Storage - Prof. Vijay Kumar

Back to Top

Abstract: Error-correcting codes in distributed storage are forced to address a new challenge, namely that of recovery of one or more individual symbols of a codeword as opposed to the customary recovery of the entire codeword. This is because in a storage system, different code symbols are stored on different nodes of the storage network and each node is a storage unit that is prone to failure or else is otherwise unavailable at the time when access to the node?s contents is desired.

Two classes of codes have sprung up to meet this challenge, namely regenerating codes and codes with locality. This talk will provide an overview of these two classes of codes, from their early beginnings to current developments. Quite apart from their application to storage, these two classes of codes also have served to enrich coding theory by giving rise to new classes of codes possessing additional and desirable properties.

Lecturer’s Bio: Prof. Kumar obtained his PhD from the University of Southern California (USC). Between 1983-2003, he was a full-time faculty in the EE department of USC. Since 2003, he has been a Professor in the ECE department of the Indian Institute of Science (IISc) Bangalore, where he is currently department Chairman and Tata Chem Chaired Professor of IISc. He also holds the position of Adjunct Research Professor at USC. He is an ISI highly cited author, an IEEE Fellow and a Fellow of the In- dian National Academy of Engineering. He is also co- recipient of the 1995 IEEE Information Theory Society Prize-Paper award, a Best-Paper award at the DCOSS 2008 conference on sensor networks and the IEEE Data Storage Best-Paper Award of 2011/2012. A pseudo- random sequence family designed in a 1996 paper co-authored by him now forms the short scrambling code of the 3G WCDMA cellular standard. He received the USC School of Engineering’s Senior Research Award in 1994 and the Rustum Choksi Award for Excellence in Research in Engineering in 2013 at IISc. He has been on the Board of Governors of the IEEE Information Theory Society since 2013, was a plenary speaker at ISIT 2014 and TPC Co-Chair of ISIT 2015.