EE Systems Seminar

Thursday January 28, 2016 4:00 PM

Excess-distortion analysis of lossy compression

Speaker: Yuval Kochman, School of Computer Science and Engineering, Hebrew University of Jerusalem
Location: Moore B280
<!-- /* Font Definitions */ @font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;} @font-face {font-family:Cambria; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} @page Section1 {size:8.5in 11.0in; margin:1.0in 1.25in 1.0in 1.25in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.Section1 {page:Section1;} -->

<!-- /* Font Definitions */ @font-face {font-family:Cambria; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} @page Section1 {size:8.5in 11.0in; margin:1.0in 1.25in 1.0in 1.25in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.Section1 {page:Section1;} -->

 

 

Abstract:

Finite-blocklength lossy compression is traditionally treated by setting a distortion threshold. Then, the excess-distortion probability is measured over a block of data that is processed by a fixed-rate quantizer. Various works analyze the tradeoffs in this setting. Specifically, for a fixed excess-distortion probability, the excess rate needed above the rate-distortion function decays inversely proportional to the square root of the blocklength, according to the second-order (dispersion) analysis.

 

From an operational point of view, the blocklength over which excess-distortion probability is measured (which we call fidelity blocklength) need not necessarily be equal to the quantizer dimension. For example, if the source emits a long sequence, we may still wish to process shorter sub-sequences for reasons such as delay and complexity. We find that indeed the quantizer dimension may be taken to be much shorter than the fidelity blocklength without sacrificing asymptotic performance, thus the dispersion expression does not predict the needed quantizer dimension. Moreover, if we go in the other direction, i.e., take the fidelity blocklength to be shorter than the quantizer dimension, we show that surprisingly performance improves! This is due to the non-convexity of the excess-distortion probability measure.

 

We suggest to avoid these troubling phenomena by making two changes to the problem definition. First, we replace blocklength by a collection of different quantities, each representing a distinct operational consideration. And second, we replace the binary measure of excess-distortion probability by a continuous one, that keeps growing with the distortion above the threshold. For this new problem, we give the second-order (dispersion) characterization.

 

Based in part on joint work with Gregory Wornell (MIT).

 

Bio:

Yuval Kochman received his B.Sc. (cum laude), M.Sc. (cum laude) and Ph.D. degrees from Tel Aviv University in 1993, 2003 and 2010, respectively, all in electrical engineering. During 2009-2011, he was a Postdoctoral Associate at the Signals, Informtion and Algorithms Laboratory at the Massachusetts Institute of Technology (MIT), Cambridge, MA, USA. Since 2012, he has been with the School of Computer Science and Engineering at the Hebrew University of Jerusalem. 

Series Electrical Engineering Systems Seminar Series

Contact: Shirley Slattery at x4715 shirley@systems.caltech.edu