TY - GEN
T1 - Rate-distortion in near-linear time
AU - Gupta, Ankit
AU - Verdù, Sergio
AU - Weissman, Tsachy
PY - 2008
Y1 - 2008
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 -