Universal Algorithms in Information Theory

General data

Course ID:	1000-1S20UAI
Erasmus code / ISCED:	11.1 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Mathematics The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Universal Algorithms in Information Theory
Name in Polish:	Uniwersalne algorytmy w teorii informacji
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	Seminars for Mathematics
ECTS credit allocation (and other scores):	(not available) Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	English
Type of course:	elective seminars
Prerequisites (description):	The seminar is appropriate for 2nd stage studies students and PhD students who have taken a course in probability theory. Background in information theory and ‏dynamical systems is not required but may be helpful.
Short description:	A reading seminar on universal algorithms in information theory from a theoretical point of view as well as related subjects in the theory of dynamical systems.
Full description:	Information theory is a branch of (applied) mathematics which has many applications in science and especially in computer science and electrical engineering. The field studies communication of information between a source and destination taking into account inter alia quantification, coding, noise reduction, decoding and storage. The seminar will focus on universal algorithms in information theory from a theoretical point of view as well as related subjects in the theory of dynamical systems. In order to illustrate the concept of universality and its relation to the theory of dynamical systems, consider the famous 1977 Lempel-Ziv universal lossless data compression algorithm which in finite versions is the basis for many popular data compression packages. This algorithm allows to almost surely code a message of length n (in the asymptotic regime n-->infinity) generated from an unknown arbitrary ergodic process by at most nh + o(n) binary digits. Moreover no other algorithm can perform better asymptotically. Several proofs of this remarkable fact have been given. One proof by Ziv uses tools from topological dynamics. Another proof by Ornstein and Weiss uses tools from ergodic theory
Bibliography:	Paul C. Shields, The ergodic theory of discrete sample paths. Vol. 13. American Mathematical Soc., 1996. Robert M. Gray, Entropy and information theory. Springer Science & Business Media, 2011. Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. IEEE Transactions on information theory 23(3): 337-343, 1977. Jacob Ziv. Coding theorems for individual sequences. IEEE Transactions on Information Theory 24(4): 405-412, 1978. Donald S. Ornstein and Benjamin Weiss. Entropy and data compression schemes. IEEE Transactions on Information Theory, 39(1):78–83, 1993. Donald S. Ornstein and Paul C. Shields. Universal almost sure data compression. The Annals of Probability 18(2): 441-452, 1990. Amos Lapidoth and Jacob Ziv. On the universality of the LZ-based decoding algorithm, IEEE Transactions on Information Theory 44(5):1746–1755, 1998. Shirin Jalali and H. Vincent Poor. Universal compressed sensing for almost lossless recovery. IEEE Transactions on Information Theory, 63(5):2933–2953, 2017. Yonatan Gutman and Masaki Tsukamoto. Embedding minimal dynamical systems into Hilbert cubes. Inventiones Mathematicae, 2020. Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú, and Marcelo J. Weinberger. Universal discrete denoising: Known channel. IEEE Transactions on Information Theory, 51(1):5–28, 2005. Meir Feder, Neri Merhav, and Michael Gutman. Universal prediction of individual sequences. IEEE transactions on Information Theory, 38(4):1258–1270, 1992. Boris Ryabko. Compression-based methods for nonparametric prediction and estimation of some characteristics of time series. IEEE Transactions on Information Theory 55(9): 4309-4315, 2009.
Learning outcomes:	Acquire a deep understanding of at least one article related to the theme of the seminar as well as the ability to teach its essentials to an audience.
Assessment methods and assessment criteria:	Presentation of at least one paper on a given topic during the semester. The presentation may take several meetings.

This course is not currently offered.

Course descriptions are protected by copyright.
Copyright by University of Warsaw.