ECE287A: Universal Information Processing

Professor Young-Han Kim, UCSD, Winter Quarter 2013–14

Course Description

How can data be compressed with the minimum number of bits? How can an asset be invested in the stock market with the maximum growth of wealth? Or how can a future signal be predicted from the past with the least amount of distortion? Over the past four decades, several algorithms have been developed for such tasks that achieve essentially optimal performance with no prior knowledge about the statistical properties of the data.

This course studies theoretical foundations on such universal algorithms for probabilistic (random data) and deterministic (nonrandom data) settings, with the ultimate goal of developing a unified framework for universal information processing. We focus on three main topics–universal data compression (with or without distortion), universal portfolio, and universal prediction — and discuss mathematical properties of universal algorithms and their implementation issues. In addition, we briefly explore other topics such as universal filtering, denoising, and decoding in the final project.

Lectures

  • TuTh 5–6:20 pm, Atkinson Hall 4004

Course Requirements and Grading

  • Class participation: Each student is expected to scribe one or two lectures.

  • Midterm report: Each student should attend relevant sessions at the ITA Workshop, find an interesting theorem, and submit a complete statement of the theorem and its proof.

  • Final project: During the last week of the quarter, you should present an in-depth survey of a topic not covered in class. You can choose to be theoretical (more analysis) or practical (some implementation). Each project will be performed in a group of one or two students. The final report should be submitted by March 20. Suggested topics can be found here.

  • Grading: Class participation 1/4, midterm report 1/4, and final project 1/2. We reserve the right to change the weights at any moment for any reason.

Prerequisite

Working knowledge of probability.