ESE 523 Information TheoryESE 523 Information TheoryLectures 17-19Joseph A O’SullivanJoseph A. O SullivanSamuel C. Sachs ProfessorElectrical and Systems EngineeringElectrical and Systems EngineeringWashington University211 Urbauer Hall211 Urbauer Hall314-935-4173 [email protected] 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-19 [email protected] RDi i ThOutline: Rate-Distortion TheoryGaussian Rate-Distortion TheoryGaussian RateDistortion Theory Rate-Distortion TheoremProof of R-D TheoremProof of RD Theorem Achievability Converse Discussion of R-D TheoremOctober 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-192Rate-Distortion Theory:Mi iMotivation Underlying theory for audio, image, and video yg y , g,compression Theory underlying the standards: JPEG, MPEG, MP3, etc. Represent a signal with as few bits as possible, but allow a level of distortionRequires a notion of distortion: how close is the Requires a notion of distortion: how close is the representation of a signal to the original signal  Tradeoff fidelity for data storage bitsRate-Distortion: Minimize rate (bits per symbol) RateDistortion: Minimize rate (bits per symbol) subject to a distortion constraint Distortion-Rate: Minimize distortion subject to a rate constraintOctober 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-193rate constraintDi i F iDistortion Functions A distortion function or distortion measure is a nonnegative function of the source alphabet and reproduction alphabet, and is interpreted as the cost of a representationˆ:d+×→XX R A distortion function is bounded if its maximum value is finite. Examples:pHamming Distortionˆ0, if ˆ()xxdxx=⎧=⎨Erasure Distortion01ˆ()dxx∞⎡⎤⎢⎥()(,)ˆ1, if ˆˆ(,) ( )dxxxxEdXX PX X Perror=⎨≠⎩⎡⎤=≠=⎣⎦{} { }(,)10ˆInterpretation: 0,1 0, ,1dxxe=⎢⎥∞⎣⎦X= , X=October 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-194Di t rti F ti R lVl dDistortion Functions: Real-Valued2Squared-Error Distortion2ˆˆ(,) ( )Absolute-Error Distortionˆˆ(,)dxx x xdxx x x=−=−()(,)Distortion Induced by Relative Entropyˆˆ(,) (;)|(;)dDpqθθ θ θ= ii()I-divergence: induced by Poisson distributionsPoisson: ( ;PN k=) , 0,1,2,!kekkμμμ−==…()!!(,)logloglogNNkeNdE eμμμμμνμμν−⎡⎤⎢⎥==−−⎢⎥⎢⎥October 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-195()() g g g!NeNμνμμμνν−⎢⎥⎢⎥⎣⎦Example: Single Variable Distortion dLl d’ Al ihand Lloyd’s Algorithm For extensions and more details, see the work of Bob Gray d lland colleagues Bob Gray won the Shannon Award for 2008 Implementation in Matlab on subsequent slides{} {}222121min ( ) min min ( )nRnRiilnn n nn nllllJpx x dx px x dxξξξξ≤≤==−=−∑∫∫A{}(0)2() ()Initialize 0lllnnn n nlJpxxdxpxdxkξξξ⎡⎤∇= −⎢⎥⎢⎥⎣⎦∫∫AA{}{}()22() () ()(1) ()Initialize ,0:,|ik nnk nklliknnkkxx x iEX Xξξξξ+==−≤−∀⎡⎤⎣⎦AAOctober 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-196(1) ()|1. IterateknnkllEX Xkkξ+⎡⎤=∈⎣⎦=+ALl d’ Al rithLloyd’s Algorithmfunction [xp,seppoints]=lloydalg(pdf,xpoints,npoints)pdf pdf/sum(pdf);pdf=pdf/sum(pdf);niter=30;sepstep=(max(xpoints)-min(xpoints))/(npoints+4);seppoints=(min(xpoints)+3*sepstep):sepstep:(max(xpoints)-3*sepstep);pp ( ( p ) p p) p p ( ( p )pp)nsep=length(seppoints);kiter=0;xptot=[];septot=seppoints;septot=seppoints;while kiter<niter,kiter=kiter+1;xp=lloydpoints(pdf,xpoints,seppoints);seppoints=lloydsep(xp);xptot=[xptot;xp];septot=[septot; seppoints];endOctober 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-197endLloyd’s Algorithmfunction seppoints lloydsep(meanpoints)function seppoints=lloydsep(meanpoints)n=length(meanpoints);m=n-1;km=0;while km<mwhile km<m,km=km+1;seppoints(km)=(meanpoints(km)+meanpoints(km+1))/2;endfunction points=lloydpoints(pdf,xpoints,seppoints)n=length(seppoints)+1;kn=0;xmin=min(xpoints);while kn<n-1,kn=kn+1;ixp=find((xpoints<=seppoints(kn))&(xpoints>=xmin));xp=xpoints(ixp);points(kn)=sum(xp.*pdf(ixp))/sum(pdf(ixp));xmin=xpoints(max(ixp)+1);endkn=kn+1;October 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-198ixp=find(xpoints>=xmin);xp=xpoints(ixp);points(kn)=sum(xp.*pdf(ixp))/sum(pdf(ixp));x10-3Gaussian PDF; Reconstruction and Separation PointsLloyd’s Algorithm: GiC-4 -2 0 2 400.51x 10x10-3Gaussian Case-4 -2 0 2 400.51x 10x10-3-4 -2 0 2 400.51x 10x10-3-4 -2 0 2 400.51x 10Values of Random Variablex=-4:0 002:4;a ues o a do a ab ex=4:0.002:4;x2=x.^2;pdf=exp(-x2/2)/sqrt(2*pi);pdf=pdf/sum(pdf);npoints=4;October 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-199npoints=4;[xp,seppoints]=lloydalg(pdf,x,npoints)RtDi t rti Tr d ffRate-Distortion Tradeoff Points from 13 to 303, 10-1Distortion vs. Number of Pointssteps of 10 Log-log plot: log distortion vs. rate10-2n On this scale, the curve is nearly linear:1.8 0.82(2)RD−≈-410-3Distortion The exponent is suboptimal2(2)D≈222RDσ−=12310-510-42optDσ=101102103Number of PointsOctober 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-1910ARDi i C dA Rate-Distortion Code An (2nR,n) code consists of An index set {1, 2, …, 2nR}. An encoding function fn: Xn Æ {1, 2, …, 2nR}  A decoding function gn: {1, 2, …, 2nR}Æ Xn^gn{}The (average per-symbol) distortion between two vectors is1ˆˆ(,) (,)nnniidx x dx x=∑ˆ:d+×→XX R()()1()(,) (,)The expected distortion for a rate-distortion code is() (()) (( ))iiinnnn nnnDdfEdXfX=⎡⎤∑∑:d×→XX R()()()(),(()),(( ))Codebook: nnnnnn nnnn nnxDpxdxgfxEdX g f X∈⎡⎤==⎣⎦=∑XC{}(1), (2), , (2 )nRnn ngg g…October 24-29, 2013 J. A. O'Sullivan ESE 523 Lectures 17-1911{}1Assignment Regions: ( ) : ( )nn nnnfi x fx i−=∈ =XA hi bilit d Th rAchievability and Theorem  A rate-distortion pair (R,D) is achievable if there exists a sequence of (2nRn) codes such that sequence of (2nR,n) codes such that lim D(n)≤ D as n Æ ∞. The rate-distortion region is the closure of the set of achievable rate-distortion pairsachievable rate-distortion pairs. The rate-distortion function R(D) is the infimum of rates Rsuch that for fixed D, (R,D) is in the rate-distortion region. ThTh tditti f ti f iid Theorem:The rate-distortion function for an i.i.d. source and bounded distortion function equals ˆ() min(; )RD I X X=ˆ(|)ˆ(,)() min(; ) ˆˆsubject to ( ) ( | ) ( , )pxxxxRD I X Xpxpxxdxx D=≤∑October 24-29, 2013 J. A.