A major challenge in signal processing, communication, and compression applications is the construction of schemes that approach the theoretical performance limits. The fact that a priori knowledge of source and channel characteristics is rarely available in practice necessitates that these schemes be universal. While it is clear that existing universal schemes for different problems share many common ingredients, thus far they have been considered mostly separately. This project develops a unified framework encompassing theoretical, algorithmic, and implementation aspects of the universality problem.
We address questions concerning universal schemes in problem areas ranging from denoising, Wyner-Ziv coding, joint source-channel coding, scanning and prediction, to reinforcement learning. We develop a unified framework for addressing such questions, which facilitates the construction of universal schemes for new problems, and leads to new insights on existing ones. On the more applied side, we are developing new algorithmic paradigms that have attractive complexity, and applying them in practice. We are also developing analytic tools for assessing the performance of the new algorithms.
This project tackled a major challenge in information processing, communication, and compression: the construction of schemes that approach the theoretical performance limits universally, that is, without a priori knowledge of source and channel characteristics. A unified framework encompassing theoretical, algorithmic, and implementation aspects of the universality problem was developed. A deep understanding of the principles underlying universal schemes was gained. Further, the unified framework developed led to the development of universal schemes for new and timely problems in network information processing, communication, and compression. New algorithmic paradigms have been developed, and led to the construction of new low-complexity and provably universally optimal practical schemes. In turn, these results have led to a new refined understanding of the fundamental tradeoffs between performance, complexity, and universality in both classical and new problems involving information processing, communication, and compression. A new generation of coding schemes for data compression, communication, denoising, and algorithms for other statistical signal processing tasks that significantly outperform existing architectures in practice, with solid theoretical performance guarantees, has been developed. The research was complemented by a strong educational component which included: 1) Teaching a unified approach to tackling problems in statistical signal processing and information theory when signal and/or noisy channel statistics or characteristics are not a-priori available. 2) Training students to harness practical methods for deriving schemes in the real-world manifestation of these problems. 3) Disseminating the new research findings. These objectives were achieved via activities that included new courses on universal schemes in information theory and in statistical signal processing, establishment of a seminar series as well as a workshop on the main themes of this project. Programs for mentoring undergraduate and high school students in subjects related to the themes of this project were developed and executed in coordination with Stanford’s Office of Research Experience for Undergraduates (REU) and Office of Science Outreach (OSO).
