On the asymptotic distribution of the errors in ve

ThisworkwassupportedbyNSFGrantNCR-9105647.August16,1995OntheAsymptoticDistributionoftheErrorsinVectorQuantizationDavidL.NeuhoffElectricalEngineeringandComputerScienceDepartmentUniversityofMichiganAnnArbor,MI48109ABSTRACTInarecentpaper,LeeandNeuhofffoundanasymptoticformulaforthedistributionofthelengthoftheerrorsproducedbyavectorquantizerwithmanyquantizationpoints.Thisdistribu-tiondependsonthesourceprobabilitydensity,thequantizerpointdensityandthequantizershapeprofile.(Thelattercharacterizestheshapesofthequantizationcellsasafunctionofposition.)Thepurposeofthispaperistogivearigorousderivationofthisformulabyidentifyingpreciseconditionsunderwhichitisshownthatifasequenceofvectorquantizerswithagivendimensionandanincreasingnumberofpointshasspecificpointdensitiesandspecificshapeprofilesconvergingtoamodelpointdensityandamodelshapeprofile,respectively,thenthedistributionofthelengthofthequantizationerror,suitablynormalized,convergestotheaforementionedformula,withthemodelpointdensityandthemodelshapeprofilesubstituted.INDEXTERMSAsymptoticquantization,quantizationerror,high-ratequantization,vectorquantization,errordistribution,errordensity,pointdensity,shapeprofile,shapefunction,inertialprofile.1I.INTRODUCTIONWhenak-dimensionalvectorquantizerwithquantizationruleQisappliedtoarandomvec-torX=(X1…Xk),theresultingquantizationerroristhek-dimensionalrandomvectorU=X-Q(X).Inarecentpaper,LeeandNeuhoff[1]foundanapproximateformulafordistributionofthelengthofthiserror,suitablynormalized,thatapplieswhenthenumberofquantizationpoints,N,islarge.Specifically,theyconsidered,thenormalizederrorlengthWNΔ=N1/k||X-Q(X)||,andshowedthatwhenNislarge,theprobabilitydensityofWNis,approximately,pWN(w)≅kVkwk-1∫pX(x)λ(x)g(x,wλ(x)1/k)dx,w≥0,(1.1)whereVkisthevolumeofak-dimensionalspherewithunitradius,pX(x)isthesourceprob-abilitydensity,λ(x)isthequantizerpointdensity,whichindicatesthesizesofthecellsinthevicinityofx,andg(x,r)isthequantizershapeprofile,whichreflectstheshapesofthecellsinthevicinityofx.Precisedefinitionsofλ(x)andg(x,r)willbegivenlater.Theresultin[1]wasderivedusinginformalapproximationargumentssuchas∫Ff(x)dx≅vol(F)f(x')foranypointx'inF.Thepurposeofthepresentpaperistoputthisresultonafirmfoundationbygivingcarefuldefinitionsofpointdensityandshapeprofileandbyfindingpreciseconditionsunderwhichitispossibletoshowthatifasequence{QN}ofvectorquantizersindimensionk,indexedbythenumberofpoints,haspointdensitiesconverginginacertainsensetoagivenλ(x)andshapeprofilesconverginginacertainsensetoagiveng(x,r),thentheprobabilitydistributionfunctionofWNconvergestoFW(w)=kVk∫RkpX(x)∫0wλ(x)1/kg(x,u)uk-1dudx.(1.2)Differentiatingtheaboveyieldstheright-handsideof(1.1).2Whenthetermspointdensityorshapeprofileareused,theymaymeanoneoftwothings:acharacteristicofaspecificvectorquantizer;oramodelcharacteristicthatagivenquantizerapproximatesoraspiresto.Forexample,thepointdensityλ(x)ofaspecificvectorquantizerisusuallydefinedtobethereciprocalofNtimesthevolumeofthecellinwhichxlies.Ontheotherhand,itisknown[2]thatthepointdensitythatasymptoticallyminimizesmeansquarederrorisλ(x)=pX(x)k/(k+2)∫RkpX(x)k/(k+2)dx.Clearly,noquantizercouldhavepointdensitygivenexactlybytheaboveformula.Neverthelessitrepresentsthepointdensitytowhichquantizersaspire.Thepointofthisdiscussionisthatitisnecessarytointroducetwonotionsofpointdensity(andshapeprofile):thespecificpointdensity(shapeprofile)characterizesaspecificquantizer;andthemodelpointdensity(shapeprofile)isthetargettowhichthequantizeraspires.Themainresultofthispaper,Theorem1,showsthatwhenasequenceofquantizers{QN}hasspecificpointdensitiesandshapeprofilesconvergingtoagivenmodelpointdensityandshapeprofile,thenthedistributionfunctionofWNconvergesto(1.2).AnattempthasbeenmadetomakeTheorem1asgeneralaspossiblebymakingitsconditionsasweakaspossible.Alongtheselines,itisassumedthatthesourcerandomvectorisabsolutelycontinuouswithadensity,butthereisnoassumptionthatthedensitybeboundedorhaveboundedsupport.Thereisalsotherequirementthatthedensitybepiecewisecontinuous.Inregardtothemodeofconvergenceofthespecificpointdensities,mentionedinthepreviousparagraph,weassumethatthisconvergenceisinprobability,asopposedtosureoralmostsureconvergence.Amongotherthings,thisindicatesthatitdoesnotmatterwhatthequantizersdoinregionsoutsidethesupportofthesourcedensity.Convergenceinprobabilityisalsorequiredforthespecificshapeprofiles,butinaddition,itisnecessarytoaccountforhowconvergencetakesplaceforthevariousvaluesoftheadditionalargumentring(x,r).3ThestatementandproofofTheorem1isthetopicoftheSectionIII.SectionIIgivesthedefinitionsintermsofwhichtheresultisstated,andSectionIVpresentsseverallemmasthatareneededintheproof.II.PRELIMINARIESTheprimarycharacteristicsofavectorquantizer(VQ)areitsdimensionk,sizeN∞,partitionSN={SN,1,…,SN,N}ofk-dimensionalEuclideanspaceℜkintoNcells,andcodebookCN={yN,1,…,yN,N}consistingofNpointsinℜk.Itassumedthatallcellshavenonzerovolume.LetSN,xdenotethecellcontainingx,whichisasmallbutconvenientabuseofnotation.Thequantizerwillbedenoted(SN,CN).Becausewedealwithsequencesofquantiz