### 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 C_{1}(γ)∈^{-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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008 |

Pages | 847-851 |

Number of pages | 5 |

DOIs | |

State | Published - Sep 29 2008 |

Event | 2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, Canada Duration: Jul 6 2008 → Jul 11 2008 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

ISSN (Print) | 2157-8101 |

### Other

Other | 2008 IEEE International Symposium on Information Theory, ISIT 2008 |
---|---|

Country | Canada |

City | Toronto, ON |

Period | 7/6/08 → 7/11/08 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Rate-distortion in near-linear time'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008*(pp. 847-851). [4595106] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2008.4595106