QUANTIZATION AND ERASURES IN FRAME REPRESENTATIONS by PETROS T. BOUFOUNOS B.Sc. Economics,MassachusettsInstituteofTechnology(2000), B.Sc. EECS, MassachusettsInstituteofTechnology(2002), M.Eng. EECS, MassachusettsInstituteofTechnology(2002). SubmittedtotheDepartmentofElectricalEngineeringand ComputerScience in partialfulfillmentoftherequirementsfor thedegreeof DoctorofScience inElectrical Engineeringand ComputerScience at the MASSACHUSETTS INSTITUTE OFTECHNOLOGY January2006 c MassachusettsInstituteofTechnology2006. Allrightsreserved. (cid:13) Author DepartmentofElectricalEngineeringand ComputerScience January 20,2006 Certified by AlanV. Oppenheim FordProfessorofEngineering Thesis Supervisor Accepted by ArthurC. Smith Chairman,Department Committeeon GraduateStudents 2 QuantizationandErasures inFrameRepresentations by Petros T. Boufounos SubmittedtotheDepartmentofElectricalEngineering andComputerScience onJanuary20,2006, inpartialfulfillmentofthe requirements forthedegreeof DoctorofScienceinElectricalEngineering andComputerScience Abstract Frame representations, which correspond to overcomplete generalizations to basis expansions, are often used in signal processing to provide robustness to errors. In this thesis robustness is provided through the use of projections to compensate for errors in the representation coefficients, with spe- cific focus on quantization and erasure errors. The projections are implemented by modifying the unaffected coefficients using an additive term, which is linear in the error. This low-complexity im- plementation onlyassumes linear reconstruction using apre-determined synthesis frame, andmakes noassumption onhowtherepresentation coefficientsaregenerated. Inthecontextofquantization,thelimitsofscalarquantizationofframerepresentationsarefirstexam- ined, assuming the analysis is using inner products with the frame vectors. Bounds on the error and thebit-efficiencyarederived,demonstratingthatscalarquantizationofthecoefficientsissuboptimal. As an alternative to scalar quantization, a generalization of Sigma-Delta noise shaping to arbitrary frame representations is developed by reformulating noise shaping as a sequence of compensations forthequantization errorusingprojections. Thetotalerrorisquantifiedusingboththeadditivenoise model of quantization, and a deterministic upper bound based on the triangle inequality. It is thus shown that the average and the worst-case error is reduced compared to scalar quantization of the coefficients. The projection principle is also used to provide robustness to erasures. Specifically, the case of a transmitter that is aware of the erasure occurrence is considered, which compensates for the erasure error by projecting it to the subsequent frame vectors. It is further demonstrated that the transmitter canbesplittoatransmitter/receiver combination thatperformsthesamecompensation, butinwhich only the receiver is aware of the erasure occurrence. Furthermore, an algorithm to puncture dense representations inordertoproducesparseapproximateonesisintroduced. Inthisalgorithmtheerror duetothepuncturingisalsoprojectedtothespanoftheremainingcoefficients. Thealgorithmcanbe combined with quantization to produce quantized sparse representations approximating the original denserepresentation. ThesisSupervisor: AlanV.Oppenheim Title: FordProfessorofEngineering 3 4 Acknowledgments I oweagreat debt, monetary, emotional, and intellectual to myparents, Theodosis and Maria. They made sure I brushed my teeth every night, ate my food, and had fun. They tried to make sure I did my homework while inschool but Imanaged to cut some corners with that... sorry mom! Iguess it does not matter now; theworkload atM.I.T.morethan made upformyprior slackness. Myparents didn’t teach meeverything I know, but made sure I get the best education they could provide. They are the best credit card, moral guidance, and emotional support I could ever have. Their advice is always valuable and I would never be here without it. Ihope I willbe able to repay them for all the greatthingstheyhavedoneforme. Idedicate thisthesistothem. Myintellectual mentor these past fewyears in MITis myresearch advisor, AlOppenheim. Iwould like to thank him for taking me when I was “green” and letting me mature seemingly on my own. Aliskindofmentorwholetsyoudiscovertheacademic world,butheisalwaystheretoprotect you fromfalling. Heisalwaysinvolved inresearchbutneverdictatesaproblemtobesolved,andIthank himforthat. Ilookforwardtofuturecollaboration, andIhopeIwillbeasgoodamentorandasgood ateacherasAlis. Of course, this thesis would not have been possible without the involvement of the other two com- mitteemembers,GeorgeVergheseandVivekGoyal. Theircommentsandtheirquestions throughout the meetings and during the writing process madethis thesis significantly better. George and Vivek, thankyouforallthetimeandeffortyoudevotedintoguidingme. Many thanks to all the past and present members of the groups at the 6th floor of building 36, espe- cially the DSPG group, for making sure there are enough intellectually stimulating (or not) conver- sations to keep me busy. Wade, Yonina, Andrew, Charles and Maya, made me feel welcome in the 5 group when I first joined. After they were gone, Sourav, little Al, Zahi, Joonsung, Tom, Melanie, Joe, Ross, Matt, Denis, and, of course, Charlie were always there to chat, answer my questions, or just keep me company in the office. Sourav receives an honorable mention, being my officemate, andbeingtheonewhotolerated allmyrandom ramblingwhenIwaswebsurfing, readinge-mail,or (occasionally) doing research. Special thanks also goes toAlecia andEric, thetwoDSPGassistants while I was here. Thanks to them all the administrative details were covered and wehad nothing to worryabout. Iamgratefultomyacademicadvisor,GregWornell,formakingsureIdonotfallbehindacademically and for guiding me through the course selection problems. He always had great advice on picking courses and making difficult academic and scheduling choices. Of course some of that would not have been possible without his assistant, Tricia, who also managed to keep the 6th floor well fed everyWednesday withsandwiches fromtheAreaIfacultymeeting. ThepeopleattheMitsubishiElectricResearchLab,especiallyParisSmaragdistogetherwithBhiksha Raj, provided two valuable summer experiences. My summer internships there were very stimulat- ing, productive, and fun. They were distracting enough to return to MIT with a fresh view on my researchandaclearmind,butnottoodistractingtodelaymyresearch. MyexperienceinMERLwas invaluable. Grad school is not all about work, and my friends reminded me of that quite often. Lia Kolokouri provided me withindispensable emotional support and made sure I waswell-nourished—especially with carbohydrates—while I was writing my thesis. Several waves of Boston-based Greek (or hon- orary Greek) friends helped me maintain my Greek language skills, especially in parties or clubs. Special thanks in noparticular order to Paris, Karrie, Elias, Carl, Nicholas, Olga, Andy,Sav, George Z.,Natasa,MariaK.,Elina,TheodoreK.(alsoforhisproofreadingskills),AnnaS.,CostasP.,George C., Angelina, George K., Peggy, Mari, Rozita, Panos, Michalis, Marianna, Alexandra, Polina, Yan- nis K., Thetis, Hip, Apostolos, Dafni, Anastasia, my cousins (especially Costas, Vicky, Eleni, and Dimitris), and everyone else I am forgetting, including the extended kb group (you know who you are...). Ontheinternational side,IthankArin,Joanna, Kavita,Mike,Daniele, Ozge,andtheremain- ing happybunch. Life in Boston and vacations in Greece would not have been the same without my friends. I would also like to thank everyone who participated in my small polls on the thesis template. I probably managed to disappoint all of you with the final thesis appearance, but I did take every opinion intoconsideration. Youmayliketheresultorblameitto“design bycommittee.” Ihopeitis theformer. Writing the acknowledgments is one of the most enjoyable but also one of the most difficult parts of writing the thesis. I want to list all my professors, my teachers, the administrators, and everyone who contributed to me being here. This includes people I don’t know, such as the MIT admissions officers who gave me a chance to come here. Unfortunately, listing everybody is not possible. I am alsoboundtoforgetpeopleIknow,andIapologize forthat. 6 Contents 1 Introduction 17 2 Background 21 2.1 LinearRepresentations ofVectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 BasesandBasisRepresentations . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 FramesandFrameRepresentation . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.3 FramesasaTransformation ofOrthonormalBases . . . . . . . . . . . . . . 23 2.1.4 DecouplingtheAnalysisfromtheSynthesis . . . . . . . . . . . . . . . . . . 25 2.1.5 FramesImpliedbyMatrixOperations . . . . . . . . . . . . . . . . . . . . . 26 2.1.6 FramesImpliedbyDiscrete-time Filters . . . . . . . . . . . . . . . . . . . . 26 2.1.7 FramesImpliedbyFilterbanks . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.8 UsefulFamiliesofFrames . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 OrthogonalProjection ofVectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.2.1 ProjectionsandFrameExpansions . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7 2.3.1 ScalarQuantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.2 VectorQuantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.3 AdditiveNoiseModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 CompensationUsingProjections 39 3.1 ErrorCompensation UsingRepresentation Coefficients . . . . . . . . . . . . . . . . 39 3.1.1 ComputationoftheProjection Coefficients . . . . . . . . . . . . . . . . . . 41 3.1.2 ProjectionsandRe-expansion oftheError . . . . . . . . . . . . . . . . . . . 43 3.2 Pre-compensation FollowedbyPost-correction . . . . . . . . . . . . . . . . . . . . 44 4 QuantizationofFrameRepresentations 47 4.1 Quantization ofOrthonormal BasisExpansions . . . . . . . . . . . . . . . . . . . . 48 4.2 Quantization GridsandFrameRepresentations . . . . . . . . . . . . . . . . . . . . 49 4.2.1 LinearReconstruction fromtheQuantizedCoefficients . . . . . . . . . . . . 49 4.2.2 AnalysisFollowedbyScalarQuantization . . . . . . . . . . . . . . . . . . . 50 4.3 LimitsofScalarQuantization oftheAnalysisCoefficients . . . . . . . . . . . . . . 51 4.3.1 Representation BitsUse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.2 LowerBoundontheQuantization Error . . . . . . . . . . . . . . . . . . . . 52 4.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.4 Intersection ofaHyperplane withaHypercube Lattice . . . . . . . . . . . . . . . . 55 4.4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.4.2 Intersection ofaSingleCellwithaHyperplane . . . . . . . . . . . . . . . . 57 4.4.3 Intersection ofCellsintheHypercubeLattice . . . . . . . . . . . . . . . . . 58 4.5 EfficiencyofFrameRepresentations . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5 QuantizationNoiseShapingonFiniteFrameRepresentations 61 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.2 ConceptsandBackground . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2.1 FrameRepresentation andQuantization . . . . . . . . . . . . . . . . . . . . 63 5.2.2 Sigma-DeltaNoiseShaping . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.3 NoiseshapingonFrames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.3.1 SingleCoefficientQuantization . . . . . . . . . . . . . . . . . . . . . . . . 65 8 5.3.2 SequentialNoiseShapingQuantizer . . . . . . . . . . . . . . . . . . . . . . 66 5.3.3 TreeNoiseShapingQuantizer . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.4 ErrorModelsandAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.4.1 AdditiveNoiseModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.4.2 ErrorMagnitude UpperBound . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.4.3 AnalysisoftheErrorModels . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.5 FirstOrderQuantizerDesign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.5.1 SimpleDesignStrategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.5.2 Quantization GraphsandOptimalQuantizers . . . . . . . . . . . . . . . . . 72 5.6 FurtherGeneralizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.6.1 ProjectionRestrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.6.2 HigherOrderQuantization . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.7 ExperimentalResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.8 NoiseShapingwithCompleteCompensation . . . . . . . . . . . . . . . . . . . . . 80 5.8.1 ErrorUpperBound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.8.2 DeterminationoftheResidualVectors . . . . . . . . . . . . . . . . . . . . . 81 5.8.3 NoiseShapingonFiniteShiftInvariant Frames . . . . . . . . . . . . . . . . 82 6 NoiseShapingforInfiniteFrameRepresentations 85 6.1 ExtensionstoInfiniteFrames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.1.1 InfiniteShiftInvariant Frames . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.1.2 FirstOrderNoiseShaping . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.1.3 HigherOrderNoiseShaping . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2 MultistageD/AConverters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.2.1 EliminationoftheDiscrete-timeFilter . . . . . . . . . . . . . . . . . . . . . 90 6.2.2 MultistageImplementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.2.3 Conversion Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.3 TunableSigma-DeltaConversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.3.1 TunableDigitaltoAnalogConversion . . . . . . . . . . . . . . . . . . . . . 95 6.3.2 TunableAnalogtoDigitalConversion . . . . . . . . . . . . . . . . . . . . . 96 6.3.3 OptimalTuningandQuantization Precision . . . . . . . . . . . . . . . . . . 97 9 7 CompensationforErasures 99 7.1 ErasureCompensation UsingProjections . . . . . . . . . . . . . . . . . . . . . . . 101 7.1.1 ProblemStatement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 7.1.2 Compensation ofaSingleErasure . . . . . . . . . . . . . . . . . . . . . . . 102 7.1.3 Compensation ofMultipleCoefficients . . . . . . . . . . . . . . . . . . . . 103 7.2 CausalCompensation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.2.1 Transmitter-awareCompensation . . . . . . . . . . . . . . . . . . . . . . . 105 7.2.2 Pre-compensation withCorrection . . . . . . . . . . . . . . . . . . . . . . . 106 7.2.3 Compensation Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 7.2.4 SimulationResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7.3 PuncturingofDenseRepresentations . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.3.1 PuncturingAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 7.3.2 ErrorEvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.3.3 SparsificationSchedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.3.4 Quantization CombinedwithSparsity . . . . . . . . . . . . . . . . . . . . . 116 8 ConclusionsandFutureWork 119 8.1 ErrorCompensation UsingProjections . . . . . . . . . . . . . . . . . . . . . . . . . 119 8.2 Quantization Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 8.3 Generalization ofSigmaDeltaNoiseShaping . . . . . . . . . . . . . . . . . . . . . 120 8.4 Compensation forErasures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.5 SuggestedResearchDirections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Bibliography 123 10