University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Tuesday, September 7, 2004

DTC Seminar Series

Universal Types, Trees and Simulation of Individual Sequences


Gadiel Seroussi
Hewlett-Packard Laboratories

Tuesday, September 7, 2004
3:00 pm

402 Walter Library


Download slides (pdf 330 KB) We define the universal type class of an individual sequence xn, in analogy to the classical notion used in the method of types. Two sequences of the same length are said to be of the same universal type if and only if they yield the same set of phrases in the incremental parsing of Ziv and Lempel (1978). We show that the empirical probability distributions of any finite order k of two sequences of the same universal type converge, in the variational sense, as the sequence length increases. Consequently, the normalized logarithms of the probabilities assigned by any k-th order probability assignment to two sequences of the same type converge, for any k. We estimate the size of a universal type class, and show that its behavior parallels that of the conventional counterpart, with the LZ78 code length playing the role of the empirical entropy. We also characterize the number of different types for sequences of a given length n. The problem, which is equivalent to counting t-ary trees by path length, is interesting on its own, as it poses a very natural combinatorial question for which the answer was unknown. We present efficient procedures for enumerating the sequences in a universal type class, and for drawing a sequence from the class with uniform probability. As an application, we consider the problem of universal simulation of individual sequences. A sequence drawn with uniform probability from the universal type class of xn is a good simulation of xn in a well defined mathematical sense, a fact we illustrate by showing simulations of binary textures produced with the proposed scheme.

Seroussi presenting


Gadiel Seroussi is Director of Information Theory Research at Hewlett-Packard Laboratories. He received the B.Sc. degree in electrical engineeering, and the M.Sc. and D.Sc. degrees in computer science from Technion — Israel Institute of Technology, Haifa, Israel, in 1977, 1979 and 1981, respectively. From 1981 to 1987, Seroussi was with the faculty of the Computer Science Department at Technion. During the 1982-83 academic year, he was a Postdoctoral Fellow at the Mathematical Sciences Department of IBM T.J. Watson Research Center, Yorktown Heights, New York. From 1986 to 1988, he was a Senior Research Scientist with Cyclotomics Inc., Berkeley, California. He joined Hewlett-Packard Laboratories in Palo Alto, California, in 1988. Dr. Seroussi is a Fellow of the IEEE, cited "for contributions to the theory and practice of error correction and data compression algorithms and architectures." He is a co-author of the algorithm at the core of the recent JPEG-LS lossless image compression standard, as well as a contributor to the coding algorithm of the JPEG-2000 standard. His research interests include the mathematical foundations and practical applications of information theory, error correcting codes, data and image compression and cryptography. Dr. Seroussi has published numerous journal and conference articles in these areas, and is a co-author of the book Elliptic Curves in Cryptography, published by Cambridge University Press. He is an inventor in 22 granted U.S. patents, and more than 30 pending patent applications and invention disclosures.