Korada, Satish BabuUrbanke, Rudiger2009-08-112009-08-112009-08-11200910.1109/ITW.2009.5351488https://infoscience.epfl.ch/handle/20.500.14299/42030We consider lossy source compression of a binary symmetric source with Hamming distortion function. We show that polar codes combined with a low-complexity successive cancellation encoding algorithm achieve the rate-distortion bound. The complexity of both the encoding and the decoding algorithm is O(N\log(N)), where N is the blocklength of the code. Our result mirrors Arikan's capacity achieving polar code construction for channel coding.lossy source codingpolar codeslow-complexity algorithmsNCCR-MICSNCCR-MICS/CL1text::conference output::conference proceedings::conference paper