Rate-distortion in near-linear time

Abstract—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(γ)−C2(γ). 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. I