Achievable complexity-performance tradeoffs in lossy compression

We present several results related to the complexity-performance tradeoff in lossy compression. The first result shows that for a memoryless source with rate-distortion function $R(D)$ and a bounded distortion measure, the rate-distortion point $(R(D)+\gamma,D+\varepsilon)$ can be achieved with constant decompression time per (separable) symbol and compression time per symbol proportional to $(\lambda_1/\varepsilon)^{\lambda_2/\gamma^2}$, where $\lambda_1$ and $\lambda_2$ are source dependent constants. The second result establishes that the same point can be achieved with constant decompression time and compression time per symbol proportional to $(\rho_1/\gamma)^{\rho_2/\varepsilon^2}$. These results imply, for any function $g(n)$ that increases without bound arbitrarily slowly, the existence of a sequence of lossy compression schemes of blocklength $n$ with $O(ng(n))$ compression complexity and $O(n)$ decompression complexity that achieve the point $(R(D),D)$ asymptotically with increasing blocklength. We also establish that if the reproduction alphabet is finite, then for any given $R$ there exists a universal lossy compression scheme with $O(ng(n))$ compression complexity and $O(n)$ decompression complexity that achieves the point $(R,D(R))$ asymptotically for any stationary ergodic source with distortion-rate function $D(\cdot)$.