Introduction

Motivation

This course focuses on algorithms in signal processing and communications. When training data is available in such systems, we can process the data by first training onhistorical data and then running a Bayesian scheme, which relies on the statistics being known. A similar Bayesian approach can also be used when thestatistics are approximately known.

For example, consider lossy image compression. It is well known that wavelet coefficients of images have a distribution that resembles Laplace,

and the coefficients are approximately independent and identically distributed (i.i.d.). A well-known approach to lossy image compression is to first compute the wavelet coefficients and thencompress them using a lossy compressor that is designed for Laplace i.i.d. coefficients  [link] . In this approach, the trainingconsists of the body of art that realizes that wavelet coefficients are approximately Laplace i.i.d., and the Bayesan algorithm is a lossy compressor that is designed for this distribution.

However, sometimes the statistics of the input (often called the source ) are completely unknown,there is no training data, or there is great uncertainty in the statistics. For example, in lossless data compression,we do not know whether a file is an executable, source code, a DNA sequence, contains financial transactions, is text, etc.And even if we know that the file contains text, it has been noted that even different chapters that appear in the same book that is written by the same authormay contain different statistics.

For this latter set of problems, the Bayesian approach is useless, because there is no training data. A good alternative approach to Bayesian algorithms is to use universal algorithms   [link] , [link] . These algorithms have good performance irrespectiveof statistics. In fact, in some cases, these algorithms can achieve (with equality) the theoretically optimum performance in an appropriate asymptotic framework.

In lossless compression , universal algorithms have had great impact. For example, the Lempel-Ziv family of algorithms  [link] , [link] asymptotically achieve the entropy rate  [link] , [link] , which is the best possible compression ratio achievable in lossless compression, despite not knowing the input statistics.Additionally, the Lempel-Ziv algorithms allow efficient implementation.

Overview

The goal of this course is to study universal algorithms, starting from the well-trodden material in lossless compression, and later discussing universal algorithms in other areas of communicationsand signal processing. Let us overview the material studied during the course. We begin in [link] with a review of some information theory material, including typical sequences and source coding, in order to provide sufficient background. Next, [link] statistical models for data will be described. [link] then presents techniques for universal lossless compression of parametric sources. One approach to universal compression of parametric sources is minimum description length, which compresses the data in order to minimize for the sum of the complexity of the model and the complexity of the data given the parameters of the model. Minimum description length has been used with context tree models to provide universal contextual prediction; context tree approaches are detailed in [link] . We then switch gears in [link] and move beyond lossless compression; universal lossy compression and signal reconstruction are described in detail. Finally, [link] describes Lempel-Ziv algorithms for universal lossless compression based on parsing an input sequence. For convenienve, notation is summarized in [link] .

This manuscript is a work in progress, and we expect to expand and improve it during future teachings of the course.