On sequential universal coding of sequences with limited amount of training data
I. Sutskover, J. Ziv · 21st IEEE Convention of the Electrical and Electronic Engineers in Israel. Proceedings (Cat. No.00EX377) · 2002
The problem of universal coding in the non-asymptotic regime is investigated. In a forthcoming paper, some non-asymptotic lower bounds on the achievable compression are proven by Ziv for the class of stationary sources and a class of admissible algorithms. To these lower bounds we match an achievable upper bound by construction of a proper algorithm. We also extend our results to a case where some prior assumptions can be incorporated into universal algorithms, creating algorithms that are "almost universal".