Rate-distortion in near-linear time

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) + gamma, D + isin) can be achieved with constant decoding time per symbol and encoding time per symbol proportional to C₁(gamma)isin^-C2^(gamma). 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.