TY - GEN

T1 - Rate-distortion in near-linear time

AU - Gupta, Ankit

AU - Verdù, Sergio

AU - Weissman, Tsachy

PY - 2008/9/29

Y1 - 2008/9/29

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=52349116182&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=52349116182&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2008.4595106

DO - 10.1109/ISIT.2008.4595106

M3 - Conference contribution

AN - SCOPUS:52349116182

SN - 9781424422579

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 847

EP - 851

BT - Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008

T2 - 2008 IEEE International Symposium on Information Theory, ISIT 2008

Y2 - 6 July 2008 through 11 July 2008

ER -