CIF: Small: Fast Rate-Efficient Codes for Data Compression and Transmission via Sparse Regression

现代通信网络在规模和复杂程度上不断增长。新的应用程序要求这些网络可靠、计算效率高且延迟小。为了满足这些要求，具有低复杂度、速率高效的通信和压缩代码是至关重要的。自从香农的基本结果以来，已经有一系列的活动来设计实现容量的、计算高效的编码方案。对于信道编码问题，直到20世纪90年代初才实现了容量实现码。类似地，许多好的量化器设计被开发用于有损压缩，但不幸的是，这些低复杂度的代码没有一个能够被证明达到率失真界限。信息论结果和代码构建之间的分歧在网络通信问题中更加明显。尽管对几种网络模型的信息论限制进行了严格的描述，但针对这些问题的最佳实用编码仍不能满足容量限制。该研究涉及为高斯源和信道开发计算高效的编码。为此，我们利用了高维稀疏回归的最新进展。这是第一批可证明达到高斯源和信道的信息论极限码的低复杂度代码。本研究项目的主要目标是：(1)确定稀疏回归码在各种通信理论环境下的基本极限；(2)为我们的稀疏回归码开发低复杂度的编解码方案。该部分借鉴了函数逼近和稀疏信号恢复的思想。该项目还为在通信理论、数据压缩、统计学和网络等学科培训研究生和博士后研究人员提供了机会。

Modern communication networks are constantly growing in size and sophistication. New applications require these networks to be reliable, computationally efficient, and have small latency. To meet these demands it is critical to have low-complexity, rate-efficient codes for communication and compression. Since Shannon's fundamental results, there has been a flurry of activity to design capacity achieving, computationally efficient coding schemes. For the channel coding problem, it was not until the early 1990s that capacity achieving codes were implemented. Similarly, many good quantizer designs were developed for lossy compression, but unfortunately none of these low-complexity codes provably attain the rate-distortion bound. The divergence between information-theoretic results and code construction is even more pronounced in network communication problems. Despite a sharp characterization of information-theoretic limits for several network models, the best practical codes for these problems fall short of the capacity limits.This research involves the development of computationally efficient codes for Gaussian sources and channels. To this end we leverage recent advances in high-dimensional sparse regression. These are the first low-complexity codes that provably attain the information-theoretic limits codes for Gaussian sources and channels. The main objectives of this research project are: (1) Determining the fundamental limits of sparse regression codes in a variety of communication theoretic settings; (2) Developing low-complexity encoding and decoding schemes for our sparse regression codes. This part of the project draws on ideas from function approximation and sparse signal recovery. The project also provides an opportunity for training graduate students and postdoctoral researchers in the disciplines of communication theory, data compression, statistics and networks.