Rate-distortion in near-linear time

Ankit Gupta, Sergio Verdù, Tsachy Weissman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations


We present two results related to the computational complexity of lossy compression. The first result shows that for a memoryless source Ps with rate-distortion function R(D), the rate-distortion pair {R(D) + γ, D + ∈) can be achieved with constant decoding time per symbol and encoding time per symbol proportional to C1(γ)∈-C 2(γ). The second results establishes that for any given R, there exists a universal lossy compression scheme with O(ng(n)) encoding complexity and O(n) decoding complexity, that achieves the point (R, D(R)) asymptotically for any ergodic source with distortion-rate function D(.), where g(n) is an arbitrary non-decreasing unbounded function. A computationally feasible implementation of the first scheme outperforms many of the best previously proposed schemes for binary sources with blocklengths of the order of 1000.

Original languageEnglish (US)
Title of host publicationProceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
Number of pages5
StatePublished - 2008
Event2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, Canada
Duration: Jul 6 2008Jul 11 2008

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8101


Other2008 IEEE International Symposium on Information Theory, ISIT 2008
CityToronto, ON

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Rate-distortion in near-linear time'. Together they form a unique fingerprint.

Cite this