(1 + ε)-approximate sparse recovery
Eric Price, David P. Woodruff
FOCS 2011
Shannon’s self-information of a string is generalized to its complexity relative to the class of finite-state-machine (FSM) defined sources. Unlike an earlier generalization, the new one is valid for both short and long strings. The definition is justified in part by a theorem stating that, asymptotically, the mean complexity provides a tight lower bound for the mean length of all so-called regular codes. This also generalizes Shannon’s noiseless coding theorem. For a large subclass of FSM sources a simple algorithm is described for computing the complexity. Copyright © 1986 by The Institute of Electrical and Electronics Engineers, Inc.
Eric Price, David P. Woodruff
FOCS 2011
Limin Hu
IEEE/ACM Transactions on Networking
Lixi Zhou, Jiaqing Chen, et al.
VLDB
Sabine Deligne, Ellen Eide, et al.
INTERSPEECH - Eurospeech 2001