Jalali and T. Weissman (Lossy Compression Data Compression)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(n)$

Space Complexity

$O(n)$? words

(Derived: Auxiliary data structures are H_k and m_k. H_k is just a singular value and is constant space, but m_k is a O(n)-size vector.)

Description

Gibbs sampler

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2008

Reference

https://web.stanford.edu/~tsachy/pdf_files/Lossy%20Source%20Coding%20via%20Markov%20Chain%20Monte%20Carlo.pdf