PHASERETRIEVALFROMCONTINUOUSANDDISCRETE PTYCHOGRAPHICMEASUREMENTS By SamiEidMerhi ADISSERTATION Submittedto MichiganStateUniversity inpartialful˝llmentoftherequirements forthedegreeof MathematicsDoctorofPhilosophy 2019 ABSTRACT PHASERETRIEVALFROMCONTINUOUSANDDISCRETEPTYCHOGRAPHIC MEASUREMENTS By SamiEidMerhi Inthisdissertation,wepresentandstudytwonovelapproachestophaseretrieval aninverseprobleminwhichoneattemptstoreconstructacomplex-valuedfunction(or vector)fromphaseless(ormagnitude-only)measurements.Phaseretrievalarisesinseveral scienti˝careasincludingbio-chemistry,optics,astronomy,quantummechanics,andspeech signalprocessing.Earlysolutionstophaseretrieval,althoughpractical,lackedrobustness guarantees.Tothisday,practitionersinscienti˝cimagingarestillseekingdemonstrably stableandrobustrecoveryalgorithms. Ptychographyisaformofcoherentdi˙ractiveimagingwheredi˙ractionpatternsare processedbyalgorithmstorecoveranimageofaspecimen.Morespeci˝cally,smallregions ofaspecimenareilluminatedone-at-a-time,andadetectorcapturestheintensitiesofthe resultingdi˙ractionpatterns.Assuch,themeasurementsare local and phaseless .Inthis work,wepresenttwoalgorithmstorecoversignalsfromptychographicmeasurements.The ˝rstalgorithmaimstorecoveradiscreteone-dimensionalsignalfromdiscretespectrogram measurementsviaamodi˝edWignerdistributiondeconvolution(WDD)method.Whilethe methodisknowntopractitionersofscienti˝cimaging,robustnessandrecoveryguarantees arelacking,ifnotabsent;ourcontributionistosupplysuchguarantees. Thesecondalgorithmaimstoapproximatelyrecoveracompactlysupportedfunctionfrom continuousspectrogrammeasurementsvialiftingandangularsynchronization.Thissetup canbeinterpretedasthein˝nite-dimensionalequivalentofdiscreteptychographicimaging. Ourcontributionisamodelwhichassumesin˝nite-dimensionalsignalsandmeasurements abinitio ,asopposedtomostrecentalgorithmsinwhichdiscretemodelsareanecessity. Finally,weconsidertheworst-casenoiserobustnessofanyphaseretrievalalgorithmwhich aimstoreconstructallnonvanishingvectorsfromthemagnitudesofanarbitrarycollection oflocalcorrelationmeasurements.Therobustnessresultsprovidedthereinapplytoawide rangeofptychographicimagingscenarios.Inparticular,ourcontributionistoshowthat stablerecoveryofhigh-resolutionimagesofextremelylargesamplesislikelytorequireavast numberofmeasurements,independentoftherecoveryalgorithmemployed. The˝rstchapterintroducesthephaseretrievalproblemandpresentshistoricalcontext, aswellasapplicationsinwhichphaseretrievalmanifests.Inaddition,weintroducepty- chography,discussexistingWDDformulations,andcomparethesetoourcontributionin thediscretesetting.Chapter2providesrecoveryguaranteesforusingaliasedWDDmethods tosolvethephaseretrievalprobleminadiscretesettingwithsub-sampledmeasurements. InChapter3weprovidelowerLipschitzboundsforgenericphaseretrievalalgorithmsfrom locallysupportedmeasurements.Finally,Chapter4presentsanumericalmethodtorecover compactlysupportedfunctionsfromlocalmeasurementsvialiftingandangularsynchroniza- tion. Thisdissertationisdedicatedtomylovingparents,AntoinetteAsmarandEidMerhi. ForevenasHelovesthearrowthat˛ies,soHelovesalsothebowthatisstable. - GibranKhalilGibran,TheProphet iv ACKNOWLEDGMENTS Whenyoupartfromyourfriend,yougrievenot;forthatwhichyoulovemostinhimmay beclearerinhisabsence,asthemountaintotheclimberisclearerfromtheplain. - GibranKhalilGibran,TheProphet Thisdissertationisthefruitofwonderfulrelationshipsestablishedduringmyyearsof studyatMichiganStateUniversity.Onapersonallevel,thecamaraderieIenjoyedwith fellowdoctoralstudentshelpedeasethefrustrationofgraduateschool.Professionally,the mentorshipandguidanceIreceivedfrommyadvisorandcollaboratorssetmeupforacademic ful˝llment.Iwouldliketodedicateafewparagraphstothankthepeoplewhounequivocally contributedtomywell-beingandsuccess. Firstandforemost,Iwouldliketothankmyadvisor,Dr.MarkIwen,forallhehas doneformeduringmyyearsatMichiganStateUniversity.Yourclassoncompressive sensingshowedmehowpracticalharmonicanalysiscanbe,andhowfunpagesandpagesof computationsare.Wheneverwehitaresearchwall,somehowyoumanagedto˝ndaway aroundit.Yourtenacityisinfectious.Iappreciatehowdedicatedyouarenotonlytoyour workandyourcareer,butalsotothesuccessofyourstudentsandcollaborators.TosayI havehadthepleasuretoworkwithyouisanunderstatement.Thankyouforyourtime, yourguidance,andyourunderstanding. IwouldalsoliketothankAdityaViswanathan,whocollaboratedonmyresearchboth asapostdoctoralfellowandassistantprofessor.Yourexperienceinprogrammingandcom- putationwereinvaluabletome,andIlearnedmorefromreadingyourscriptsthanfrom anyothersource.Yourreadinesstoanswerquestionsanddebugproblemsisappreciated. Youhavebeengreathelptome,andforthatI'mforevergrateful.Whileonthetopicof v co-authorship,IwouldalsoliketothankMichaelPerlmutterforhiscollaborationonmy research,andforthevaluablefeedbackhe'sprovided. MyyearsofstudyingandteachingatMSUweremadeenjoyablethankstoanamazing sta˙,goodfriends,andwonderfulteachers.Iwouldspeci˝callyliketothankTsvetaSendova andAndrewKrauseforgivingmetheopportunitytomentorfellowgraduatestudents,and togrowinleadership.I'mgratefultoRyanMaccombsformakingthetediousaspectsof settingupcoursesdisappear.Icouldn'tpossiblythankallthefriendsImadeatMSU,for theyaremany.Andyet,Iwouldliketomentionthosewhosharedinmyaccomplishments andhelpedmethroughthedi˚culttimes.Rami,Wenzhao,Charlotte,Paata,Nick,Andy, Tyler,Guillermo,Reshma,Hitesh,Max,andArman:thankyouforbeingamemorable partofmystory.IamdeeplythankfulandgratefulforMegan;youhavebeensuchagreat companionoverthepasttwoyears,andhavebroughtsomuchhappinessandjoyintomy life.Thankyouforrunningthisraceandforcelebratingwithmeatthe˝nishline. ManyofthefacultyatMSUhelpednourishmyinterestinappliedmathematicsgenerally, andappliedharmonicanalysisspeci˝cally.IwouldliketothankDr.YingdaChengfor runningapleasurableclassinappliedmethodsforODEs,andDr.SelinAviyenteforher invaluableclassinwaveletsandtime-frequencyanalysis.BothDr.ChengandDr.Aviyente servedonmycomprehensiveexamcommittee,andwithDr.ZhengfangZhou,alsoserved onmydissertationcommittee;forthatI'mdeeplygrateful. MymathematicaljourneystartedatWesternConnecticutStateUniversity,andIwould beremissifIdidn'tmention,andthank,Dr.XiaodiWang,whoplayedanexceptionalrole inintroducingmetoresearchinappliedmath.Youwereinstrumentalinguidingmeand preparingmeforagraduatetrack.WCSUhostedagroupofin˛uentialeducatorswho,in onewayoranother,preparedmeforteachingatMSU.ThanksareduetoDr.Lubell,Dr. vi Rocca,Dr.Novozhilova,Dr.Burns,Dr.Mittag,Dr.Lightwood,andDr.Hamer,forthe wonderfulexperiencesIhadinyourclassrooms.IwouldalsoliketothankPierceO'Donnell, who,alongwithbeingmy˝rstcollaborator,hasbeenmybestfriendandclosecon˝dentfor years.Yourfriendshiphasbeenindispensabletome. Lastly,butmostimportantly,Iamforevergratefulforhavingasupportivefamily.I couldn'thaveaskedforbettersiblings;CelinaandAnthony,thankyouforlaughingatmy sillyjokes,andforlisteningwhennooneelsecould.MomandDad,youarethekindof parentseveryonewishestheyhad.Yoursupportandencouragementhelpedmealongthe way,andtheprospectofmakingyouproudgotmetothe˝nishline.Wedidit! vii TABLEOFCONTENTS LISTOFFIGURES ................................... x KEYTOSYMBOLS .................................. xi KEYTOABBREVIATIONS ............................. xii Chapter1HistoryofPhaseRetrievalandPtychography .......... 1 1.1ProblemDe˝nitionandApplications......................1 1.2ExistingSolutionstoPhaseRetrieval......................3 1.2.1AlternatingProjections..........................3 1.2.2PhaseLift.................................5 1.2.3WirtingerFlow..............................6 1.3Ptychography...................................8 1.3.1ExperimentalSetup............................8 1.3.2PtychographyandContinuousWignerDistributionDeconvolution..9 1.3.3PtychographyviaDiscreteWignerDistributionDeconvolution....13 1.3.3.1NotationandBasicPropertiesoftheDFT..........13 1.3.3.2WignerDistributionDeconvolutionintheDiscreteSetting.17 Chapter2PhaseRetrievalviaAliasedWignerDistributionDeconvolu- tionandAngularSynchronization .................. 19 2.1AliasedWDDforPhaseRetrieval........................21 2.1.1Sub-samplinginFrequency........................22 2.1.2Sub-samplinginFrequencyandSpace..................24 2.1.3RecoveringDiagonalsof b x b x .......................26 2.1.3.1ASpecialCaseofTheorem2.1.1...............37 2.1.4OtherSupportConditions........................40 2.1.4.1ASpecialCaseofLemma2.1.6.................43 2.2NumericalResults.................................51 2.2.1EmpiricalValidationofTheorem2.1.1(Algorithm1).........53 2.2.2EmpiricalValidationofLemma2.1.5..................58 2.2.3EmpiricalValidationofTheorem2.1.2(Algorithm2).........62 Chapter3LowerLipschitzBoundsforPhaseRetrievalfromLocallySup- portedMeasurements ......................... 63 3.1IntroductionandStatementofResults.....................64 3.1.1RelatedWorkandImplications.....................67 3.1.2MainResults...............................70 3.2TheProofsofTheorem3.1.1andTheorem3.1.2................72 3.3Examples:LowerBoundsforSpeci˝cMeasurementMasks..........77 3.3.1WindowedFourierMeasurementMasks.................77 viii 3.3.2Two-ShotMeasurementMasks......................81 3.4DiscussionandFutureWork...........................84 Chapter4RecoveryofCompactlySupportedFunctionsfromSpectro- gramMeasurementsviaLifting ................... 86 4.1Introduction....................................87 4.1.1TheProblemStatementandSpeci˝cations...............88 4.1.2TheProposedNumericalApproach...................89 4.2OurLiftedFormulation..............................90 4.2.1ObtainingaTruncated,FiniteLiftedLinearSystem..........93 4.3NumericalResults.................................97 4.4FutureWork....................................100 APPENDIX ........................................ 101 REFERENCES ...................................... 105 ix LISTOFFIGURES Figure1.3.1:Experimentalsetupfor˛y-scanptychography.Adaptedfrom ptychographHuangetal.,Scienti˝cReports5(9074),2015.......8 Figure2.2.1:SelectionofHIO+ERiterationparameters.(HIO,ER) =( x;y ) indicates thateverysetof x iterationsoftheHIOalgorithmwasfollowedbyaset of y iterationsoftheERalgorithm......................52 Figure2.2.2:ReconstructionaccuracywithandwithoutHIO+ER( 60 iterations)post- processing,improvedmagnitudeestimation.................54 Figure2.2.3:Reconstructionaccuracyvs.numberofshifts L ...............55 Figure2.2.4:Reconstructionaccuracyvs.addednoise...................57 Figure2.2.5:Executiontimevs.signalsize d ........................57 Figure2.2.6:ReconstructionaccuracywithandwithoutHIO+ER( 60 iterations)post- processing,improvedmagnitudeestimation,andcomparisonwithresults from[36]....................................59 Figure2.2.7:Reconstructionaccuracyvs.numberofFouriermodes K ..........60 Figure2.2.8:Reconstructionaccuracyvs.addednoise...................61 Figure2.2.9:Executiontimeversussignalsize d ......................61 Figure2.2.10:Reconstructionaccuracyvs.addednoise..................62 Figure4.3.1:ModulatedGaussiansignaland11shiftsofaGaussianwindow......97 Figure4.3.2:TrueGaussiansignalanditsreconstruction.................97 Figure4.3.3:TruemodulatedGaussiansignalanditsreconstruction...........98 Figure4.3.4:Characteristicfunctionanditsreconstruction................98 Figure4.3.5:Piecewisecontinuousfunctionanditsreconstruction............98 x KEYTOSYMBOLS Thefollowingisalistofsomeofthenotationusedthroughoutthispaper. For d 2 N , [ d ] 0 := f 0 ; 1 ;:::;d 1 g isthesetofremaindersmodulo d . For d 2 N , [ d ]:= f 1 g +[ d ] 0 = f 1 ; 2 ;:::;d g . L 1 ( R ) ,thesetofintegrablefunctionson R . L 2 ( R ) ,thesetofsquare-integrablefunctionson R . kk 2 , kk F , kk 1 ,theEuclidean,Frobenius,andsupremumnorms,respectively. kk L 2 := kk L 2 ( H ) ,the L 2 normontheHilbertspace H . h x ; y i ,thecomplexinnerproductof x ; y 2 C d . F ,theFouriertransformon L 2 ( R ) . F d ,the d d Fouriertransformmatrix;alsodenoted F whendimensionisclear. ,thecontinuousconvolutionoperatoron L 2 ( R ) L 2 ( R ) . d ,thediscreteconvolutionoperatoron C d C d . ,thecomponentwiseHadamardproduct. I ,theidentitymatrix. M ,theHermitian(conjugate)transposeofmatrix M . diag ( M ) ,thediagonalofmatrix M . ˙ min ( M ) ,thesmallestsingularvalueofmatrix M . M 0 denotesapositivesemi-de˝nitematrix M . j S j ,thecardinalityofset S . ˜ S ,thecharacteristic(orindicator)functionofset S . x j S ,therestrictionofvector x totheindexset S . r f ,thegradientoffunction f . N (0 ; 1) ,thestandardnormaldistribution. sinc ( x ):=sin( x ) =x ,theunnormalizedsincfunctionat x . xi KEYTOABBREVIATIONS AP,theAlternatingProjectionsalgorithm. CCD,charge-coupleddevice. DFT,thediscreteFouriertransform. ePIE,theextendedPtychographicIterativeEngine. FFT,theFastFouriertransform. HIO+ER,theHybridInput-Output+ErrorReductionalgorithm. PIE,thePtychographicIterativeEngine. SNR,signal-to-noiseratio. STFT,theshort-timeFouriertransform. WDD,theWignerdistributiondeconvolution. WDF,theWignerdistributionfunction. WF,theWirtingerFlowalgorithm. xii Chapter1 HistoryofPhaseRetrievaland Ptychography 1.1ProblemDe˝nitionandApplications Phaseretrievalinthediscretesettingistheprocessofalgorithmicallyrecoveringanestimate toavector x 2 C d from D (possiblynoisy)measurementsoftheform y = j B x j 2 + 2 C D : (1.1.1) Here, B 2 C D d is(usually)aknownmeasurementmatrix,and 2 C D isanadditivenoise vector.Theoperator 2 representsthecomponentwisemagnitudesquaredoperation,so that j u j 2 n := j u n j 2 8 u :=( u 0 ;:::;u d 1 ) T 2 C d : Asimpleinspectionof(1.1.1)showsthatanysolutiontothephaseretrievalproblemisonly possiblyuniqueuptoaglobalphasefactor.Moreprecisely,if x 0 2 C d solves(1.1.1),then sodoes e x 0 forany 2 [0 ; 2 ˇ ) .Thisphaseambiguitymeansthatanyphaseretrieval 1 algorithmaimsto˝ndauniquesolutionto(1.1.1)undertheequivalencerelation u ˘ v () u = v forsome 2 C with j j =1 . Phaseretrievaloriginatesfromthefactthatlightdetectors,suchasphotographicplatesor charge-coupleddevices(CCDs),canoftentimesonlymeasuretheintensityofincidentlight. Thisisbecausethesedevicesrespondonlytothenumberandenergyofphotonsarrivingat theirsurface.Morespeci˝cally,thesedetectorsrecordthesquaredmagnitudeoftheFresnel orFraunhoferdi˙ractionpatternoftheradiationthatisscatteredfromanobject.These measurementsarethereforeincomplete,becausealightwavehasnotonlyanamplitude (relatedtotheintensity),butalsoaphase,whichissystematicallylostinameasurement. Itisimportanttonotethatthephasepartofthewaveoftenencodesrelevantinformation aboutthespecimenofinterest,especiallyindi˙ractionormicroscopyexperiments. Historically,the˝rstapplicationofphaseretrievalisX-raycrystallography[29,45],a techniqueusedfordeterminingtheatomicstructureofacrystal,inwhichthecrystalline arrangementcausesabeamofincidentX-raystodi˙ractintomanyspeci˝cdirections.X-ray crystallographyisstilltheprimarymethodforcharacterizingtheatomicstructureofnew materialsandindiscerningmaterialsthatappearsimilarbyotherexperiments. Otherareasofimagingscienceinwhichphaseretrievalisemployedincludedi˙raction imaging[11,52],optics[59],electronmicroscopy[32],astronomy[21],andX-raytomography [19],tonameafew.Phaseretrievalalsoappearsinsolutionstoproblemsinquantum mechanics[18],speechrecognitionandaudioprocessing[46,4,56],andself-calibration[40]. 2 1.2ExistingSolutionstoPhaseRetrieval Priortoalgorithmicsolutionstophaseretrieval,practitionershadtoinvent,andcontend with, adhoc methodstoresolvetheirphaselessimagingexperiments.Indeed,the1915 NobelPrizeinPhysicswasawardedjointlytoSirWilliamHenryBraggandhisson,William LawrenceBragg,fortheirgeometricanalysisofcrystalstructuresbymeansofX-rays.It wasnotuntilthe1970sthatasystematicmethodforphaseretrievalcametothescene,and showedpromiseoutsidetheX-raycrystallographyregimen.Themethod,called Alternating Projections (AP),wasproposedbyGerchbergandSaxtonin1971[24],andlaterre˝nedand improved.Inthesectionsbelow,weprovidebriefoutlinesofthegenericAPalgorithm,as wellasmorerecentnumericalmethodsforphaseretrievalwhichenjoytheoreticalrecovery guarantees. 1.2.1AlternatingProjections Byandlarge,themostpopularmethodsforphaseretrievalfromover-sampleddataare alternatingprojections(AP)algorithmspioneeredbyGerchbergandSaxton[24]andFienup [22,23].APalgorithmsprovidedgreatsimprovementsover adhoc methods,sincetheycould beappliedtofairlygeneraldata,withveryminimalassumptionsmadeonthestructureof thespecimenbeingimaged. AtypicalAPalgorithmworksinthefollowingmanner.Supposeonehastorecover x 2 C d fromthemeasurements y = j A x j ,wherethe D rowsof A 2 C D d areaframe, and D d .Twopiecesofinformationareavailableconcerningthesolutionofthisphase retrievalproblem:thesolutionhasamplitude y andislocatedontherangeof A ,denoted 3 R A .Onethende˝nesa phasecorrection operator P A : C D ! C D as P A := A ( A A ) 1 A ; whichprojectsacomplexvectorto R A ,andan amplitudecorrection operator P y : C d ! C d , de˝nedforall u 2 C D componentwiseby P y u j := y j u j u j ˜ u j + y j 1 ˜ u j : Assuch, P y substitutestheamplitude u j by y j andpreservesphaseinformation. Withthenotationabove,solvingthephaseretrievalproblemamountsto˝ndingavector x 0 2 C D whichisa˝xedpointofbothoperators P A and P y ;thatis, x 0 satis˝esthetwo conditions k ( x 0 P A x 0 ) k =0 and k x 0 P y x 0 k =0 : Theunknown x maythenbeestimatedas ( A A ) 1 A x 0 . TheAPalgorithmgetsitsnamefromtheiterativeschemeusedto˝ndthe˝xedpoint x 0 : g j + 1 = 2 := P y g j ; g j + 1 := P A g j + 1 = 2 ; where j rangesover N and g 0 istheinitialguess. Marchesiniandhiscollaboratorsprovedin2015thatAPalgorithmsusinggenericmea- surementsareguaranteedtoconvergewhenprovidedwithasu˚cientlyaccurateinitialguess [43].Tothisday,noglobalrecoveryguaranteesexistforAPalgorithmsinthecaseoflo- calmeasurements.Thesealgorithmswillconvergewhenprovidedwithanaccurateenough 4 initialization;however,thegeometryofthebasinofattractionisunknown.Althougheasy tostateandexplain,Marchesinietal.arguethatAPalgorithmsoftenrequirecarefulex- ploitationofsignalconstraintsanddelicateparameterselectiontoincreasethelikelihood ofconvergence.Forinstance,ourknowledgemaybethatthesignalisreal-valued,posi- tive,band-limited,orspatially-limited.MorecanbesaidaboutAPalgorithmswhenthe measurementsareGaussian.Forexample,Waldspurgerhasarguedthatwhenprovidedwith Gaussianmeasurements,spectralinitializationissu˚cientlyaccurateforAPalgorithms[58]. 1.2.2PhaseLift In2011,EmmanuelJ.Candèsandhiscollaboratorsproposed PhaseLift ,analgorithmbased onconvexprogramming,tosolvethephaseretrievalproblem[14].Theirapproachincluded twomaincomponents: multiplestructuredilluminations ,asisthecaseinptychographic imaging,andtheformulationofphaserecoveryasa matrixcompletionproblem . TosummarizethePhaseLiftalgorithm,letusposethephaseretrievalproblemas Find x 2 C d satisfying jh x ; a k ij 2 = y k 8 k 2 [ D ] 0 := f 0 ; 1 ;:::;D 1 g : (1.2.1) Letusnowdenoteby X therank-onematrix xx ,andby A k therank-onematrix a k a k . Moreover,let A denotethelinearoperatormappingpositivesemi-de˝nitematricesinto f Tr ( A k X ): k 2 [ D ] 0 g .Thenthephaseretrievalproblemisequivalentto ˝nd X minimizerank ( X ) subjectto 8 > < > : A ( X )= y X 0 rank ( X )=1 () subjectto ( A ( X )= y X 0 : Oncetheleft-handsideoftheproblemaboveissolved,therank-onesolution X can 5 befactorizedas xx ,hence˝ndingsolutionstothephaseretrievalproblemuptoaglobal phase,ifthelinearoperator A iswell-behaved.Theproblemaboveisarankminimization problemoverana˚nesliceofthepositivesemi-de˝nitecone.Assuch,itfallsintherealm oflow-rankmatrixcompletionormatrixrecovery. SincetheminimizationproblemaboveisNPhard,theauthorsproposeusingthetrace normasaconvexsurrogatefortherankfunctional,givingthesemi-de˝niteprogram minimizeTrace ( X ) subjectto ( A ( X )= y X 0 : OneshouldnotethatwhileSDPbasedrelaxationmethodsprovidetractablesolutions, theybecomecomputationallyprohibitiveasthedimension d ofthesignalincreases. 1.2.3WirtingerFlow In2015,Candès,Li,andSoltanolkotabidevelopedanon-convexformulationofthephase retrievalproblem,andproposedasolutionalgorithm[13].Thealgorithm,referredtoas WirtingerFlow (WF),reliesonaspectralinitializationandupdaterulesoflowcomputa- tionalcomplexity. TheWFalgorithmworksasfollows.Considerthephaseretrievalproblemasstatedin (1.2.1).Set 2 = d P k y k P k k a k k 2 : Thentheinitialguess, g 0 ,istheleadingeigenvector(normalizedsothat k g 0 k = )ofthe matrix Y = 1 D D X k =1 y k a k a k : 6 Theguessisupdatedviathefollowingsteepest-descentrecursion: g j + 1 = g j j +1 k g 0 k 2 r f g j ; where j +1 isthestepsize,and f : C d ! R isthelossfunction f ( u ):= 1 2 D D X k =1 y k j a k u j 2 2 : Theauthorsin[13]motivatethespectralinitializationstepbyconsideringthesimple casewhereeverythingisreal-valued,andthemeasurementvectors a k arei.i.d. N (0 ;I ) .In thiscase,thematrix Y isequalto I +2 xx inthelimitoflargesamples.Moreover,thetop eigenvectorof I +2 xx isoftheform x forsomepositivescalar .Thismeansthat x can berecoveredperfectlybytheinitializationstep,uptoaglobalsign 1 . BothPhaseLift[15,28]andWirtingerFlow[13]achieverecoveryguaranteeswithhigh probabilitywhenusing O d log 4 d maskedFouriercodeddi˙ractionpatternmeasurements, butstopshort,however,ofprovidingguaranteeswhenthemeasurementsarenotrandomized. Weendthissectionbynotingthatthemethodsaforementioneddonotprovidetheoret- icalrecoveryguaranteesforlocallysupportedanddeterministicmeasurementsofthetype encounteredinptychography. 7 1.3Ptychography 1.3.1ExperimentalSetup Ptychographyisacomputationalmethodofmicroscopicimaging,inwhichimagesaregener- atedbyprocessingalargenumberofcoherentdi˙ractionpatternsthathavebeenscattered fromaspecimenofinterest.Theinterferencepatternsaregeneratedbyaconstantfunction, saya˝eldofillumination,movinglaterallybyaknownamountwithrespecttothespecimen. Assuch,ptychographyistranslation-invariant.Theinterferencepatternsarecapturedbya detector,somedistanceawayfromthespecimen,sothatthescatteredwavesfoldintoone another.Thisexplainstheoriginofthename: ptycho inGreekmeans tofold . Figure1.3.1:Experimentalsetupfor˛y-scanptychography.Adaptedfrompty- chographHuangetal.,Scienti˝cReports5(9074),2015. ThenameychographwascoinedbyHegerlandHoppein1972[30]todescribea solutiontothecrystallographicphaseproblem˝rstsuggestedbyHoppein1969[31].In thisearlystage,theconceptrequiredthespecimentobeacrystal,andtobeexposed toapreciselyengineeredwave,sothatonlytwopairsofdi˙ractionpeaksinterferewith oneanotheratatime.TheFouriershifttheoremimpliesthatashiftintheillumination changestheinterferencecondition.Thismeansthattwoptychographicmeasurementscan 8 beusedtosolveforphasedi˙erencesbetweenthedi˙ractionpeaks,bybreakingacomplex- conjugateambiguitythatwouldotherwiseexist[52].Innon-crystallineobjects,millionsof beamsinterfereatthesametime,makingthephasedi˙erencesinseparable;forthisreason, crystallineptychographycouldnotbeusedtoimagecontinuousmedia. Betweentheyears1989and2007Rodenburgandhiscolleaguescreatedmultipleinver- sionmethodsforthegeneralptychographicphaseproblem,includingWignerdistribution deconvolution(WDD)[49],SSB[50],the PIE iterativemethod[51](aprecursorofthe ePIE algorithm[41]),demonstratingproof-of-principlesatdi˙erentwavelengths.Chapmanused Wignerdeconvolutiontodemonstratethe˝rstimplementationofX-rayptychographyin 1996[17].Thepoorqualityofdetectorsandrudimentarycomputingabilitiesofthetime mayaccountforthelimitedadoptionofptychographybyotherpractitioners. 1.3.2PtychographyandContinuousWignerDistributionDeconvo- lution Inthissection,weintroducethemethodofWignerdistributiondeconvolutionaspresented byRodenburgandBates[49],discusshowitappliestophaseretrievalinthecontinuous setting,andpresentnovelideasinthecaseofdiscretemeasurements.Amorethorough discussiononWDD,andafurtherexpansionofthemethod,arethesubjectofChapter2. Let F : L 2 ( R ) ! L 2 ( R ) denotethecontinuousFouriertransform,de˝nedvia: Ff h g ( ! ):= 1 h ( t ) e 2 ˇi!t dt: (1.3.1) Let f : R ! C denoteanunknownspecimen,and g : R ! C denoteaknown mask or window function.Theshort-timeFouriertransformof f ataphysicalshift ` 2 R and 9 frequency ! 2 R ,giventhewindowfunction g ,isde˝nedas STFT f f;g g ( `;! ):= Ff f S ` g g ( ! ) ; (1.3.2) where S t istheshiftoperatorde˝nedsothat ( S t g )( x )= g ( x + t ) .ToeachSTFTmeasure- ment STFT f f;g g ( `;! ) correspondsa spectrogram measurement b ( `;! ) formedbysquaring theabsolutevalue: b ( `;! ):= j STFT f f;g g ( `;! ) j 2 : (1.3.3) Spectrogrammeasurementsareptychographicinnature,sincethemaskorwindowfunction g maybeseenasaspatially-limitedprobefunction,thefunction f representsanunknown specimen,and b ( `;! ) representsaphaselessintensitymeasurementascapturedbyade- tector.Oneistheninterestedinrecovering f froma˝nitenumberofsuchspectrogram measurements.TheWDDmethoddoessoduetothefollowingequality: F Ff b g ! 0 ` 0 = F f S ! 0 f ` 0 F n g S ! 0 g o ` 0 (1.3.4) forall ` 0 ;! 0 2 R R .Insimpleterms,applyingthecontinuousFouriertransformtwice tothespectrogrammeasurements,˝rstinthefrequencyvariableandtheninthespacial variable,leadstoa decoupling oftheunknownfunction f fromtheknownmask g . Forthesakeofcompleteness,wepresentacomputationalproofof(1.3.4).Theproof usesthefollowingelementarypropertiesoftheFouriertransformasde˝nedin(1.3.1),which holdforany h : R ! C : jFf h gj 2 = F n h e h o ; 10 FfFf h gg = e h; where denotestheconvolutionoperator,and e h isthereversalof h aboutzero,sothat e h ( t )= h ( t ) forall t 2 R .Nowobservethatfor ( `;! ) 2 R R , b ( `;! )= 1 f ( t ) g ( t ` ) e 2 ˇiwt dt 2 = jFf f S ` g g ( ! ) j 2 = F n ( f S ` g ) e f ] S ` g ( ! ) : UpontakingaFouriertransforminthe ! variable,at ! 0 ,onegets Ff b ( `; ) g ! 0 = F n F n ( f S ` g ) e f ] S ` g ! 0 = ( f S ` g ) e f ] S ` g ! 0 = 1 f ( t ) g ( t ` ) e f ] S ` g t ! 0 dt = 1 f ( t ) g ( t ` ) f ( t + ! 0 ) g ( t ` + ! 0 ) dt = 1 f ( t ) S ! 0 f ( t ) g ( t ` ) S ! 0 g ( t ` ) dt = 1 f S ! 0 f ( t ) e g S ! 0 e g ( ` t ) dt = 1 f ! 0 ( t ) g ! 0 ( ` t ) dt; where f ! 0 ( t ):= f S ! 0 f ( t ) ; g ! 0 ( t ):= e g S ! 0 e g ( t ) : 11 Therefore,wehave Ff b ( `; ) g ! 0 = 1 f ! 0 ( t ) g ! 0 ( ` t ) dt = f ! 0 g ! 0 ( ` ) = f S ! 0 f e g S ! 0 e g ( ` ) : TakingaFouriertransformonelasttime,inthe ` variable,at ` 0 ,yields F Ff b g ! 0 ` 0 = F f S ! 0 f ` 0 F n e g S ! 0 e g o ` 0 ; bytheConvolutionTheorem.Thisproves(1.3.4). TheWDDmethodgetsitsnamefromobservingthateachoftheFouriertransformson theright-handsideof(1.3.4)isa Wignerdistributionfunction .Namely, F f S ! 0 f ` 0 = WDF f ! 0 ;` 0 ; (1.3.5) F n e g S ! 0 e g o ` 0 = WDF e g ! 0 ;` 0 ; (1.3.6) wheretheWignerdistributionfunctionof h at ( u;v ) isde˝nedas WDF h ( u;v ):= 1 h ( t ) h ( t + u ) e 2 ˇivt dt: (1.3.7) InChapter4,weproposeadi˙erentapproachtorecovercompactlysupportedfunctions fromtheirspectrograms.ThemethoddoesnotrequireapplicationsofFouriertransforms, butratherarewritingofthephaselessmeasurementsinaliftedform.Angularsynchroniza- tionisthenusedtosolveforavectorizedversionofthein˝nitedimensionalspecimen. 12 1.3.3PtychographyviaDiscreteWignerDistributionDeconvolu- tion Inthissection,wede˝neadiscreteWignerdistributiondeconvolutionmethodforrecovering adiscretesignalfromitsspectrogrammeasurements.Tobeprecise,wede˝nesuch(noiseless) measurementsasfollows.Let x ; m 2 C d 1 denotespecimenandmask,respectively.The spectrogramof x givenmask m ataphysicalshift ` 2 [ d ] 0 andFouriermode k 2 [ d ] 0 isthe phaselessquantity d 1 X n =0 x n m n ` e 2 ˇink d 2 : (1.3.8) TheapproachbelowisthediscreteequivalentoftheWDDmethodintroducedbyRodenburg andBatesin1992[49].Speci˝cally,themask,specimen,andmeasurementsareassumedto bediscreteabinitio.Beforediscussingthisapproachindetail,weintroducesomenotation andbasicpropertiesofthediscreteFouriertransform(DFT). 1.3.3.1NotationandBasicPropertiesoftheDFT Let x =( x 0 ;x 1 ;:::;x d 1 ) T 2 C d 1 .Recallthat [ d ] 0 = f 0 ; 1 ;:::;d 1 g isthesetof remaindersmodulo d .Wedenotebysupp ( x ) theindexsetcorrespondingtothenonzero entriesof x ;thatis, supp ( x ):= f n 2 [ d ] 0 j x n 6 =0 g : TheFouriertransformof x ,denotedby b x 2 C d 1 ,isde˝nedcomponentwisevia b x k :=( F d x ) k = d 1 X n =0 x n e 2 ˇink d ; 13 where F d 2 C d d denotesthe d d DFTmatrixwithentries ( F d ) `;k = e 2 ˇi`k d 8 ( `;k ) 2 [ d ] 0 [ d ] 0 : Withthisde˝nitiononecaninverttheFouriertransformvia x n = F 1 d b x n = 1 d d 1 X k =0 b x k e 2 ˇikn d : Givenavector u 2 C d 1 ,denoteby e u thereversalof u aboutits˝rstentrysothatits componentsare e u n := u n mod d 8 n 2 [ d ] 0 : Given ` 2 [ d ] 0 ,de˝nethecircularshiftoperator S ` : C d 1 ! C d 1 componentwisevia ( S ` u ) n = u ( ` + n )mod d 8 n 2 [ d ] 0 : Similarly,given k 2 [ d ] 0 ,de˝nethemodulationoperator W k : C d 1 ! C d 1 componentwise via ( W k u ) n = u n e 2 ˇikn d 8 n 2 [ d ] 0 : WesummarizesomepropertiesoftheDFTandtheoperatorsaboveinthelemmabelow. TheinterestedreadermayrefertotheAppendixforacompleteproof. Lemma1.3.1. Thefollowingequalitiesholdforany x 2 C d 1 andforall ` 2 [ d ] 0 : 1. F d b x = d e x . 2. F d ( W ` x )= S ` b x . 14 3. F d ( S ` x )= W ` b x . 4. W ` F d S ` e x = b x . 5. g S ` x = S ` e x . 6. F d x = F d e x . 7. e b x = F d e x . Let d and denotethecircularconvolutionoperatorandtheHadamardproductin C d 1 ,respectively.Moreprecisely,given x ; y 2 C d 1 and ` 2 [ d ] 0 ,wede˝ne ( x d y ) ` := d 1 X n =0 x n y ( ` n )mod d ; ( x y ) ` := x ` y ` : ThediscreteversionoftheConvolutionTheoremmaybestatedasfollows: Lemma1.3.2. (ConvolutionTheorem)Forall x ; y 2 C d 1 onehas F 1 d ( b x b y )= x d y and ( F d x ) d ( F d y )= d F d ( x y ) : Wealsointroducesometechnicallemmasbelow,whichwillbeusedintheproofsof lemmasandtheoremsthroughoutthischapter,aswellasinChapter2. 15 Lemma1.3.3. Let x ; y 2 C d 1 and `;k 2 [ d ] 0 .Then ( x S ` y ) d e x S ` e y k = ( x S k x ) d e y S k e y ` : Proof. Let x ; y 2 C d 1 and `;k 2 [ d ] 0 bearbitrary.Wecalculate ( x S ` y ) d e x S ` e y k = d 1 X n =0 ( x S ` y ) n e x S ` e y k n (byde˝nitionof d ) = d 1 X n =0 x n y n ` e x k n e y ` + k n (byde˝nitionof ) = d 1 X n =0 x n x n k e y ` n e y ` ( n k ) (byde˝nitionof e ) = ( x S k x ) d e y S k e y ` : (byde˝nitionof d ) Lemma1.3.4. Forany x 2 C d 1 ,onehas j F d x j 2 = F d x d e x : Proof. Let x 2 C d 1 bearbitrary.Then j F d x j 2 =( F d x ) ( F d x ) =( F d x ) F d e x (byLemma1.3.1(4)with ` =0 ) = F d x d e x : (byLemma1.3.2) 16 1.3.3.2WignerDistributionDeconvolutionintheDiscreteSetting Wearenowreadytoprovidetheequivalentof(1.3.4)inthediscrete,noisysetting.Let x ; m 2 C d 1 denotetheunknownspecimenandknownmask,respectively.Assumewehave d 2 noisyspectrogrammeasurementsoftheform ( y ` ) k = d 1 X n =0 x n m n ` e 2 ˇink d 2 +( ` ) k ; ( `;k ) 2 [ d ] 0 [ d ] 0 : (1.3.9) Letthesemeasurementspopulateamatrix Y 2 R d d ,whose ` th columnwewilldenote by y ` 2 C d 1 ,for ` 2 [ d ] 0 .Similarly,letthenoisemeasurements ( ` ) k populateamatrix N 2 C d d ,whose ` th columnwewilldenoteby ` 2 C d 1 .Wehavethefollowinglemma. Lemma1.3.5. Let x 2 C d 1 denoteanunknownspecimen,andlet m 2 C d 1 denotea knownmask(orwindow).Let Y 2 R d d bethematrixofnoisyspectrogrammeasurements asin(1.3.9).Thenforany k 2 [ d ] 0 , F d ( Y N ) T F T d k = d F d ( x S k x ) F d e m S k e m : (1.3.10) Proof. ByLemma1.3.4,wemaywriteforany ` 2 [ d ] 0 , y ` = j F d ( x S ` m ) j 2 + ` = F d ( x S ` m ) d e x S ` e m + ` : (1.3.11) TakingaFouriertransformof y ` at k 2 [ d ] 0 yields ( F d y ` ) k = d ( x S ` m ) d e x S ` e m k +( F d ` ) k ; 17 byLemma1.3.1(1);byLemma1.3.3,weget ( F d y ` ) k = d ( x S k x ) d e m S k e m ` +( F d ` ) k : (1.3.12) Foragiven ` 2 [ d ] 0 ,thevector F d y ` 2 C d 1 isthe ` th columnofthematrix F d Y ;its transpose, y T ` F T d 2 C 1 d isthe ` th rowofthematrix ( F d Y ) T .Similarly,thevector F d ` 2 C d 1 isthe ` th columnofthematrix F d N ;itstranspose, T ` F T d 2 C 1 d isthe ` th rowof thematrix ( F d N ) T .Wemaythuswrite Y T F T d k ` = d ( x S k x ) d e m S k e m ` + N T F T d k ` ; sothatforany k 2 [ d ] 0 ,thevector Y T N T F T d k 2 C d 1 maybecomputedasa convolution: Y T N T F T d k = d ( x S k x ) d e m S k e m : Takinga˝nalFouriertransformnowyields F d ( Y N ) T F T d k = d F d ( x S k x ) F d e m S k e m ; byLemma1.3.2. TheresultofLemma1.3.5canbeinterpretedasthediscreteanalogueto(1.3.4).In (1.3.10),theunknownspecimen x andtheknownmask m aredecoupled.Thisallowsfor therecoveryof x viaangularsynchronization,whichisdiscussedinChapter2. 18 Chapter2 PhaseRetrievalviaAliasedWigner DistributionDeconvolutionandAngular Synchronization InChapter1,wediscussedhowtheWignerdistributiondeconvolutionmethodcouldbe appliedto d 2 discreteptychographicmeasurementsinordertorecoveravector x 2 C d .The methodconsistedofapplyingtwoconsecutiveFouriertransformstothematrixofmeasure- ments,yieldingtheproductoftwoWignerdistributionfunctions,oneforthespecimenand oneforthemask. Inpractice,oneisinterestedincollectingasfewmeasurementsaspossible,whilemain- tainingrobustrecoveryguarantees.Thisamountstoshiftingthemaskbya˝xedstep-size largerthan1,whilemaintainingspatialoverlapbetweenconsecutiveshiftedmasks.Another formofsub-samplingtakesplaceintheFourierdomain,wherethespectrogrammeasure- mentsmaybecollectedatasubsetofequallyspacedFouriermodes.Onecouldalsocombine bothformsofsub-sampling,thusreducingthenumberofmeasurementsdrastically. Inwhatfollows,wediscussphaseretrievalfromsub-sampledshort-timeFouriertransform (STFT)magnitudemeasurementsofavector x 2 C d basedonatwo-stepapproach:˝rst, amodi˝edWignerdistributiondeconvolutionapproachisusedtosolveforaportionofthe 19 liftedrank-onesignal b x b x 2 C d d .Second,anangularsynchronizationapproachisusedto recover b x (andthen,byFourierinversion, x )fromtheknownportionof b x b x .Inaddition tobeingcomputationallye˚cient,theproposedmethodalsogivesinsightintothedesignof goodwindow(orprobe)functions. BeforediscussingaliasedWDDmethods,weintroducesomeadditionalnotationtothat inChapter1.Letsgn : C ! C bethenormalizationmapping sgn ( z )= 8 > > > < > > > : z j z j ; if z 6 =0 ; 1 ; if z =0 : Foragiven n 2 N ,weintroducetheoperator C 2 n 1 : C d (2 n 1) ! C d d de˝nedvia ( C 2 n 1 ( M )) j;k = 8 > > > < > > > : M j;n 1+( k j )mod d ; if j j k j d n; 0 ; otherwise. (2.0.1) Wenote,inparticular,thatthisoperatorpreservestheFrobeniusnorm.Withthede˝nition above, C 2 n 1 ( M ) 2 C d d isacirculantversionof M 2 C d (2 n 1) ,insuchawaythat column n 1 of M (themiddlecolumn)isthediagonalof C 2 n 1 ( M ) .Forexample, C 3 0 B B B B B B B B B B B B B @ 2 6 6 6 6 6 6 6 6 6 6 6 6 6 4 a 0 ; 0 a 0 ; 1 a 0 ; 2 a 1 ; 0 a 1 ; 1 a 1 ; 2 . . . . . . . . . a d 2 ; 0 a d 2 ; 1 a d 2 ; 2 a d 1 ; 0 a d 1 ; 1 a d 1 ; 2 3 7 7 7 7 7 7 7 7 7 7 7 7 7 5 1 C C C C C C C C C C C C C A = 2 6 6 6 6 6 6 6 6 6 6 6 6 6 4 a 0 ; 1 a 0 ; 2 0 a 0 ; 0 a 1 ; 0 a 1 ; 1 a 1 ; 2 0 . . . . . . . . . . . . . . . 0 a d 2 ; 0 a d 2 ; 1 a d 2 ; 2 a d 1 ; 2 0 a d 1 ; 0 a d 1 ; 1 3 7 7 7 7 7 7 7 7 7 7 7 7 7 5 : 20 Givenanaturalnumber s whichdivides d ,weintroducethesub-samplingoperator Z s : C d 1 ! C d s 1 ; de˝nedcomponentwisevia ( Z s u ) n := u n s 8 n 2 d s 0 : Fouriertransformsofsub-sampledvectorshaveanaliasinge˙ectwhichisdescribedinthe lemmabelow.AproofisprovidedintheAppendix. Lemma2.0.1. (Aliasing)Forany d 2 N and s 2 N thatdivides d ,andforany u 2 C d 1 and ! 2 h d s i 0 ,onehas F d s ( Z s u ) ! = 1 s s 1 X r =0 b u ! r d s : Finally,weprovideatechnicallemmawhichprovidesanequivalencebetweentheFourier transformofanautocorrelationofavector x andthatofitsFouriertransform, b x .Aproof isprovidedintheAppendix. Lemma2.0.2. Let x 2 C d 1 and ;! 2 [ d ] 0 .Then ( F d ( x S ! x )) = 1 d e 2 ˇi! d F d b x S b x ! : 2.1AliasedWDDforPhaseRetrieval Inthissection,weexpandontheclassicalWDDmethodtoincludesub-sampling.Speci˝- cally,inSection2.1.1,weprovideaWDDformulationforthecasewhenonecollectsmea- surementsonasmallsubsetofall d Fouriermodesin [ d ] 0 .Next,inSection2.1.2,weexplore 21 furthertoincludethecasewhereoneshiftsthemask m atasubsetofall d possibleshifts in [ d ] 0 .WethenprovidetwoalgorithmsinSection2.1.3whichallowfortherecoveryof aspecimen x fromsub-sampledmeasurementsviaaliasedWDDformulationsandangular synchronization.RecoveryguaranteesarethenprovidedforAlgorithms1and2. 2.1.1Sub-samplinginFrequency Let K beapositiveintegerwhichdivides d ,andassumethatthedataismeasuredat K equallyspacedFouriermodes.Assuch,werestricttheFouriermodesofstep-size d K to K = d K [ K ] 0 = ˆ 0 ; d K ; 2 d K ;:::;d d K ˙ : (2.1.1) De˝nition. Givenamatrix A 2 C d d withcolumns a j ,andaninteger K whichdivides d , wedenoteby A K;d 2 C K d thesubmatrixof A whose ` th columnisequalto Z d K ( a ` ) . ThefollowinglemmaisageneralizationofLemma1.3.5. Lemma2.1.1. Supposethatthemeasurementsin(1.3.9)arecollectedonasubset K [ d ] 0 of K equallyspacedFouriermodes.Thenforany ! 2 [ K ] 0 , F d Y K;d N K;d T F T K ! = K d K 1 X r =0 F d ( x S ! rK x ) F d e m S rK ! e m ; where Y K;d N K;d 2 C K d isthematrixofsub-samplednoiseless K d measurements. Beforeprovidingaproof,wenotethatinthespecialcasewhereonecollectsdataatall d frequenciesin [ d ] 0 ,i.e.,when K = d ,thelemmaabovereducesto(1.3.12): F K Z d K ( y ` ` ) ! =( F d ( y ` ` )) ! = d ( x S ! x ) d e m S ! e m ` : 22 Proof. Letusrecallfrom(1.3.11)thatfor ` 2 [ d ] 0 ,the ` th columnofthematrix Y N is y ` ` = F d ( x S ` m ) d e x S ` e m : Wemaywrite,forany 2 [ K ] 0 , Z d K ( y ` ` ) = F d ( x S ` m ) d e x S ` e m d K : UpontakingaFouriertransformat ! 2 [ K ] 0 ,weget F K Z d K ( y ` ` ) ! = K d d K 1 X r =0 ( b y ` b ` ) ! rK (byLemma2.0.1) = d K d d K 1 X r =0 ( x S ! rK x ) d e m S rK ! e m ` : (by(1.3.12)) Notethatthe ` th columnof Y K;d N K;d 2 C K d isequalto Z d K ( y ` ` ) .Thenthe ! th columnof Y K;d N K;d T F T K 2 C d K ,forany ! 2 [ K ] 0 ,maybecomputedas Y K;d N K;d T F T K ! = K d K 1 X r =0 ( x S ! rK x ) d e m S rK ! e m 2 C d 1 : Takingone˝nalFouriertransformnowyields F d Y K;d N K;d T F T K ! = K d K 1 X r =0 F d ( x S ! rK x ) F d e m S rK ! e m ; (2.1.2) 23 byLemma1.3.2andthelinearityoftheFouriertransform. 2.1.2Sub-samplinginFrequencyandSpace Let L beapositiveintegerwhichdivides d .Letusassumethatthemeasurementsare collectedat L equallyspacedphysicalshiftsofstep-size d L ,sothatthesetofshiftsis L = d L [ L ] 0 = ˆ 0 ; d L ; 2 d L ;:::;d d L ˙ : (2.1.3) De˝nition. Givenamatrix A 2 C d d ,andaninteger L whichdivides d ,wedenoteby A d;L 2 C d L thesubmatrixof A whoserowsarethoseof A ,sub-sampledinstep-size d L . WestateamoregeneralizedversionofLemma2.1.1andLemma1.3.5below. Lemma2.1.2. Supposethatthemeasurementsin(1.3.9)arecollectedonasubset K [ d ] 0 of K equallyspacedfrequenciesandasubset L [ d ] 0 of L equallyspacedphysicalshifts. Thenforany ! 2 [ K ] 0 and 2 [ L ] 0 , F L Y K;L N K;L T F T K ! = KL d 3 d K 1 X r =0 d L 1 X ` =0 F d b x S `L b x ! rK F d b m S `L b m ! rK ; (2.1.4) where Y K;L N K;L 2 C K L isthematrixofsub-samplednoiseless K L measurements. Proof. For˝xed ` 2 [ d ] 0 and ! 2 [ K ] 0 ,wehavecomputed(intheproofofLemma2.1.1) F K Z d K ( y ` ` ) ! = K d K 1 X r =0 ( x S ! rK x ) d e m S rK ! e m ` : 24 Letus˝x ! 2 [ K ] 0 ,andlookatthevector p ! 2 C L 1 ,de˝nedcomponentwisevia ( p ! ) ` := F K Z d K y ` d L ` d L ! 8 ` 2 [ L ] 0 : (2.1.5) Notethattherowsof Y K;L N K;L 2 C K L arethoseof Y K;d N K;d 2 C K d ,sub- sampledinstep-sizeof d L .Withthis,onecanseethat ( p ! ) ` = Y K;L N K;L T F T K ! ` ; where F T K ! 2 C K 1 isthe ! th columnof F T K .Therefore, p ! = Y K;L N K;L T F T K ! 2 C L 1 8 ! 2 [ K ] 0 : Now,observethatforany ` 2 [ L ] 0 ,wehave ( p ! ) ` = K d K 1 X r =0 ( x S ! rK x ) d e m S rK ! e m ` d L = K 0 B B @ Z d L 0 B B @ d K 1 X r =0 ( x S ! rK x ) d e m S rK ! e m 1 C C A 1 C C A ` : Forany 2 [ L ] 0 ,onehasbyLemma2.0.1andLemma1.3.2 ( F L p ! ) = KL d d K 1 X r =0 d L 1 X ` =0 F d ( x S ! rK x ) d e m S rK ! e m `L = KL d d K 1 X r =0 d L 1 X ` =0 ( F d ( x S ! rK x )) `L F d e m S rK ! e m `L : 25 UsingLemma2.0.2,wecanwriteforany ! 2 [ K ] 0 and 2 [ L ] 0 , F L Y K;L N K;L T F T K ! = KL d 3 d K 1 X r =0 d L 1 X ` =0 F d b x S `L b x ! rK F d b e m S `L b e m rK ! : Finally,Lemma1.3.1(7),appliedtothelastFouriertransformintheequalityabove,yields F d b e m S `L b e m rK ! = F d e b e m S `L e b e m ! rK = F d b m S `L b m ! rK : Lemma1.3.5cannowbeseenasacorollaryofLemma2.1.2above;inthespecialcase whereonecollectsdataatallshifts ` 2 [ d ] 0 andallFouriermodes ! 2 [ d ] 0 ,i.e.,when K = L = d ,onehas F d ( Y N ) T F T d ! = d d d 3 d d 1 X r =0 d d 1 X ` =0 F d b x S `d b x ! rd F d b m S `d b m ! rd = 1 d F d b x S b x ! F d b m S b m ! ; whichisanequivalentresulttothatofLemma1.3.5. 2.1.3RecoveringDiagonalsof b x b x Letusassumethat m isband-limitedwithsupp ( b m )=[ ] 0 forsome ˝ d .ThenAlgorithm 1belowallowsfortherecoveryofanestimateof b x fromspectrogrammeasurementsvia Wignerdistributiondeconvolutionandangularsynchronization. 26 Algorithm1WDDandAngularSynchronizationforBand-limitedMasks Inputs 1: Y d;L 2 C d L :matrixof d L noisymeasurementsoftheform ( y ` ) k = d 1 X n =0 x n m n ` e 2 ˇink d 2 + k;` ; ( k;` ) 2 [ d ] 0 d L [ L ] 0 : (2.1.6) 2: Band-limitedmask(orwindow) m 2 C d 1 ,withsupp ( b m )=[ ] 0 . 3: Integer ,sothat 2 1 diagonalsof b x b x areestimated,and L = + 1 . Steps 1: Estimatetheperturbedvectors F d b x S b x (assumingnonoise)accordingto F d b x S b x ˇ d 2 F d Y d;L F T L L F d b m S b m 8 2 [ ] 0 ; F d b x S L b x ˇ d 2 F d Y d;L F T L L F d b m S L b m 8 2 [ L ] 0 n [ L +1] 0 : 2: InverttheFouriertransformsabovetorecoverestimatesofthe (2 1) vectors b x S b x . 3: Formthebandedmatrix C 2 1 ( Y 2 1 ) fromthemeasurementsinstep2. 4: Hermitianizethematrixabove: C 2 1 ( Y 2 1 ) [ 1 2 C 2 1 ( Y 2 1 )+ C 2 1 ( Y 2 1 ) . 5: Estimate j b x j fromthediagonalof C 2 1 ( Y 2 1 ) . 6: Normalize C 2 1 ( Y 2 1 ) componentwisetoform e Y 2 1 . 7: Computetheleadingeigenvector, u ,of e Y 2 1 . Output Anestimate b x e (uptoaglobalphase)to b x ,givencomponentwisevia: ( b x e ) j := q ( C 2 1 ( Y 2 1 )) j;j u j : 27 Lemma2.1.3. Let x 2 C d 1 bearbitraryand m 2 C d 1 withsupp ( b m )=[ ] 0 .Assume d L 2 N ,andlet Y d;L 2 C d L contain d L noisyautocorrelationmeasurementsasin(2.1.6). Thenforany 2 [ L ] 0 and ! 2 [ d ] 0 , F L Y d;L N d;L T F T d ! = L d 2 d L 1 X ` =0 F d b x S `L b x ! F d b m S `L b m ! : (2.1.7) Moreover,if L = + 1 forsome 1 ,thenforall ! 2 [ d ] 0 thesumabovereduces toexactlyonetermasfollows: d 2 L F L Y d;L N d;L T F T d ! = 8 > > > < > > > : F d b x S b x ! F d b m S b m ! ; if 2 [ ] 0 ; F d b x S L b x ! F d b m S L b m ! ; if 2 [ L ] 0 n [ ] 0 : Proof. Equation(2.1.7)followsfromequation(2.1.4)inLemma2.1.3bysetting K = d .It remainstoshowthatif L ischosensothat L = 1+ forsome 1 and ischosen in [ L ] 0 nf +1 ;:::;L g ,thenthesumreducestoasingletermforall ! 2 [ d ] 0 . Tothatend,assumethatsupp ( b m )=[ ] 0 forsome ˝ d andset L = 1+ .Observe that b m S `L b m = 0 wheneverthesupportsof b m and S `L b m aredisjoint.Notethat supp ( b m ) \ supp S `L b m 6 = ;()j `L j 1 : Now,since L 2 1 ,thenforany 2 [ ] 0 , j `L j 1 ifandonlyif ` =0 ,andfor any 2f L +1 ;:::;L 1 g , j `L j 1 ifandonlyif ` =1 . WearenowreadytoproviderecoveryguaranteesforAlgorithm1. 28 Theorem2.1.1. Let x 2 C d 1 bearbitraryand m 2 C d 1 withsupp ( b m )=[ ] 0 .Let L = + 1 forsome 1 ,andassume L divides d .Let Y d;L 2 C d L contain d L noisyautocorrelationmeasurementsasin(2.1.6).De˝ne S := ( n : j b x n j < 1 4 N d;L 1 4 F ) ; (2.1.8) andlet > 0 denotethemask-dependentconstant :=min j p 1 q 2 [ d ] 0 F d b m S p b m q : (2.1.9) ThenAlgorithm1outputsanestimate b x e to b x with min ˚ 2 [0 ; 2 ˇ ] b x e i˚ b x e 2 C 0 k b x k 1 d 2 2 s 4 2 N d;L F + j S j + C 00 d 5 L 1 4 s N d;L F ; (2.1.10) forsomeconstants C 0 ;C 00 2 R .If = N d;L F min j b x j 4 ,then min ˚ 2 [0 ; 2 ˇ ] b x e i˚ b x e 2 C 0 d 4 k b x k 1 N d;L F L 1 2 5 2 min j b x j 2 + C 00 d 5 4 N d;L 1 2 F L 1 4 1 2 : (2.1.11) Proof. Let x , m ,andthemeasurementsbeasinTheorem2.1.1.ByLemma2.1.3, F d b x S b x = d 2 L F d Y d;L N d;L F T L F d b m S b m 8 2 [ ] 0 ; F d b x S L b x = d 2 L F d Y d;L N d;L F T L F d b m S L b m 8 2 [ L ] 0 n [ L +1] 0 ; 29 wherethedivisioniscomponentwise.Thus,the (2 1) diagonalsoftherank-onematrix b x b x canbecomputedas b x S b x = d 2 L F 1 d 0 @ F d Y d;L N d;L F T L F d b m S b m 1 A 8 2 [ ] 0 ; b x S L b x = d 2 L F 1 d 0 @ F d Y d;L N d;L F T L F d b m S L b m 1 A 8 2 [ L ] 0 n [ L +1] 0 : DistributingtheinverseFouriertransformyields b x S b x + d 2 L F 1 d 0 @ F d N d;L F T L F d b m S b m 1 A = d 2 L F 1 d 0 @ F d Y d;L F T L F d b m S b m 1 A forall 2 [ ] 0 ,and b x S L b x + d 2 L F 1 d 0 @ F d N d;L F T L F d b m S L b m 1 A = d 2 L F 1 d 0 @ F d Y d;L F T L F d b m S L b m 1 A forall 2 [ L ] 0 n [ L +1] 0 .Onecanthuslearn (2 1) diagonalsof b x b x exactlyassuming thenoiseisknownandthemask m ischosensothat (asin(2.1.9))ispositive.Inpractice, however, N d;L isentirelyunknown,saveforpossiblyanestimateonitsnorm. Letusdenoteby X 2 1 2 C d (2 1) thematrixwithcolumns b x S ˙ b x ; j ˙ j 1 ; orderedbyincreasing ˙ .Also,denoteby N 2 1 2 C d (2 1) thematrixwithordered 30 columns d 2 L F 1 d 0 @ F d N d;L F T L F d b m S b m 1 A ; 2f 1 ; 2 ;:::; 0 g ; and d 2 L F 1 d 0 @ F d N d;L F T L F d b m S L b m 1 A ; 2f 2 2 ; 2 3 ;:::;k g : Similarly,denoteby Y 2 1 2 C d (2 1) thematrixwithorderedcolumns d 2 L F 1 d 0 @ F d Y d;L F T L F d b m S b m 1 A ; 2f 1 ; 2 ;:::; 0 g ; and d 2 L F 1 d 0 @ F d Y d;L F T L F d b m S L b m 1 A ; 2f 2 2 ; 2 3 ;:::;k g : Then Y 2 1 = X 2 1 + N 2 1 : (2.1.12) Using k F d k 2 = p d and F 1 d 2 = 1 p d ,wecomputethefollowingboundontheFrobenius normof N 2 1 : k Y 2 1 X 2 1 k 2 F = k N 2 1 k 2 F d 4 L 2 1 p d 2 F d N d;L F T L 2 F 2 = d 3 L 2 2 L d N d;L 2 F = d 4 2 N d;L 2 F ; 31 where isasin(2.1.9).Thus, k N 2 1 k F d 2 p N d;L F : (2.1.13) Now,onecanwrite(2.1.12)intoacirculantformusingtheoperator C 2 1 de˝nedin(2.0.1): C 2 1 ( X 2 1 )= C 2 1 ( Y 2 1 ) C 2 1 ( N 2 1 ) : Finally,let e X 2 1 and e Y 2 1 bethe(componentwise)normalizedversionsofthematrices C 2 1 ( X 2 1 ) and C 2 1 ( Y 2 1 ) ,respectively: e X 2 1 := C 2 1 ( sgn ( X 2 1 )) ; e Y 2 1 := C 2 1 ( sgn ( Y 2 1 )) : Let S beasin(2.1.8).Forany j;k 2 S c ,webound e X 2 1 j;k e Y 2 1 j;k asfollows: e X 2 1 j;k sgn 0 @ ( C 2 1 ( Y 2 1 )) j;k ( C 2 1 ( X 2 1 )) j;k 1 A e X 2 1 j;k ( C 2 1 ( Y 2 1 )) j;k ( C 2 1 ( X 2 1 )) j;k + ( C 2 1 ( Y 2 1 )) j;k ( C 2 1 ( X 2 1 )) j;k sgn 0 @ ( C 2 1 ( Y 2 1 )) j;k ( C 2 1 ( X 2 1 )) j;k 1 A 2 e X 2 1 j;k ( C 2 1 ( Y 2 1 )) j;k ( C 2 1 ( X 2 1 )) j;k 32 =2 ( C 2 1 ( N 2 1 )) j;k ( C 2 1 ( X 2 1 )) j;k 2 q N d;L 1 F ( C 2 1 ( N 2 1 )) j;k : Thelastinequalityholdssince j;k 2 S c ,whence 1 b x k b x j > 1 2 N d;L 1 2 F : Wecannowcalculate e Y 2 1 e X 2 1 2 F X j;k 2 S c 4 N d;L F ( C 2 1 ( N 2 1 )) j;k 2 + X j or k 2 S e X 2 1 j;k e Y 2 1 j;k 2 4 N d;L F k N 2 1 k 2 F + X j 2 S 4(4 3) 4 4 2 N d;L F +4(4 3) j S j ; wherethelastinequalityfollowsfrom(2.1.13).Thus,thereexistsaconstant C 0 2 R such that e Y 2 1 e X 2 1 2 F C 0 4 2 N d;L F + j S j : Since e X 2 1 F = p (2 1) d; wecanwrite e Y 2 1 e X 2 1 F C s d 1 4 2 N d;L F + j S j e X 2 1 F 33 forsomeuniversalconstant C .Now,byCorollary2of[36],wehave min 2 [0 ; 2 ˇ ] b x j b x j e sgn ( u ) 2 C 0 s d 1 4 2 N d;L F + j S j d 5 2 2 ; (2.1.14) where b x j b x j isthevectoroftruephasesof b x ,and u isthetopeigenvectorof e Y 2 1 . Let b x e betheestimateof b x producedbyAlgorithm1,sothat ( b x e ) j = q ( C 2 1 ( Y 2 1 )) j;j sgn ( u ) j 8 j 2 [ d ] 0 : Wecompute min ˚ 2 [0 ; 2 ˇ ] b x e i˚ b x e 2 =min ˚ 2 [0 ; 2 ˇ ] j b x j b x j b x j j b x e j e i˚ b x e j b x e j 2 min ˚ 2 [0 ; 2 ˇ ] j b x j b x j b x j j b x j e i˚ b x e j b x e j 2 + j b x j e i˚ b x e j b x e j j b x e j e i˚ b x e j b x e j 2 ; wherethesecondtermisindependentof ˚ .Wethushave min ˚ 2 [0 ; 2 ˇ ] b x e i˚ b x e 2 k b x k 1 min ˚ 2 [0 ; 2 ˇ ] b x j b x j e i˚ b x e j b x e j 2 ! + C 00 s p d d 2 p N d;L F forsomeabsoluteconstant C 00 > 0 .HeretheboundonthesecondtermfollowsfromLemma 3of[37]andtheCauchy-Schwartzinequality.Combiningtheboundabovewith(2.1.14) yields min ˚ 2 [0 ; 2 ˇ ] b x e i˚ b x e 2 C 0 k b x k 1 p d s 4 2 N d;L F + j S j d 5 2 2 + C 00 v u u t d 5 2 p N d;L F = C 0 k b x k 1 d 2 2 s 4 2 N d;L F + j S j + C 00 d 5 L 1 4 s N d;L F : 34 Notethatif = N d;L F min j b x j 4 ,then S = ; ,andthus min ˚ 2 [0 ; 2 ˇ ] b x e i˚ b x e 2 C 0 d 4 k b x k 1 N d;L F L 1 2 5 2 min j b x j 2 + C 00 d 5 4 N d;L 1 2 F L 1 4 1 2 : Inordertoguaranteethattheconstant isnonzero,westatethefollowinglemma. Lemma2.1.4. Let m 2 C d 1 beband-limitedto [ ] 0 ,sothatitsFouriertransformis b m = a 0 e 0 ;:::;a 1 e 1 ; 0 ;:::; 0 T forsomerealnumbers a 0 ;:::;a 1 .Let :=min j p 1 q 2 [ d ] 0 F d b m S p b m q ; where 1 .If j a 0 j > ( 1) j a 1 j (2.1.15) and j a 1 jj a 2 jj a 1 j > 0 ; (2.1.16) then > 0 : 35 Proof. For 0 p 1 ,wehave b m S p b m n = 8 > > > < > > > : a n a n + p e i n n + p ; if n 2 [ p ] 0 ; 0 ; otherwise, andfor +1 p< 0 , b m S p b m n = 8 > > > < > > > : a n p j a n e i n n p j ; if n 2fj p j ; j p j +1 ;:::; 1 g ; 0 ; otherwise. Thereforeforany q 2 [ d ] 0 , F d b m S p b m q = 1 p j X n =0 a n a j p j + n e i˚ n;p;q ; where ˚ n;p;q issomerealnumberdependingonlyon n;p; and q: Usingtheassumptions (2.1.15)and(2.1.16)weseethat 1 p j X n =1 a n a j p j + n e i˚ n;p;q ( 1) j a 1 j a 1+ j p j < j a 0 j a j p j : (2.1.17) Withthis, F d b m S p b m q = 1 p j X n =0 a n a j p j + n e i˚ n;p;q = a 0 a j p j e i˚ 0 ;p;q + 1 p j X n =1 a n a j p j + n e i˚ n;p;q 36 a 0 a j p j e i˚ 0 ;p;q 1 p j X n =1 a n a j p j + n e i˚ n;p;q = a 0 a j p j 1 p j X n =1 a n a j p j + n e i˚ n;p;q > 0 ; wherethelastinequalityfollowsby(2.1.17).Thiscompletestheproof. TheinterestedreadermayreadProposition2onpage63of[48]foraconnectionbetween andtheconditionnumberofthemeasurementsystem. 2.1.3.1ASpecialCaseofTheorem2.1.1 LetusconsiderthespecialcaseofTheorem2.1.1,where =2 sothatsupp ( b m )= f 0 ; 1 g , = =2 sothat L =3 .Wemaydesign m 2 C d 1 sothat b m = ae i ;be i˚ ; 0 ;:::; 0 T forsomenonzero a;b 2 R ,with j a j > j b j .Forthischoiceofmask,wehaveforany ! 2 [ d ] 0 : F d b m b m ! = F d a 2 ;b 2 ; 0 ;:::; 0 T ! = a 2 + b 2 e 2 ˇi! d 6 =0 ; F d b m S 1 b m ! = F d abe i ( ˚ ) ; 0 ;:::; 0 T ! = abe i ( ˚ ) 6 =0 ; F d b m S 1 b m ! = F d 0 ;abe i ( ˚ ) ; 0 ;:::; 0 T ! = abe i ( ˚ ) e 2 ˇi! d 6 =0 : Themask-dependentconstant is :=min ! 2 [ d ] 0 ˆ j ab j ; a 2 + b 2 e 2 ˇi! d ˙ > 0 : 37 Wehave b x S p b x + d 2 3 F 1 d 0 B @ F d N d; 3 F T 3 p F d b m S p b m 1 C A = d 2 3 F 1 d 0 B @ F d Y d; 3 F T 3 p F d b m S p b m 1 C A ;p 2 1 ; 0 ; 1 g : Letusdenoteby X 3 2 C d 3 thematrixwithcolumns b x S 1 b x , b x b x ,and b x S 1 b x ,sothat X 3 = 2 6 6 6 6 6 6 6 6 6 4 b x 0 b x d 1 j b x 0 j 2 b x 0 b x 1 b x 1 b x 0 j b x 1 j 2 b x 1 b x 2 . . . . . . . . . b x d 1 b x d 2 j b x d 1 j 2 b x d 1 b x 0 3 7 7 7 7 7 7 7 7 7 5 ; andby Y 3 ;N 3 2 C d 3 thematrices Y 3 = d 2 3 F 1 d ([ 1 j 0 j 1 ]) ;N 3 = d 2 3 F 1 d ([ ˚ 1 j ˚ 0 j ˚ 1 ]) ; whosecolumnsaregivenby p := F d Y d; 3 F T 3 p F d b m S p b m ;˚ p := F d N d; 3 F T 3 p F d b m S p b m : Wemaywrite C 3 ( X 3 )= C 3 ( Y 3 ) C 3 ( N 3 ) ; 38 where C 3 ( X 3 )= 2 6 6 6 6 6 6 6 6 6 6 6 6 6 4 j b x 0 j 2 b x 0 b x 1 0 b x 0 b x d 1 b x 1 b x 0 j b x 1 j 2 b x 1 b x 2 0 . . . . . . . . . . . . . . . 0 b x d 2 b x d 3 j b x d 2 j 2 b x d 2 b x d 1 b x d 1 b x 0 0 b x d 1 b x d 2 j b x d 1 j 2 3 7 7 7 7 7 7 7 7 7 7 7 7 7 5 isabandedversionoftherank-onematrix b x b x 2 C d d .Finally,let e X 3 , e Y 3 ,and e N 3 bethe (componentwise)normalizedversionsof C 3 ( X 3 ) , C 3 ( Y 3 ) ,and C 3 ( N 3 ) ,respectively,sothat if b x = j b x 0 j e 0 ;:::; j b x d 1 j e d 1 ,then e X 3 = 2 6 6 6 6 6 6 6 6 6 6 6 6 6 4 1 e i ( 0 1 ) 0 e i 0 d 1 e i ( 1 0 ) 1 e i ( 1 2 ) 0 . . . . . . . . . . . . . . . 0 e i d 2 d 3 1 e i d 2 d 1 e i d 1 0 0 e i d 1 d 2 1 3 7 7 7 7 7 7 7 7 7 7 7 7 7 5 : Wehave e Y 3 = e X 3 + e N 3 : Asbefore,de˝netheset S := ( n : j b x n j < 1 4 N d; 3 1 4 F ) ; 39 andlet b x e betheestimateof b x producedbyAlgorithm1.Then min ˚ 2 [0 ; 2 ˇ ] b x e i˚ b x e 2 C 0 k b x k 1 d 2 2 2 s 4 3 2 N d; 3 F + j S j + C 00 d 5 4 s N d; 3 F p 3 : Additionally,if = N d; 3 F min j b x j 4 ,then S = ; and min ˚ 2 [0 ; 2 ˇ ] b x e i˚ b x e 2 C 0 d 4 k b x k 1 N d; 3 F min j b x j 2 + C 00 d 5 4 N d; 3 1 2 F 1 2 : 2.1.4OtherSupportConditions Wehaveconsideredabovethecasewherethemask m 2 C d 1 isband-limitedsothat supp ( b m )=[ ] 0 with ˝ d ,and x 2 C d 1 isarbitrary.Letusnowconsiderothercaseson thesupportsof x ; b x ; m ; and/or b m . Lemma2.1.5. Let x 2 C d 1 bearbitraryand m 2 C d 1 withsupp ( m )=[ ˆ ] 0 .Assume d K 2 N ,andlet Y K;d 2 R K d containnoisyautocorrelationmeasurementsoftheform ( y ` ) k = d 1 X n =0 x n m n ` e 2 ˇink d 2 + k;` ; ( k;` ) 2 d K [ K ] 0 [ d ] 0 : Thenforany 2 [ d ] 0 and ! 2 [ K ] 0 , F d Y K;d N K;d T F T K ! = K d 2 d K 1 X r =0 F d b x S b x ! rK F d b m S b m ! rK (2.1.18) 40 = K d K 1 X r =0 ( F d ( x S ! rK x )) ( F d ( m S ! rK m )) : (2.1.19) Moreover,if K = ˆ 1+ forsome 1 ˆ ,andif ! 2 [ K ] 0 nf +1 ;:::;K g , thenforall 2 [ d ] 0 ,thesumabovecollapsestoonlyonetermasfollows: F d Y K;d N K;d T F T K ! = 8 > > > < > > > : K ( F d ( x S ! x )) ( F d ( m S ! m )) ; if ! 2 [ ] 0 ; K ( F d ( x S ! K x )) ( F d ( m S ! K m )) ; if ! 2 [ K ] 0 n [ K +1] 0 : Proof. Theequalityin(2.1.18)followsfromLemma2.1.2with L = d ,while(2.1.19)holds bybyLemma2.0.2: F d b x S b x ! rK = d e 2 ˇ ( ! rK ) d ( F d ( x S ! rK x )) ; F d b m S b m ! rK = d e +2 ˇ ( ! rK ) d ( F d ( m S ! rK m )) : Itremainstoshowthatif K ischosensothat K = ˆ 1+ forsome 1 ˆ and ! ischosenfrom [ K ] 0 nf +1 ;:::;K g ,thenthesumreducestoasingletermforall 2 [ d ] 0 . Assumethatsupp ( m )=[ ˆ ] 0 forsome ˆ ˝ d andset K = ˆ 1+ .Observethat m S ! rK m = 0 wheneverthesupportsof m and S ! rK m aredisjoint.Now, supp ( m ) \ supp ( S ! rK m ) 6 = ;()j ! rK j ˆ 1 : 41 Notethatsince K 2 ˆ 1 ,forany ! 2 [ ] 0 , j ! rK j ˆ 1 ifandonlyif r =0 ,andfor any ! 2f K +1 ;:::;K 1 g , j ! rK j ˆ 1 ifandonlyif r =1 . Wehavesofarconsideredconditionsonthesupportsofthemask m oritsFourier transform b m .Next,weconsiderthee˙ectofimposingsupportconditionson b x . Lemma2.1.6. Let x 2 C d 1 bearbitrarywithsupp ( b x )=[ ] 0 and m 2 C d 1 with supp ( m )=[ ˆ ] 0 .Assume L and K divide d ,andlet Y K;L 2 R K L containnoisyauto- correlationmeasurementsoftheform ( y ` ) k = d 1 X n =0 x n m n ` e 2 ˇink d 2 + k;` ; ( k;` ) 2 d K [ K ] 0 d L [ L ] 0 : Thenforany 2 [ L ] 0 and ! 2 [ K ] 0 , F L Y K;L N K;L T F T K ! = KL d 3 d K 1 X r =0 d L 1 X ` =0 F d b x S `L b x ! rK F d b m S `L b m ! rK = KL d 2 d K 1 X r =0 d L 1 X ` =0 e 2 ˇi d ( ! rK )( `L ) F d b x S `L b x ! rK ( F d ( m S ! rK m )) `L : Moreover,if K = ˆ 1+ forsome 1 ˆ and L = 1+ ˘ forsome 1 ˘ ,then forall ! 2 [ K ] 0 nf +1 ;:::;K g and 2 [ L ] 0 nf ˘;˘ +1 ;:::;L ˘ g ,thesumabove collapsestoonlyoneterm,sothat F L Y K;L N K;L T F T K ! isequalto 1. KL d 3 F d b x S b x ! F d b m S b m ! if ! 2 [ ] 0 and 2 [ ˘ ] 0 ,or 2. KL d 3 F d b x S L b x ! F d b m S L b m ! if 2f L ˘ +1 ;:::;L 1 g and ! 2 [ ] 0 ,or 42 3. KL d 3 F d b x S b x ! K F d b m S b m ! K if ! 2f K +1 ;:::;K 1 g and 2 [ ˘ ] 0 ,or 4. KL d 3 F d b x S L b x ! K F d b m S L b m ! K if ! 2f K +1 ;:::;K 1 g and 2f L ˘ +1 ;:::;L 1 g . Proof. Theequivalenceofthetwodoublesumsinthelemmaaboveisanapplicationof Lemma2.0.2.Let'sconsidertheseconddoublesum;usingtheargumentfromLemma2.1.5, weobservethefollowingcases: 1. If ! 2 [ ] 0 and 2 [ ˘ ] 0 ,thesumreducesto r =0 and ` =0 . 2. If ! 2 [ ] 0 and 2f L ˘ +1 ;:::;L 1 g ,thesumreducesto r =0 and ` =1 . 3. If ! 2f K +1 ;:::;K 1 g and 2 [ ˘ ] 0 ,thesumreducesto r =1 and ` =0 . 4. If ! 2f K +1 ;:::;K 1 g and 2f L ˘ +1 ;:::;L 1 g ,thesumreducesto r =1 and ` =1 . Ifwethinkof b x S j b x , j j j ˘ 1 ,ascolumnsofamatrix e X 2 ˘ 1 2 C d (2 ˘ 1) ; thenthe theoremaboveallowsustorecoverestimatesofthe˝rst andlast 1 entriesofeachof thecolumnsof F d e X 2 ˘ 1 2 C d (2 ˘ 1) : 2.1.4.1ASpecialCaseofLemma2.1.6. Wepresentbelowanalgorithmwhichallowsfortherecoveryofaband-limitedsignal x throughmeasurementswithacompactlysupportedmask m .Speci˝cally,ifsupp ( b x )=[ ] 0 andsupp ( m )= ˆ ,then b x mayberecoveredfrom (2 ˆ 1) (2 1) measurementsas prescribedinAlgorithm2. 43 Algorithm2AliasedWDDandAngularSynchronizationforBand-limited x Inputs 1: Y K;L 2 R K L :matrixof KL noisymeasurementsoftheform ( y ` ) k = d 1 X n =0 x n m n ` e 2 ˇink d 2 + k;` ; ( k;` ) 2 d K [ K ] 0 d L [ L ] 0 : (2.1.20) 2: Spatially-limitedmask(orwindow) m 2 C d 1 . 3: Integers and ˆ ,supportsizesof b x and m ,respectively,sothat L =2 1 , K =2 ˆ 1 . Steps 1: Estimate F d b x S ˙ b x (assumingnonoise)for j ˙ j 1 and j j ˆ 1 as: if ! 2 [ ˆ ] 0 and 2 [ ] 0 ,then F d b x S b x ! ˇ d 3 KL F L Y T K;L F T K ! F d b m S b m ! ; if ! 2 [ ˆ ] 0 and 2f ;:::; 2 2 g ,then F d b x S L b x ! ˇ d 3 KL F L Y T K;L F T K ! F d b m S L b m ! ; if ! 2f ˆ;:::; 2 ˆ 2 g and 2 [ ] 0 ,then F d b x S b x ! K ˇ d 3 KL F L Y T K;L F T K ! F d b m S b m ! K ; if ! 2f ˆ;:::; 2 ˆ 2 g and 2f ;:::; 2 2 g ,then F d b x S L b x ! K ˇ d 3 KL F L Y T K;L F T K ! F d b m S L b m ! K : 44 Algorithm2Continued 2: Organizetheestimatesof F d b x S ˙ b x inamatrix V 2 C (2 ˆ 1) (2 1) . 3: Compute W + V asanestimateto A 2 C (2 1) ,where W j;k = e 2 ˇi ( j ˆ +1) k d ; ( j;k ) 2 [2 ˆ 1] 0 [ ] 0 ; W + =( W W ) 1 W 2 C (2 ˆ 1) ; A = 2 6 6 6 6 6 6 6 6 6 6 6 6 6 4 0 0 j b x 0 j 2 b x 0 b x 1 b x 0 b x 1 0 b x 1 b x 0 j b x 1 j 2 b x 1 b x 2 0 . . . . . . . . . . . . . . . . . . . . . 0 b x 2 b x 3 b x 2 2 b x 2 b x 1 0 b x 1 b x 0 b x 1 b x 2 b x 1 2 0 0 3 7 7 7 7 7 7 7 7 7 7 7 7 7 5 : (2.1.21) 4: From W + V ,formanestimate G 2 C totherank-onematrix b x j [ ] 0 b x j [ ] 0 = 2 6 6 6 6 6 6 6 6 6 4 j b x 0 j 2 b x 0 b x 1 b x 0 b x 2 b x 0 b x 1 b x 1 b x 0 j b x 1 j 2 b x 1 b x 2 b x 1 b x 1 . . . . . . . . . . . . . . . b x 1 b x 0 b x 1 b x 1 b x 1 b x 2 b x 1 2 3 7 7 7 7 7 7 7 7 7 5 : 5: Hermitianizethematrix G above: G [ 1 2 ( G + G ) . 6: Compute 1 ; thelargestmagnitudeeigenvalueof G ,and v 1 ,itsassociatedeigenvector. Output Anestimate b x e (uptoaglobalphase)to b x ,givencomponentwisevia ( b x e ) j = 8 > > > < > > > : p j 1 j ( v 1 ) j ; if j 2 [ ] 0 ; 0 ; otherwise. 45 WearenowreadytoproviderecoveryguaranteesforAlgorithm2. Theorem2.1.2. Let x 2 C d 1 beband-limitedsothatsupp ( b x )=[ ] 0 and m 2 C d 1 with supp ( m )=[ ˆ ] 0 .Let L =2 1 and K =2 ˆ 1 ,andassume ˆ and d L ; d K 2 N . Let Y K;L 2 C K L contain KL noisyautocorrelationmeasurementsasin(2.1.20),with N K;L F k b x k 2 2 forsome 0 .Let > 0 denotethemask-dependentconstant :=min j p 1 j q ˆ 1 F d b m S p b m q : (2.1.22) ThenAlgorithm2outputsanestimate b x e to b x with min ˚ 2 [0 ; 2 ˇ ] e i˚ b x b x e 2 1+2 p 2 ˙ min ( W ) d 3 p K k b x k 2 ; (2.1.23) where W isthepartialDFTmatrixdescribedin(2.1.21). Proof. LetusconsiderthespecialcaseofLemma2.1.6where L and K arechosenas L :=2 1 ;K :=2 ˆ 1 ; where and ˆ arethesupportsizesof b x and m ,respectively.Thenwehavethefollowing: 1. if ! 2 [ ˆ ] 0 and 2 [ ] 0 ,then F d b x S b x ! + d 3 KL F L N T K;L F T K ! F d b m S b m ! = d 3 KL F L Y T K;L F T K ! F d b m S b m ! ; 46 2. if ! 2 [ ˆ ] 0 and 2f ;:::; 2 2 g ,then F d b x S L b x ! + d 3 KL F L N T K;L F T K ! F d b m S L b m ! = d 3 KL F L Y T K;L F T K ! F d b m S L b m ! ; 3. if ! 2f ˆ;:::; 2 ˆ 2 g and 2 [ ] 0 ,then F d b x S b x ! K + d 3 KL F L N T K;L F T K ! F d b m S b m ! K = d 3 KL F L Y T K;L F T K ! F d b m S b m ! K ; 4. if ! 2f ˆ;:::; 2 ˆ 2 g and 2f ;:::; 2 2 g ,then F d b x S L b x ! K + d 3 KL F L N T K;L F T K ! F d b m S L b m ! K = d 3 KL F L Y T K;L F T K ! F d b m S L b m ! K : Letusrepresentthefourcasesabovewithamatrixequation T + U = V; where T;U;V 2 C (2 ˆ 1) (2 1) haveentries F d b x S b x ! ; d 3 KL F L N T K;L F T K ! F d b m S b m ! ; d 3 KL F L Y T K;L F T K ! F d b m S b m ! ; respectively,forproperlychosen and ! .Let beasin(2.1.22).Wecomputethefollowing bound: k V T k 2 F = k U k 2 F 47 d 6 K 2 L 2 F L N K;L F T K 2 F 2 = d 6 K 2 L 2 2 L K N K;L 2 F = d 6 K 2 N K;L 2 F ; sothat k U k F d 3 p K N K;L F : (2.1.24) Inshort,weareabletoestimate F d b x S ˙ b x ˚ forall j ˙ j 1 and j ˚ j ˆ 1 .Observefurthermorethatforallsuch ˚ and ˙ , F d b x S ˙ b x ˚ = 1 X n =0 e 2 ˇi˚n d b x n b x n + ˙ =: v ˚ a ˙ where v ˚ isthe ˚ th rowofthematrix W 2 C (2 ˆ 1) and a ˙ isthe ˙ th columnofthe matrix A 2 C (2 1) asin(2.1.21). Onecanorganizethe (2 ˆ 1) (2 1) valuesof F d b x S ˙ b x ˚ inthematrix T 2 C (2 ˆ 1) (2 1) sothat T (2 ˆ 1) (2 1) = W (2 ˆ 1) A (2 1) : 48 Sincethemeasurementsarecontaminatedwithnoise,wehave T + U = WA + U = V; sothat W + V = A + W + U; where W + =( W W ) 1 W 2 C (2 ˆ 1) isthepseudoinverseof W .Thismatrixexistssince ˆ andsince W isfull-rank(being thetransposeofaVandermondematrix).Wehave W + V A F = W + U F W + 2 k U k F 1 ˙ min ( W ) d 3 p K N K;L F ; wherethelastinequalityfollowsfrom(2.1.24). Onceanestimateofthematrix A 2 C (2 1) iscomputedas W + V ,onecanforman estimate G 2 C oftherank-onematrix b x j [ ] 0 b x j [ ] 0 = 2 6 6 6 6 6 6 6 6 6 4 j b x 0 j 2 b x 0 b x 1 b x 0 b x 2 b x 0 b x 1 b x 1 b x 0 j b x 1 j 2 b x 1 b x 2 b x 1 b x 1 . . . . . . . . . . . . . . . b x 1 b x 0 b x 1 b x 1 b x 1 b x 2 b x 1 2 3 7 7 7 7 7 7 7 7 7 5 ; 49 where b x j [ ] 0 = b x 0 ;:::; b x 1 T 2 C 1 .Wehave G b x j [ ] 0 b x j [ ] 0 F A W + V F 1 ˙ min ( W ) d 3 p K N K;L F : Giventhat N K;L F k b x k 2 2 forsome 0 ,weobtain G b x j [ ] 0 b x j [ ] 0 F ˙ min ( W ) d 3 p K k b x k 2 2 : Finally,byLemma8of[36],if i isthe i th largestmagnitudeeigenvalueof G and v i an associatedeigenvector,suchthatthe v i formanorthonormaleigenbasis,then min 2 [0 ; 2 ˇ ] e b x b x e 2 =min 2 [0 ; 2 ˇ ] e b x j [ ] 0 p j 1 j v 1 2 1+2 p 2 ˙ min ( W ) d 3 p K k b x k 2 : Remark2.1.1. WhilethereareliteraryworksontheconditionnumbersofVandermonde matrices(seeforexample[2]),theformulationsthereindonotapplytothematrix W above. Beforeexploringtheproposedalgorithmsnumerically,wenotethattherecoveryguar- antees(upperbounds)providedinthischaptersu˙erfromadependenceonpowersofthe signaldimension, d .Anaturalquestionarisesthen,concerningthelowerLipschitzbounds forphaseretrievalfromlocallysupportedmeasurements.ThisisthetopicofChapter3.As wewillsee,thedependenceonpowersof d isnotentirelyoutoftheordinary. 50 2.2NumericalResults Numericalexperimentsdemonstratingtherobustnessande˚ciencyoftheproposedframe- work,aswellascomparisonstoexistingphaseretrievalalgorithmsarenowpresented.These resultsweregeneratedusingtheopensource BlockPR Matlabsoftwarepackage(freelyavail- ableat[34])onalaptopcomputerwithanIntel r Core TM M-5Y10c(5 th generation,dual core)processor,8GBRAM,andrunningGNU/Linux(Ubuntu16.04 x86_64 )andMat- labR2018a.Eachdatapointintheexecutiontimeandrobustnessplotswasobtainedby averagingresultsfrom 100 trials. Unlessotherwisestated,weusei.i.d.zero-meancomplexGaussianrandomtestsignals withmeasurementerrorsmodeledusinga(real)i.i.d.Gaussiannoisemodel.Inparticular, appliedmeasurementnoiseandreconstructionerrorarebothreportedindecibels(dB)in termsofsignal-to-noiseratios(SNRs),with SNR(dB) =10log 10 P D 1 jh x ; m k ;` ij 4 D˙ 2 ! ; Error(dB) =10log 10 min k e x e x k 2 2 k x k 2 2 ! ; where m k ;` = W k S ` m isoneof D shiftedandmodulatedversionsofthemask m ,and x ; x e ;˙ 2 and D = KL denotethetruesignal,recoveredsignal,(Gaussian)noisevariance, andnumberofmeasurementsrespectively. Forcompleteness,wealsopresentselectedresultscomparingtheproposedformulation againstotherwellestablishedphaseretrievalalgorithmssuchas PhaseLift [16](implemented asatrace-regularizedleast-squaresproblemusingthe˝rstorderconvexoptimizationpackage TFOCS[9,8], HybridInput-Output/ErrorReduction(HIO+ER) alternatingprojectional- gorithm[7,23],and WirtingerFlow [13].Wenotethatmoreaccurateresultsusing PhaseLift maybeobtainedusingothersolversandsoftwarepackages(suchasCVX[26,25]),albeitat 51 prohibitivelyexpensivecomputationalcosts.FortheHIO+ERalgorithm,thefollowingtwo projectionswereutilized:(i)projectionontothemeasuredmagnitudes,and(ii)projection ontothespanofthemeasurementvectors f m k;` g = W k S ` m .Theinitialguesswas settobetheall-zerovector,althoughuseofarandomstartingguessdidnotchangethe qualitativenatureoftheresults.Furthermore,asimplementedinpopularpractice(see,for example,[23])everyfew( 25 )HIOiterationswerefollowedbyasmallnumberof( 5 )ER iterations,withthemaximumnumberofHIO+ERiterationslimitedto 600 thischoice ofiterationcountensuresconvergenceofthealgorithm(seeFigure2.2.1)whilecomparing favorablywiththecomputationalcost(seeFigure2.2.5)oftheproposedmethod. Figure2.2.1:SelectionofHIO+ERiterationparameters.(HIO,ER) =( x;y ) indicatesthat everysetof x iterationsoftheHIOalgorithmwasfollowedbyasetof y iterationsoftheER algorithm. 52 2.2.1EmpiricalValidationofTheorem2.1.1(Algorithm1) RecallfromAlgorithm1thatthismeasurementconstructioninvolvestheuseofband-limited masks.Numericalexperimentswereperformedwiththefollowingthreetypesofmasks: b m k = 8 > > > < > > > : a N e 2 ˇ U ; if k 2 [ ] 0 ; 0 ; otherwise ; a N ˘N (0 ; 1) ; U ˘U (0 ; 1) ; (randommask)(2.2.1) where N (0 ; 1) and U (0 ; 1) denotei.i.d.standardGaussiananduniform(intheinterval [0 ; 1] ) randomdistributionsrespectively; b m k = 8 > > > < > > > : e k=a 4 p 2 1 ; if k 2 [ ] 0 ; 0 ; otherwise ; a =max(4 ; ( 1) = 2) ; (exponentialmask)(2.2.2) and b m k = 8 > > > < > > > : 1+ k 1 ( 1) ; if k 2 [ ] 0 ; 0 ; otherwise : (linearmask)(2.2.3) Theexponentialmaskin(2.2.2)isrelatedtothedeterministicmasks˝rstintroducedand constructedin[36].Thecorrespondingvaluesofthemask-dependentconstant (seeLemma 2.1.4)forthesethreemaskswere 3 : 085 10 1 , 6 : 149 10 2 ,and 2 : 585 10 1 respectively. Thequalitativeandquantitativeperformanceofallthreemasksweresimilar. Webeginbyexaminingtheimprovementinaccuracyo˙eredbyaddinganinexpensive post-processingsteptoAlgorithm1.Morespeci˝cally,therecoveredsolution x e ispost- processedusing 60 iterationsoftheHIO+ERalgorithm(intwoblocks;eachblockconsisting of 25 iterationsofHIOfollowedby 5 iterationsofER).Inaddition,aneigenvector-based 53 magnitudeestimationproceduredescribedinof[36]maybeutilizedinplaceofthe diagonalelementbasedestimatesinStep5ofAlgorithm1.Numericalresultsshowingthe utilityoftheseproceduresisshowninFigure2.2.2,whichplotsthereconstructionerrorin recoveringatestsignal( d =255 )using 15 shiftsandarandommaskband-limitedto =8 at severalnoiselevels.The˝gureshowsthatthecombinationofthesetwoproceduresimproves reconstructionaccuracy(atanegligibleincreaseincomputationalcost),andwilltherefore beutilizedinthenumericalresultswhichfollow. 1 Figure2.2.2:ReconstructionaccuracywithandwithoutHIO+ER( 60 iterations)post- processing,improvedmagnitudeestimation. Next,weexaminetheimportanceofthenumberofshifts L inrelationtoreconstruction accuracy.Weexpectthatreconstructionsusinglarger L (whichentailsusingmoremea- surements,eachcorrespondingtogreateroverlapbetweensuccessivemaskedregionsofthe specimen)wouldo˙erimprovedaccuracy.Thisisindeedcon˝rmedbyFigure2.2.3where 1 Whereappropriate,resultsusingnopost-processingwillalsobeincluded. 54 thereconstructionaccuracy(atvariousnoiselevels)forseveraldi˙erentvaluesof L isplot- ted.Wenotethateachvalueof L correspondstoaslightlydi˙erentvalueof d toensure L divides d .Inthiscase, =16 waschosen,alongwithrandommasksandthepost-processing proceduredescribedearlier.Asexpected,reconstructionaccuracyimprovesforlarger L , withabouta 10 dBperformancespread.Asuitablevalueof L canbechosendependingon whethertheproposedmethodisusedasareconstructionprocedure,orasaninitializerfor anotheralgorithm. Figure2.2.3:Reconstructionaccuracyvs.numberofshifts L . InFigure2.2.4,wecomparetheperformanceoftheproposedmethodtootherpopular phaseretrievalmethods.Reconstructionerrorsforrecoveringa d =60 -lengthsignalusing arandommaskwith =8 and L =15 shiftsareplottedfordi˙erentlevelsofaddednoise. 55 Weseethattheproposedmethod(bothwithandwithoutpost-processing)compareswell withthepopular HIO+ER algorithm.Thenoiseperformanceisalsoalmostasgoodasthe signi˝cantlymoreexpensiveSDP-based PhaseLift algorithm.WenotethattheWirtinger Flowmethodissensitivetothechoiceofparametersanditerationcounts.Weusefewertotal iterations( 50 at 10 dBnoise)athighernoiselevelsandmoreiterations( 6500 at 60 dB)as thenoiseleveldecreasestoensureconvergenceofthealgorithmtothelevelofnoise.Weare notawareofanymethodicalprocedureforsettingthevariousalgorithmicparameterswhen utilizingthe(local)measurementconstructionsconsideredinthispaper.Wealsonotethat noneofthecompetingmethodsshownintheplothaverecoveryguaranteesforthisclassof (local,spectrogram-type)measurements. Finally,Figure2.2.5plotsthecorrespondingexecutiontimeforthecompetingalgorithms asafunctionoftheproblemsize d .Inthiscase,randommaskswerechosenwith = d 1 : 25log 2 d e alongwith L = + d = 2 e 1 shifts.The˝gurecon˝rmstheessentiallye computationalcostofAlgorithm1;furthermore,italsocon˝rmsthatthepost-processing procedureintroducedinFigure2.2.2doesnotincreasethecomputationalcostdrastically. Morespeci˝cally,theproposedmethodprovidesbcomputationale˚ciency,is aboutafactorof 2 5 fasterthanthe HIO+ER and WirtingerFlow methods,andseveral ordersfasterthantheSDP PhaseLift . 56 Figure2.2.4:Reconstructionaccuracyvs.addednoise. Figure2.2.5:Executiontimevs.signalsize d . 57 2.2.2EmpiricalValidationofLemma2.1.5 WenextprovidenumericalresultsvalidatingLemma2.1.5.Recallthatthismeasurement constructionrequiresthatsupp ( m )=[ ˆ ] 0 ;i.e.,supportrestrictionsareimposedinthe physical(space)domain.AswithSection2.2.1,experimentswereconductedwithvarious masksallyieldingcomparablequalitativeandquantitativeresults.The˝guresbelowuse theexponentialmaskconstruction˝rstintroducedin[36] m k = 8 > > > < > > > : e k=a 4 p 2 ˆ 1 ; if k 2 [ ˆ ] 0 ; 0 ; otherwise ; a =max(4 ; ( ˆ 1) = 2) ; (2.2.4) therebyallowingustodirectlycomparetheperformanceoftheproposedmethodwiththe algorithmintroducedin[36].WebeginwithFigure2.2.6whichplotsthereconstruction errorinrecoveringatestsignal( d =257 )usingthemasksin(2.2.4)with ˆ =10 and K =19 (yieldingatotalof 19 d measurements).Resultswithandwithoutthepost-processing proceduredetailedinSection2.2.1areprovided,alongwithresultsfrom[36]withandwithout thesamepost-processingprocedure. 58 Figure2.2.6:ReconstructionaccuracywithandwithoutHIO+ER( 60 iterations)post- processing,improvedmagnitudeestimation,andcomparisonwithresultsfrom[36]. Ascanbeseeninthe˝gure,thepost-processingprocedureyieldsasmallimprovement ofabout 5 dBinthereconstructionerror,especiallyatlownoiselevels.Wealsoobservethat theproposedmethodcompareswellwiththosefrom[36].Althoughtheresultsfrom[36]are comparable,theyareless˛exible;forexample,theydonotallowforphysicaldomainshifts ( L )greaterthan 1 aswaspossibleinSection2.2.1. Next,weinvestigatethereconstructionaccuracyasafunctionof K ,thenumberofFourier modes.Figure2.2.7plotsreconstructionerrorinrecoveringatestsignalfor K =13 ; 15 ; 17 and 19 respectively.Thetestsignalsize(approximately d =256 )variesslightlyineachcase tosatisfythedivisibilityconditions( d divides K )whilethesupportoftheexponentialmask, ˆ ,waschosentobe 10 .Asexpected,theplotshowsthatreconstructionaccuracyimproves overawiderangeofaddednoiselevelswhen K increases;i.e.,whenmoremeasurementsare acquired. 59 Figure2.2.7:Reconstructionaccuracyvs.numberofFouriermodes K . Forcompleteness,weincludenoiserobustness(Figure2.2.8)andexecutiontime(Figure 2.2.9)plotscomparingtheperformanceoftheproposedmethodtothe HIO+ER , PhaseLift , and WirtingerFlow algorithms.FromFigure2.2.8,weseethattheproposedmethod(both withandwithoutpost-processing)compareswellwiththe HIO+ER implementationacrossa widerangeofSNRs.Wealsosee,aswithFigure2.2.9inSection2.2.1,theessentially timecomputationalcostofthemethodaswellasthebest-in-classcomputationale˚ciency whencomparedtoothercompetingalgorithms. 60 Figure2.2.8:Reconstructionaccuracyvs.addednoise. Figure2.2.9:Executiontimeversussignalsize d . 61 2.2.3EmpiricalValidationofTheorem2.1.2(Algorithm2) WeprovidepreliminarynumericalresultsvalidatingAlgorithm2,withcomparisonstothe HIO+ER algorithm.Considerthesignalparameters: d =190 ;ˆ =48 ; =10 ;K =2 ˆ 1 ;L =2 1 ;D = KL .Algorithm2hasanexecutiontimeof 0 : 033 seconds.Whenadding thepost-processingmethodfromSection2.2.1,theexecutiontimeincreasesto 0 : 589 seconds. Bothofthesemethodsareconsiderablyfasterthan HIO+ER ,whichreconstructssignalsin 2 : 635 seconds.NotethatinStep3ofAlgorithm2,weutilizetheTikhonovregularization A =( W W + ˙ 2 I ) 1 W V ,where ˙ 2 ischosenusingtheL-curvemethod. Finally,inFigure2.2.10wecompareAlgorithm2to HIO+ER .Whenpost-processedwith 60iterationsof HIO+ER ,Algorithm2compareswellwiththe HIO+ER implementation(600 iterations)acrossawiderangeofSNRs,whilebeingsigni˝cantlyfasterinreconstruction. Figure2.2.10:Reconstructionaccuracyvs.addednoise. 62 Chapter3 LowerLipschitzBoundsforPhase RetrievalfromLocallySupported Measurements Theworkinthischapter˝rstappearedin[35]. AsdemonstratedinChapter2,noiserobustnessguaranteesaredesirableforanyreliable phaseretrievalalgorithm.Muchoftheworkinthis˝eldisdedicatedtothedesignof algorithmsthataresimultaneouslye˚cientandrobust.Asinmanyotherareasofharmonic analysis,anaturalquestionarises:whatistheworst-casenoiserobustnessofanyphase retrievalalgorithm?Asitstandsthisquestionsistoogeneral,asalgorithmsvarywidely basedonthemeasurementmodelandtheassumptionsonthespecimenofinterest.Inthis chapter,wenarrowdownthequestionabovetothefollowingsetting:whatistheworst-case noiserobustnessofanyphaseretrievalalgorithmwhichaimstoreconstructallnonvanishing vectors x 2 C d (uptoasingleglobalphasemultiple)fromthemagnitudesofanarbitrary collectionoflocalcorrelationmeasurements? Examplesofsuchmeasurementsincludebothspectrogrammeasurementsof x usinglo- callysupportedwindowsandmaskedFouriertransformintensitymeasurementsof x using band-limitedmasks.Asaresult,therobustnessresultsconsideredhereinapplytoawide 63 rangeofbothptychographicandFourierptychographicimagingscenarios.Inparticular,the mainresultsimplythattheaccuraterecoveryofhigh-resolutionimagesofextremelylarge samplesusinghighlylocalizedprobesislikelytorequireanextremelylargenumberofmea- surementsinordertoberobusttoworst-casemeasurementnoise,independentoftherecovery algorithmemployed.Asaresult,recentpushestoachievehigh-speedandhigh-resolution ptychographicimagingofintegratedcircuitsforprocessveri˝cationandfailureanalysiswill likelyneedtocarefullybalanceprobedesign(e.g.,theire˙ectivetime-frequencysupport) againstthetotalnumberofmeasurementsacquiredinorderfortheirimagingtechniquesto bestabletomeasurementnoise,nomatterwhatreconstructionalgorithmsareapplied. 3.1IntroductionandStatementofResults Weconsidertherobustnessofthe ˝nite-dimensionalphaseretrievalproblem inwhichone attemptstorecoverasignal x :=( x 1 ;:::;x d ) T 2 C d fromoneoftwononlinearmeasurement maps ; : C d ! R N givenby ( x )= fjh x ; f k ijg N k =1 and ( x )= fjh x ; f k ij 2 g N k =1 ; wherethevectors f f 1 ;:::; f N gˆ C d formaframe(i.e.,aspanningset)of C d .Wewillfocus onaspecialclassofframevectors f k whichhave localizedsupport (i.e.,allofwhosenonzero entriesarecontainedinanintervaloflengthatmost ˝ d ).Suchframesarecommonly encounteredinapplicationslikeptychographicimaging. Since,aspreviouslystated,phaseretrievalisonlypossibleuptoaglobalphase,consider theequivalencerelation x ˘ x 0 ; if x = e x 0 forsome 2 R : FollowingtheworkofBalanet 64 al.[3,5],wewillconsidertwocommonlyusedmetricson C d = ˘ : thenaturalmetric D 2 ( x ; x 0 ):=min 2 R k x e x 0 k 2 ; andthematrix-norminducedmetric d 1 ( x ; x 0 ):= k xx x 0 x k 1 := X k ˙ k ( xx x 0 x ) ; where ˙ k ( xx x 0 x ) isthe k -thsingularvalueofthe(atmostrank-two)matrix xx x 0 x . In[5],Balanetal.showedthatif and areinjectiveon C d = ˘ ; then isbi-Lipschitzwith respectto d 1 ; and isbi-Lipschitzwithrespectto D 2 ; whereinbothcases R N isequipped withtheEuclideannorm. Motivatedbyapplicationssuchas(Fourier)ptychography[52,60]andrelatednumerical methods[37,36],wewillstudyframeswhichareconstructedastheshiftsofafamilyof locallysupportedmeasurementvectors.Speci˝cally,weassumethat f m 1 ; m 2 ;:::; m K g is afamilyofmeasurementmasksin C d suchthatforall 1 k K thenonzeroentriesof m k arecontainedintheset [ ]:= f 1 ;:::; g forsome d 4 (althoughallofourresultsremain validifthesupportofourmasksarecontainedinanyintervaloflength ).Letting L bean integerwhichdivides d ,suchthat a := d L <; weconsidernonlinearphaselessmeasurement maps Y;Z : C d ! R K L de˝nedbytheircoordinatefunctions Y k;` ( x ):= jh S `a m k ; x ij 2 (3.1.1) and Z k;` ( x ):= jh S `a m k ; x ij (3.1.2) 65 for 1 k K and 1 ` L .Here S ` isthecircularshiftoperatoron C d de˝nedforall ` 2 Z by ( S ` x ) n := x ( n + ` 1)mod d +1 : (The +1 isneededbecauseweareindexingourvectorsfromone.)Fornotationalconvenience, wewillassumethat d iseven,althoughourresultsremainvalid,withsimilarproofs,when d isodd. ThepurposeofthisworkistoprovidelowerboundsontheLipschitzconstantsofany maps, A and B; whichreconstruct x from Y and Z ,respectively.Withsuchlowerbounds inhand,onewouldbebetterequippedto,e.g.,judgetheoptimalityoftheoreticalnoisy reconstructionguaranteesforphaseretrievalalgorithmswhichutilizelocallysupportedmea- surements(see,e.g.,[37,36]).Unfortunately, Y and Z arenotinjectiveonallof C d = ˘ .For example,iftwovectors x 2 C d arede˝nedby x n := 8 > > > > > > > > > > > > < > > > > > > > > > > > > : 1 ; 1 n d 2 0 ; d 2 > > > > > > > > > > > < > > > > > > > > > > > > : q; 1 n d 2 ; p; d 2 > > < > > > : e n=b (2 1) 1 = 4 e 2 ˇi ( k 1)( n 1) = (2 1) ; if 1 n ; 0 ; if 4 : Masksofthisformarecloselyrelatedtothoseusedinpty- chographicimaging(see,forexample,[37],Section1.3andthereferencesprovidedtherein). In[37]itwasshownthat,withthischoiceofmasks,themap Y; restrictedtothesubsetof C d where x n 6 =0 forall 1 n d; canbeinvertedbyanalgorithmwhichisbothe˚cient 77 andnumericallystableinthecasewhere L = d: Corollary3.3.1. Let 0

> > < > > > : b f i 2 n 1 2 b f j 2 n 1 2 ; if j i j j 2 ; 0 ; otherwise, where n = N 1 4 .Notethat H iscomposedofoverlappingsegmentsoftherank-onematrices y ! y ! for ! 2 n;:::;n g .Thus,ourmeasurementscanbewrittenas b ˇ diag ( GHG ) ; (4.2.1) where b isde˝nedin(4.1.2).Byconsistentlyvectorizing(4.2.1),wecanobtainasimple linearsystemwhichcanbeinvertedtolearn h ,avectorizedversionof H .Inparticular,we have b ˇ M h ; (4.2.2) wherethematrix M 2 C NK N 2 canbecomputedby,e.g.,passingthecanonicalbasis elementsfor C N N through(4.2.1).Wesolvethelinearsystem(4.2.2)asaleastsquares problem;experimentshaveshownthat M isofrank NK .Theprocessofrecoveringthe 96 Fouriercoe˚cientsof f from h isknownasangularsynchronization,andisdescribedin detailin[36]. 4.3NumericalResults 1 0 : 8 0 : 6 0 : 4 0 : 2 0 0 : 2 0 : 4 0 : 6 0 : 8 1 0 0 : 5 1 1 : 5 2 2 : 5 3 3 : 5 x y Figure4.3.1:ModulatedGaussiansignaland11shiftsofaGaussianwindow. 1 0 : 8 0 : 6 0 : 4 0 : 2 0 0 : 2 0 : 4 0 : 6 0 : 8 1 0 : 2 0 0 : 2 0 : 4 0 : 6 0 : 8 1 1 : 2 x f ( x ) True Approx. Figure4.3.2:TrueGaussiansignalanditsreconstruction. 97 1 0 : 8 0 : 6 0 : 4 0 : 2 0 0 : 2 0 : 4 0 : 6 0 : 8 1 0 : 5 0 0 : 5 1 1 : 5 2 2 : 5 3 3 : 5 x f ( x ) True Approx. Figure4.3.3:TruemodulatedGaussiansignalanditsreconstruction. 1 0 : 8 0 : 6 0 : 4 0 : 2 0 0 : 2 0 : 4 0 : 6 0 : 8 1 0 : 2 0 0 : 2 0 : 4 0 : 6 0 : 8 1 x f ( x ) True Approx. Figure4.3.4:Characteristicfunctionanditsreconstruction. 1 0 : 8 0 : 6 0 : 4 0 : 2 0 0 : 2 0 : 4 0 : 6 0 : 8 1 0 : 2 0 0 : 2 0 : 4 0 : 6 0 : 8 1 x f ( x ) True Approx. Figure4.3.5:Piecewisecontinuousfunctionanditsreconstruction. 98 Wetestthephaseretrievalalgorithmaboveforfourdi˙erentchoicesofsignal f .The˝rst isaGaussiansignal f ( x )=2 1 4 e 25 4 x 3 2 ˜ [ 1 ; 1] ( x ) : ThesecondisanoscillatoryGaussian f ( x )=2 1 4 e 8 ˇx 2 cos(24 x ) ˜ [ 1 ; 1] ( x ) : Thethirdisacharacteristicfunction f ( x )= ˜ h 1 5 ; 1 5 i ( x ) : Thefourthisapiecewisecontinuousfunction f ( x )= 1 2 ˜ h 3 10 ; 0 i ( x )+ 1 10 3 x ˜ h 0 ; 3 10 i ( x ) : Inthe˝rsttwoexperiments,thewindowusedistheGaussian g ( x )= c e 16 ˇx 2 ˜ h 1 2 ; 1 2 i ( x ) where c isaconstantchosensothat k g k L 2 =1 .Weuseatotalof11shiftsof g .Since g is supportedon h 1 2 ; 1 2 i ,anytwoconsecutiveshiftsareseparatedby 0 : 5 11 (seeFigure4.3.1).We choose61valuesof ! from [ 15 ; 15] sampledinhalf-steps,andset =7 .Thereconstructions inphysicalspaceareshownatselectedgridpointsinFigures4.3.2and4.3.3.Therelative ` 2 errorinphysicalspaceis 1 : 47 10 3 forthe˝rstexperimentand 1 : 872 10 2 forthe second. 99 Inthethirdandfourthexperiments(inwhichthesignalsarediscontinuous),thewindow usedisthe(thinner)Gaussian g ( x )= c e 32 ˇx 2 ˜ h 1 2 ; 1 2 i ( x ) : Fortherecoveyrofthecharacteristicfunction,weuseatotalof21shiftsof g ,andchoose 293valuesof ! from [ 73 ; 73] sampledinhalf-steps,andset =10 .Thereconstructionin physicalspaceforthethirdexperimentisshowninFigure4.3.4.Therelative ` 2 errorin physicalspaceis 1 : 509 10 1 . Fortherecoveryofthepiecewisecontinuousfunction,weuseatotalof41shiftsof g , andchoose121valuesof ! from [ 30 ; 30] sampledinhalf-steps,andset =10 .The reconstructioninphysicalspaceforthefourthexperimentisshowninFigure4.3.5.The relative ` 2 errorinphysicalspaceis 1 : 343 10 1 . 4.4FutureWork Whilethispaperaddressesthe1Dproblem,theextensionofthismethodtothe2Dsetting isanappealingavenueforfutureresearch.Indeed,preliminaryresultsindicatethatthe underlyingdiscretemethodthatformsthebasisforthispaperextendstotwodimensions withouttoomuchdi˚culty. Furthermore,empiricalresultssuggestthatthemethodproposedheredemonstratesro- bustnesstonoise,althoughwedeferadetailedanalysis(andderivationofanassociated robustrecoveryguarantee)tofuturework. 100 APPENDIX 101 ProofofLemma1.3.1 Proof. Let x 2 C d 1 and `;! 2 [ d ] 0 bearbitrary.Wehave ( F d b x ) ! = d 1 X k =0 b x k e 2 ˇik! d = d 1 X k =0 d 1 X n =0 x n e 2 ˇink d e 2 ˇik! d = d 1 X k =0 d 1 X n =0 x n e 2 ˇik ( n ! ) d = dx ! =( d e x ) ! ; ( F d ( W ` x )) ! = d 1 X k =0 x k e 2 ˇik` d e 2 ˇik! d = d 1 X k =0 x k e 2 ˇik ( ! ` ) d = b x ! ` =( S ` b x ) ! ; ( F d ( S ` x )) ! = d 1 X k =0 x k + ` e 2 ˇik! d = d 1 X k =0 x k + ` e 2 ˇi ( k + ` ) ! d e 2 ˇi ( ` ) ! d = e 2 ˇi`! d b x ! =( W ` b x ) ! ; W ` F d S ` e x ! = e 2 ˇi`! d W ` b e x ! = b e x ! = d 1 X k =0 e x k e 2 ˇik! d = d 1 X k =0 e x k e 2 ˇik! d = d 1 X k =0 x k e 2 ˇik! d = b x ! ; g S ` x ! = ^ ( S ` x ) ! = ( S ` x ) ! = x ` ! = e x ! ` = S ` e x ! ; ( F d x ) ! = d 1 X k =0 x k e 2 ˇik! d = d 1 X k =0 x k e 2 ˇik! d = d 1 X k =0 x k e 2 ˇik! d = ( F d e x ) ! ; e b x ! =( b x ) ! = d 1 X n =0 x n e 2 ˇin! d = d 1 X n =0 x n e 2 ˇin! d =( F d e x ) ! : 102 ProofofLemma2.0.1 Proof. Let d 2 N andsuppose s 2 N divides d .Thenforany u 2 C d 1 and ! 2 h d s i 0 , F d s ( Z s u ) ! = d s 1 X n =0 ( Z s u ) n e 2 ˇin! d=s = d s 1 X n =0 u ns e 2 ˇin! d=s = 1 d d s 1 X n =0 0 @ d 1 X r =0 b u r e 2 ˇirns d 1 A e 2 ˇi!ns d = 1 d d 1 X r =0 b u r d s 1 X n =0 e 2 ˇin ( r ! ) d=s = 1 s s 1 X r =0 b u ! + r d s = 1 s s 1 X r =0 b u ! r d s : ProofofLemma2.0.2 Proof. Let x 2 C d 1 and ;! 2 [ d ] 0 bearbitrary.Observethat ( F d ( x S ! x )) = 1 d ( b x d F d ( S ! x )) (byLemma1.3.2) = 1 d b x d W ! b x (byLemma1.3.1(3)) = 1 d d 1 X n =0 b x n W ! b x n (byde˝nitionof d ) = 1 d d 1 X n =0 b x n b x n e 2 ˇi! ( n ) d (byde˝nitionof W ! ) 103 = 1 d e 2 ˇi! d d 1 X n =0 b x n e b x n e 2 ˇi!n d (byde˝nitionof e ) = 1 d e 2 ˇi! d d 1 X n =0 b x n b x n e 2 ˇi!n d (byLemma1.3.1(6,7)) = 1 d e 2 ˇi! d F d b x S b x ! : 104 REFERENCES 105 REFERENCES [1] R.Alaifari,I.Daubechies,P.Grohs,andR.Yin.StablePhaseRetrievalinIn˝nite Dimensions. FoundationsofComputationalMathematics ,2018. [2] CélineAubelandHelmutBölcskei.Vandermondematriceswithnodesintheunitdisk andthelargesieve. AppliedandComputationalHarmonicAnalysis ,2017. [3] RaduBalan.Framesandphaselessreconstruction. FiniteFrameTheory:AComplete IntroductiontoOvercompleteness ,93:175,2016. [4] RaduBalan,PeteCasazza,andDanEdidin.Onsignalreconstructionwithoutphase. AppliedandComputationalHarmonicAnalysis ,2006. [5] RaduBalanandDongmianZou.OnLipschitzanalysisandLipschitzsynthesisforthe phaseretrievalproblem. LinearAlgebraanditsApplications ,496(SupplementC):152 181,2016. [6] AfonsoSBandeira,YutongChen,andDustinGMixon.Phaseretrievalfrompower spectraofmaskedsignals. InformationandInference:aJournaloftheIMA , 102,2014. [7] HeinzHBauschke,PatrickLCombettes,andDRussellLuke.Phaseretrieval,error reductionalgorithm,andFienupvariants:Aviewfromconvexoptimization. Journalof theOpticalSocietyofAmerica.A,Optics,Imagescience,andVision , 2002. [8] StephenBecker,EmmanuelJ.Candès,andMichaelGrant.Templatesforconvexcone problemswithapplicationstosparsesignalrecovery. MathematicalProgrammingCom- putation ,Aug.2011. [9] StephenBecker,EmmanuelJ.Candès,andMichaelGrant.TFOCS:Templatesfor ˝rst-orderconicsolvers,version1.3.1. http://cvxr.com/tfocs ,Sep.2014. [10] TamirBendory,YoninaCEldar,andNicolasBoumal.Non-convexphaseretrievalfrom STFTmeasurements. IEEETransactionsonInformationTheory ,2018. [11] OliverBunk,AnaDiaz,FranzPfei˙er,ChristianDavid,BerndSchmitt,DillipKSatap- athy,andJohannesVanderVeen.Di˙ractiveimagingforperiodicsamples:Retrieving one-dimensionalconcentrationpro˝lesacrossmicro˛uidicchannels. Actacrystallograph- ica.SectionA,Foundationsofcrystallography ,082007. 106 [12] JamesonCahill,PeterCasazza,andIngridDaubechies.Phaseretrievalinin˝nite- dimensionalHilbertspaces. Trans.Amer.Math.Soc.,Ser.B ,2016. [13] E.J.Candès,X.Li,andM.Soltanolkotabi.PhaseretrievalviaWirtingerFlow:Theory andalgorithms. IEEETransactionsonInformationTheory ,April 2015. [14] EmmanuelJCandès,YoninaCEldar,ThomasStrohmer,andVladislavVoroninski. Phaseretrievalviamatrixcompletion. SIAMreview ,2015. [15] EmmanuelJCandès,XiaodongLi,andMahdiSoltanolkotabi.Phaseretrievalfrom codeddi˙ractionpatterns. AppliedandComputationalHarmonicAnalysis , 299,Sept.2015. [16] EmmanuelJCandès,ThomasStrohmer,andVladislavVoroninski.Phaselift:Exact andstablesignalrecoveryfrommagnitudemeasurementsviaconvexprogramming. Commun.Pur.Appl.Math. ,2013. [17] HenryN.Chapman.Phaseretrievalx-raymicroscopybyWigner-distributiondeconvo- lution. Ultramicroscopy ,1996. [18] JVCorbett.ThePauliproblem,statereconstructionandquantum-realnumbers. Re- portsonMathematicalPhysics ,2006. [19] MartinDierolf,AndreasMenzel,PierreThibault,PhilippSchneider,CameronM. Kewish,RogerWepf,OliverBunk,andFranzPfei˙er.Ptychographicx-raycomputed tomographyatthenanoscale. Nature ,Sep2010. [20] YoninaCEldar,PavelSidorenko,DustinGMixon,ShabyBarel,andOrenCohen. Sparsephaseretrievalfromshort-timeFouriermeasurements. IEEESignalProcess. Lett. ,2015. [21] CFienupandJDainty.Phaseretrievalandimagereconstructionforastronomy. Image Recovery:TheoryandApplication ,pages1987. [22] J.R.Fienup.ReconstructionofanobjectfromthemodulusofitsFouriertransform. Opt.Lett. ,Jul1978. [23] J.R.Fienup.Phaseretrievalalgorithms:acomparison. Appl.Opt. , Aug1982. [24] R.W.GerchbergandASaxtonW.O.Apracticalalgorithmforthedeterminationof phasefromimageanddi˙ractionplanepictures. Optik ,,111971. 107 [25] MichaelGrantandStephenBoyd.Graphimplementationsfornonsmoothconvexpro- grams.InV.Blondel,S.Boyd,andH.Kimura,editors, RecentAdvancesinLearningand Control ,LectureNotesinControlandInformationSciences,pages0.Springer VerlagLimited,2008. http://stanford.edu/~boyd/graph_dcp.html . [26] MichaelGrantandStephenBoyd.CVX:Matlabsoftwarefordisciplinedconvexpro- gramming,version2.1. http://cvxr.com/cvx ,March2014. [27] P.GrohsandM.Rathmair.StableGaborPhaseRetrievalandSpectralClustering. CommunicationsonPureandAppliedMathematics ,2018. [28] DavidGross,FelixKrahmer,andRichardKueng.Improvedrecoveryguaranteesfor phaseretrievalfromcodeddi˙ractionpatterns. AppliedandComputationalHarmonic Analysis ,2017. [29] RobertW.Harrison.Phaseproblemincrystallography. J.Opt.Soc.Am.A ,10(5):104 1055,May1993. [30] R.HegerlandW.Hoppe.Dynamischetheoriederkristallstrukturanalysedurchelektro- nenbeugungiminhomogenenprimärstrahlwellenfeld. BerichtederBunsengesellschaft furphysikalischeChemie ,54,1970. [31] W.Hoppe.Beugungiminhomogenenprimärstrahlwellenfeld.i.prinzipeinerphasenmes- sungvonelektronenbeungungsinterferenzen. ActaCrystallographicaSectionA , 501,jul1969. [32] A.M.J.Huiser,A.J.J.Drenth,andH.A.Ferwerda.Onphaseretrievalinelectronmi- croscopyfromimageanddi˙ractionpattern. Optik(Jena) ,071976. [33] IARPA.RapidAnalysisofVariousEmergingNanoelectronics(RAVEN). https:// www.iarpa.gov/index.php/research-programs/raven/raven-baa ,Jan.2016. [34] MarkIwen,YangWang,andAdityaViswanathan.BlockPR:Matlabsoftwareforphase retrievalusingblockcirculantmeasurementconstructionsandangularsynchronization, version2.0. https://bitbucket.org/charms/blockpr ,April2016. [35] MarkA.Iwen,SamiMerhi,andMichaelPerlmutter.LowerLipschitzboundsforphase retrievalfromlocallysupportedmeasurements. AppliedandComputationalHarmonic Analysis ,2019. [36] MarkA.Iwen,BrianPreskitt,RayanSaab,andAdityaViswanathan.Phaseretrieval fromlocalmeasurements:Improvedrobustnessviaeigenvector-basedangularsynchro- nization. AppliedandComputationalHarmonicAnalysis ,2018. 108 [37] MarkA.Iwen,AdityaViswanathan,andYangWang.Fastphaseretrievalfromlocal correlationmeasurements. SIAMJournalonImagingSciences ,2016. [38] KishoreJaganathan,YoninaCEldar,andBabakHassibi.STFTphaseretrieval: Uniquenessguaranteesandrecoveryalgorithms. IEEEJ.Sel.TopicsSignalProcess. , 2016. [39] StevenGJohnson.Saddle-pointintegrationof C 1 functions.2015.preprint, arXiv:1508.04376. [40] ShuyangLingandThomasStrohmer.Self-calibrationandbiconvexcompressivesensing. InverseProblems ,31(11):115002,sep2015. [41] AndrewM.MaidenandJohnM.Rodenburg.Animprovedptychographicalphase retrievalalgorithmfordi˙ractiveimaging. Ultramicroscopy ,2,2009. [42] StephaneMallat. AWaveletTourofSignalProcessing,TheSparseWay .Academic Press,3rd.edition,2008. [43] StefanoMarchesini,Yu-ChaoTu,andHau-tiengWu.Alternatingprojection,ptycho- graphicimagingandphasesynchronization. Appl.Comput.Harmon.Anal. , 851,2016. [44] SamiMerhi,AdityaViswanathan,andMarkIwen.Recoveryofcompactlysupported functionsfromspectrogrammeasurementsvialifting.In 2017InternationalConference onSamplingTheoryandApplications(SampTA)(SampTA2017) ,Tallinn,Estonia,July 2017. [45] R.P.Millane.Phaseretrievalincrystallographyandoptics. J.Opt.Soc.Am.A , Mar1990. [46] SNawab,TQuatieri,andJaeLim.Signalreconstructionfromshort-timeFourier transformmagnitude. IEEETrans.Acoust.,Speech,SignalProcess. , 1983. [47] GoetzEPfanderandPalinaSalanevich.Robustphaseretrievalalgorithmfortime- frequencystructuredmeasurements.2016.preprint,arXiv:1611.02540. [48] BrianPreskitt. PhaseRetrievalfromLocallySupportedMeasurements .PhDthesis,UC SanDiego,2018. [49] J.RodenburgandR.Bates.Thetheoryofsuper-resolutionelectronmicroscopyvia Wigner-distributiondeconvolution. PhilosophicalTransactionsoftheRoyalSocietyof London.SeriesA:PhysicalandEngineeringSciences ,339(1655),Jun1992. 109 [50] J.Rodenburg,B.Mccallum,andP.Nellist.Experimentaltestsondouble-resolution coherentimagingviastem. Ultramicroscopy ,1993. [51] J.M.RodenburgandH.M.L.Faulkner.Aphaseretrievalalgorithmforshifting illumination. AppliedPhysicsLetters ,2004. [52] JMRodenburg.Ptychographyandrelateddi˙ractiveimagingmethods. Advancesin ImagingandElectronPhysics ,4,2008. [53] PalinaSalanevichandGötzEPfander.Polarizationbasedphaseretrievalfortime- frequencystructuredmeasurements.In Proc.2015Int.Conf.SamplingTheoryand Applications(SampTA) ,pages2015. [54] E.Stade. FourierAnalysis .PureandAppliedMathematics:AWileySeriesofTexts, MonographsandTracts.Wiley,2011. [55] ThomasStrohmerandJaredTanner.ImplementationsofShannon'ssamplingtheorem, atime-frequencyapproach. SamplingTheorySignalImageProcess. ,2005. [56] NicolasSturmelandLaurentDaudet.SignalreconstructionfromSTFTmagnitude:A stateoftheart.In Int.Conf.DigitalAudioE˙ects(DAFx) ,pages2011. [57] GauravThakur.Reconstructionofbandlimitedfunctionsfromunsignedsamples. J. FourierAnal.Appl. ,2011. [58] I.Waldspurger.PhaseretrievalwithrandomGaussiansensingvectorsbyalternating projections. IEEETransactionsonInformationTheory ,May2018. [59] AdriaanWalther.Thequestionofphaseretrievalinoptics. JournalofModernOptics , 1963. [60] GuoanZheng,RoarkeHorstmeyer,andChanghueiYang.Wide-˝eld,high-resolution Fourierptychographicmicroscopy. Naturephotonics ,7(9):739,2013. 110