Universal random number generation from finite memory sources

Mon, Oct. 26

3-4PM

400 Cory

3-4PM

400 Cory

Procedures for transforming non-uniform random sources into “perfectly random”
ones have been a subject of great interest in statistics, information theory,
and computer science for decades. Various assumptions on the nature of the input
process, what is known about it, and how the samples are accessed, give raise to
different settings for the problem. In this talk, we study this problem, both
in the fixed-to-variable (FV) and variable-to-fixed (VF) length regimes, in a
universal setting in which the input is a finite memory source of arbitrary
order and unknown parameters. After presenting the problem in a common
framework of universal schemes for tasks such as data compression and
simulation, we apply the method of types to characterize (essentially unique)
optimal universal random number generators that maximize the expected output
(respectively, minimize the expected input) length in the FV (respectively,
VF) length case. We precisely characterize, up to an additive constant, the
corresponding expected lengths, which include second-order terms similar to
those encountered in universal data compression and simulation. Finally, we
consider a "twice-universal" setting, in which the Markov order of the input
source is also unknown.

(Based on joint work with Gadiel Seroussi.)

Bio: Marcelo Weinberger is a Distinguished Scientist with the Center for Science of Information, currently residing at UC Berkeley. Marcelo retired in 2013 from Hewlett-Packard Laboratories, Palo Alto, CA, where he also was a Distinguished Scientist and led the Information Theory Research group. Prior to that, he was a Visiting Scientist at IBM Almaden Research Center, San Jose, CA, and a faculty at the Department of Electrical Engineering at Technion—Israel Institute of Technology, Haifa, Israel, for the 1991–1992 academic year. Marcelo received the Electrical Engineer degree from the Universidad de la República, Montevideo, Uruguay, and the M.Sc. and D.Sc. degrees from Technion, both in electrical engineering. His research interests include source coding, sequential decision problems, statistical modeling, and image compression. Marcelo is a coauthor of the algorithm at the core of the JPEG-LS lossless image compression standard, and was an editor of the standard specification. He also contributed to the coding algorithm of the JPEG2000 image compression standard. He is a Fellow of the IEEE and a co-recipient of the 2006 IEEE Communications/Information Theory Societies Joint Paper Award (for the "DUDE" algorithm).

(Based on joint work with Gadiel Seroussi.)

Bio: Marcelo Weinberger is a Distinguished Scientist with the Center for Science of Information, currently residing at UC Berkeley. Marcelo retired in 2013 from Hewlett-Packard Laboratories, Palo Alto, CA, where he also was a Distinguished Scientist and led the Information Theory Research group. Prior to that, he was a Visiting Scientist at IBM Almaden Research Center, San Jose, CA, and a faculty at the Department of Electrical Engineering at Technion—Israel Institute of Technology, Haifa, Israel, for the 1991–1992 academic year. Marcelo received the Electrical Engineer degree from the Universidad de la República, Montevideo, Uruguay, and the M.Sc. and D.Sc. degrees from Technion, both in electrical engineering. His research interests include source coding, sequential decision problems, statistical modeling, and image compression. Marcelo is a coauthor of the algorithm at the core of the JPEG-LS lossless image compression standard, and was an editor of the standard specification. He also contributed to the coding algorithm of the JPEG2000 image compression standard. He is a Fellow of the IEEE and a co-recipient of the 2006 IEEE Communications/Information Theory Societies Joint Paper Award (for the "DUDE" algorithm).

UC Berkeley Networking

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016