Phase retrieval algorithms a personal tour_2012

JamesR.Fienup

TheInstituteofOptics,UniversityofRochester,Rochester,NewYork14627,USA

(fienup@optics.rochester.edu)

Received28September2012;accepted15October2012;

posted4December2012(Doc.ID181961);published21December2012

Thispapergivesthereaderapersonaltourthroughthefieldofphaseretrievalandrelatedworksthatleaduptoorcitedthepaper“PhaseRetrievalAlgorithms:aComparison,”[Appl.Opt.21,2758(1982)].©2012OpticalSocietyofAmerica

OCIScodes:100.5070,100.3010,010.7350,110.0110,030.0030,070.0070.

1.Introduction2.HowItCametoBe

A.ComputerHolography,Kinoforms,andIterativeAlgorithmsatStanford

ThisisnotyourusualpaperforAppliedOptics,beingneitherjustthelatestresultsin,noracomprehen-sivereviewof,aparticularfield.SolicitedbyEditor-in-ChiefJosephMait,itisinpartaretrospec-tivepaperaboutapersonaljourneyinthefieldofphaseretrieval,inthecontextofthe50thanniver-sarycelebrationofAppliedOptics.Hesolicitedthepresentpaperbecausethepaper“PhaseRetrievalAlgorithms:aComparison”(henceforth:“the1982AppliedOpticspaper”)[1]had,asofearly2012,re-ceivedover1,350citations(ThompsonReuters’WebofScience),makingitthefourthmostcitedpaperinAppliedOptics.Itsannualrateofcitationacceleratedinthelastdecade(toover100peryear)ratherthantheusualdecelerationofcitationsthatoccursforapaperofitsvintage.Section2ofthepresentpaperdescribesthehistoricaleventsthatleaduptothe1982AppliedOpticspaper,brieflysummarizesthecontentsofthatpaper,andspeculatesonthereasonsforitshighcitationrate.Section3describessomeofthemanyfieldswithinopticsandotherdisciplinesofthepapersthatcitedthe1982AppliedOpticspaper.Section4mentionssomeofthesignificantenhance-mentstothephaseretrievalalgorithm,includingthefirstexpositionofthe“continuous”versionofthehybridinput–output(HIO)algorithm.

1559-128X/13/010045-12$15.00/0©2013OpticalSocietyofAmerica

Thisisthemostpersonalpartofthestory.Asagrad-uatestudentintheAppliedPhysicsDepartmentofStanfordUniversity,mythesis[2]advisorwasProf.JosephW.GoodmanintheElectricalEngineeringDepartment,andhehadagranttostudycomputer-generatedholograms(CGHs)asawaytoopticallystoredata.StoringdataopticallyintheFourierdomainratherthanintheimagedomainorthebitdomain,asisdonenowontheCDsandDVDsthatwehaveallusedformusicandmovies,hassomedis-tinctadvantages.SlightmotionofaFouriertrans-formhologramdoesnotchangetheintensityoftheimage,makingittoleranttopositioningthereadoutbeam;smalldefectsinaFourierhologramcauseaddednoiseintheimageratherthanthecompletedroppingofabit,makingiterror-tolerant;andtheilluminationofonehologramcancreateawholetwo-dimensional(2D)arrayofspotsintheimageplanethatcanbereadoutsimultaneously,makingitapage-orientedasopposedtoabit-orientedmem-ory.SinceIwasanamateurphotographerandknewhowthingsworkedinthephotographicdarkroom,IwasgiventhetaskofmakingsomeCGHs.Atthetime(early1972)Iwassimplyphotographingpic-turesofhologramsoutofthebookOpticalHologra-phy(see[3],Figs.19.8and19.11),whichincludedaLohmannandParisCGH[4]andakinoform[5](atthattimeGoodman’sIntroductiontoFourierOptics

1January2013/Vol.52,No.1/APPLIEDOPTICS

45

[6]hadnosuchpictures,althoughthepresentedition[7]does),tryingavarietyofphotographicpositiveandnegativematerials.Bleachingthedevelopedtransparenciesmadephasehologramsandkino-forms.Iwasintriguedbyanaccidentalresult:whileprocessingabatchofKodak5254colorfilm,Iacci-dentallyexposedittoroomlightbeforedevelopment,andtheresultingtransparencymadeareasonablekinoformwithoutbleaching.Thatgavemetheideaofusingaredtransparencyfilm(forusewithaHe–Nelaser)forkinoformsinsteadofbleachingfilm,whichwasinconsistentandtime-consuming.Tryingdifferentmaterials,IfoundthatKodachoromeIIgavealargephaseeffect,whichonecouldseebyeyebylookingatitssurface.KodachromeIIwasamar-velousmaterial,lovedbyphotographersforitsfineresolutionandwonderfulcolorreproduction,andcelebratedinsong[8].Tomakeapure-phaseCGHforilluminationwith,say,redHe–Nelaserlight,onewouldexposeKodachromeIItouniform,brightredlightandtoadesiredpatternofblue/greenlightsothatafterprocessingitwouldbetransparenttoredlight(withlittleornoneofthered-absorbingdye)andhaveadesiredthicknessvariationowingtotheblue-andgreen-absorbinglayers.AnextrabonuswasthattherewasaKodakprocessingplantnexttocampusthatcouldprocessthefilmovernight.Afterthatdiscovery,IviewedKodachromeIIasaveryeasywaytoproducekinoformswithoutthemessy,smellyprocessofbleachingphotographicfilmorplates.Kinoforms[5]areCGHsthatarephase-onlytrans-parenciesthatoperateon-axis,i.e.,withoutacarrierspatialfrequency.Theydirectlyimposephaseonatransmittedwavefrontbyvirtueoftheirspatiallyvaryingthicknessorbulkindexofrefraction(de-pendingonthematerial).Thismakesthemhighlyefficient:100%ofthelightcangointothedesiredor-derofdiffractionsincethereisonlyoneorder,thezerothorder.Aproblemwithkinoforms,however,isthattheycanonlyimpartaphasetothewavefront,whereasafieldthatwillpropagatetoformanimageofadesiredobjectwillvaryinamplitudeaswellasphase.TheamplitudeoftheFouriertransformofareal,nonnegativeobjectisverybrightonaxisandverydimelsewhere,makingthekinoformapproxi-mationverypoor.Thisproblemcanbegreatlyre-ducedbyassigningaquasi-randomphasepatterntotheobject,whichwillresultinadesiredhologramfieldthatismuchmoreuniform,hencebetter,althoughstillnotuniformenough[9].Awaytoadjustthequasi-randomphaseoftheobjecttoimprovetheuniformityofitsFouriertransformwasbyanitera-tivealgorithminventedbyGallagherandLiu[10],althoughtheylaterfoundout[11]thatithadbeeninventedevenearlierbytheinventorsofthekino-form[12].Whattheydevelopedwasawaytoperformspectrumshaping,i.e.,howtoassignaphasetoanobjectorafieldsuchthatitsspectrum(theintensityofitsFouriertransform)wouldapproachadesireddistribution.Thisisanexampleofasynthesisprob-lem.Theyalsofoundout[11]thattheiralgorithm

46

APPLIEDOPTICS/Vol.52,No.1/1January2013

wasverysimilartotheGerchberg–Saxtonalgorithmforsolvingaphaseretrievalprobleminelectronmi-croscopy[13].Thesesimilaralgorithmsworkedasfollows.Supposeafunctionf󰀁x;y󰀂hasFouriertrans-formF󰀁u;v󰀂(ortheyarerelatedbysomeotherpro-pagationintegral),andwearegiventheirmoduli(amplitudes)jf󰀁x;y󰀂jandjF󰀁u;v󰀂j,wherethemoduliareeitherthesquarerootsofmeasuredfieldinten-sitiesorthesquarerootsofdesiredimageandholo-gramintensities.Thealgorithmistostartwithaguessforthefieldintheobjectdomain,typicallyas-signingrandomnumbersforthephaseϕ󰀁x;y󰀂ofg󰀁x;y󰀂󰀃jf󰀁x;y󰀂jexp󰀄iϕ󰀁x;y󰀂󰀅,whichhasthemea-suredordesiredmodulus.Thenperformthefollow-ingfoursteps:(1)transformingthatfieldtotheFourierdomaintogivethefieldG󰀁u;v󰀂󰀃jitG󰀁theu;vmeasured󰀂jexp󰀄iθ󰀁u;orv󰀂󰀅desired,(2)changingmodulusthatinthatfielddomain,togivemakingitG0inverseFourier󰀁u;v󰀂transforming󰀃jF󰀁u;v󰀂jexpthat󰀄iθ󰀁u;backv󰀂󰀅,(3)tothentheobjectdomaintogivetheimageg0exp󰀄iϕ0siredmodulus,󰀁x;y󰀂󰀅,and󰀁x;y󰀂󰀃jg0󰀁x;y󰀂j×resulting(4)theningiveanewittheversionmeasuredofg󰀁x;ory󰀂de-󰀃jϕftion.󰀁󰀁x;x;yy󰀂󰀂jexp󰀄iϕ󰀁x;y󰀂󰀅wheretheearlierversionofTheseisreplacedfourstepsbyϕ0are󰀁x;repeatedy󰀂,completinguntilnoonefurtheritera-progressismadeorforafixednumberofiterations.ThiskindofiterativealgorithmiswidelyreferredtoastheGerchberg–Saxtonalgorithm,eventhoughthepatent[12]camefirst.(Publicationsinarchivaljour-nalsaremoreaccessiblethanpatents.)

TheGallagherandLiupaper(theonlyoneoftheiterativealgorithmpapersofwhichIwasawareinlate1973)inspiredmetotryouttheiralgorithmforkinoforms,toseekimprovementsinthealgorithm,tocontrolquantizationerrorsinotherCGHs,andtouseitforgeneralspectrumshaping[14].ForreducingquantizationerrorsinkinoformsandCGHs,how-ever,Ifoundthat,whileitwouldreducethestandarddeviationoftheerrorintheimageofabitpattern,themaximumerrorforanysinglebitcouldremainundesirablylarge.Tokeepthebiterrorratesmall,itwasimportanttoreducetheerrorsofthoseout-liers.Forwhatfollows,werefertothefunctiong󰀁x;y󰀂aboveastheinputtoaniterationofthealgorithmandg0theoutput.󰀁x;y󰀂TheafterkeythetoinversereducingFouriertheerrortransformoftheout-asliersistheobservationthatiftheinputg󰀁x;y󰀂givesrisetotheoutputg0changeinput,󰀁x;replacingy󰀂,thenitifbywegmake󰀁x;y󰀂󰀆aΔgsmallPinthe󰀁x;ywherex;yjΔg󰀁x;y󰀂j2≪P󰀂,x;yjg󰀁x;y󰀂j2,thentheex-pectedvalueofthenewoutputimageisg0αisΔga󰀁x;constanty󰀂plussomethatadditionaldependsonnoisethe[14statistics],where󰀁x;y󰀂󰀆ofαjthatF󰀁u;wasv󰀂jandsupposedjG󰀁u;vto󰀂j.beSupposezerowasthatapositiveanimagenumber.pixelThentodriveittowardzero,onecouldsubtractfromthecurrentinputα−1timesthepositivenumber,andthenewoutputwouldbeclosertozeroatthatpixel.Thisistheinput–outputpointofview.Init,wethinkofthethreeoperations—Fouriertransforming,

givingtheresultthedesiredFouriermodulus,andtheninversetransforming—asanonlinearsystem.Smallenoughchangestotheinputtothisnonlinearsystemresultincloselyrelatedsmallchangestotheoutputofthesystem.Thatislikesayingthatanon-linearfunctioncanbeapproximatedaslinearoneoverasmallenoughrangeofinputvalues.Notethat,whenthisisdone,thenewinputnolongerhasthedesiredmodulusatthatpixellikeitdoesfortheotheriterativealgorithms,sothenewinputimageisnolongeranestimateoftheobject.

Duringthetimethatthisworkoniterativealgo-rithmswasbeingdone(1973–1974),Prof.GoodmanwasattheInstitutd’OptiqueinOrsay,France,onayear-longsabbatical.Afterreturning,herecom-mendedtome:seeifaniterativealgorithmlikethiscanalsosolvethephaseretrievalproblem.Re-constructingastronomicalimagesfromintensityinterferometrydata[15]orfromstellarspeckleinter-ferometrydata[16]wasofparticularinterest.

Thephaseretrievalproblem,asfoundinx-raycrystallography,astronomicalimaging,Fouriertransformspectroscopyandsomeotherfields,isdif-ferentfromthatfoundinelectronmicroscopyorspectrumshaping.OnetypicallyhasjF󰀁u;v󰀂jfrommeasurements,butinsteadofknowingjf󰀁x;y󰀂j,onetypicallyhasmuchweakerinformation,oftenknow-ing,forexample,thatfisreal-valuedandnonnega-tive,f≥0,andknowingsomethingaboutthesupportoff,i.e.,knowingthatfmustbezerooutsideofsomeregion,thesupportconstraint.ReconstructingffromjandF󰀁u;nonnegativity)v󰀂j(andsomeconstraintsisknownasonthef,suchphaseasretrievalsupportproblem.ItissonamedbecauseifthetrueFouriertransformisF󰀁u;v󰀂󰀃jF󰀁u;v󰀂jexp󰀄iψ󰀁u;v󰀂󰀅,thenre-constructingfisequivalenttoretrievingthephaseψonefromhasjψF,jone(andcansomesimplyconstraintsinverseFourieronf),sincetransformonceFf󰀁󰀁x;u;yv󰀂󰀂.The󰀃jFphase󰀁u;v󰀂jretrievalexp󰀄iψ󰀁u;problemv󰀂󰀅inahadcomputerbeenstudiedtogetformanyyears,butnopracticalalgorithmforsolvingithadbeeninvented.Furthermore,theprospectsseemeddimbecauseitwasunderstoodthatinthecaseofone-dimensional(1D)functionstherewereordinarilyalargenumberofotherfunctionshavingthesameFouriermodulus;thatis,thesolutionwouldnotbeunique,asstudiedforspectroscopy[17]andastronomy(althoughjustinonedimension)[18].Iattemptedusingtheiterativealgorithm,includ-ingusingtheinput–outputapproach,forsolvingthephaseretrievalproblem.Unfortunately,atthatsametimesufficientfundstouseStanfordUniversity’smainframecomputerwererunningthin,soitwassuggestedthatIinsteaduseanewInterdataminicomputerthatwasavailableintheElectricalEngineeringDepartmentfornoextracost.Thatcom-puter,however,wasextremelyslowandhadverylit-tlememoryascomparedwiththemainframe.Forthatreasonthephaseretrievalexperimentswerelimitedto1Dfunctions.Constraintsusedwereanoise-freeFouriermodulus,asupportconstraint

(thewidthoftheobjectwasassumedknown),andanonnegativityconstraint.TheresultsareshowninFig.2of[19].Whiletherewasconsiderablevaria-tioninthevariousreconstructedimages,thegeneralshapeoftheobjectcouldbediscerned,despitetheknownlackofuniquenessforthis1Dphaseproblem.Presumablythenonnegativityconstrainthelpedtopreventthesolutionsfrombeingwildlydifferent.These1Dresultswerenotofsufficientqualityforjournalpublication,butwereincludedinasubsub-sectionofmydissertation[2],whichwasmostlyabouttheReferencelessOn-AxisComplexHologram(ROACH)madewithKodachromeIIfilm,whichal-lowedon-axisamplitudecontrolaswellasthephasecontrolasfromakinoform[20].

B.EarlyPhaseRetrievalatERIM

MyfirstjobaftergraduatingwasatwhatwasthenknownastheEnvironmentalResearchInstituteofMichigan(ERIM),whichwasanindependent,not-for-profitresearchinstitute,whichnotlongbeforehadbeentheWillowRunLaboratoriesoftheUniver-sityofMichigan.Itwasawonderfulhotbedofad-vancedresearchinvariousformsofreconnaissance(radarandoptical),holography,andotherfields.(ItwasboughtbyVeridianSystemsbythetimeIdepartedforacademia27yearslater,andhassincebecomepartofGeneralDynamics—AdvancedInfor-mationSystems.)Whileinitiallyworkingonprojectshavingtodowithsuchthingsasautomaticfocusingforsynthetic-apertureradar,opticalprocessingforradiointerferometerdata,anddiffractiveoptics,Iappliedforinternalresearchanddevelopment(IR&D)fundingtocontinuethephaseretrievalworkIhadstartedatStanford.Suchfundingwaspreciousandmyproposalwasturneddown;thetopicwasdeemednotsufficientlyimportant.TheninthefallofthefollowingyearIattendedtheOSAAnnualMeetinginTucson,whereatalkbyFriedenandCurrie[21]onaphaseretrievalalgorithm,eventhoughitonlyworkedforspecialcases,createdagreatdealofexcitementintheaudience.ThateventemboldenedmetobemoreforcefulinmyrequestforIR&Dfunds,whichweregrantedthenextyear.AtERIMIrepeatedthedigitalexperimentsper-formedatStanford,butwith2Dobjects,whichourPDP11∕45computercouldhandle,withthehelpofaspecialprocessorforperformingfastFouriertransforms(FFTs).Itriedseveralvariationsontheinput–outputalgorithmapplicabletotheimagereconstructionprobleminastronomicalinterfero-metricimagingthatuseddifferentwaysofmodifyingtheinputimage(thefourthstepoftheiterativealgorithm)basedonthecurrentoutputimageandthepreviousinputimage.FromtheGerchberg–Saxtonpointofview,thenextinputimagewouldbetheoutputimage,butmodifiedtosatisfytheobject-domainconstraintsofsupportandnonnega-tivity,i.e.,setthenextinputimagetotheoutputim-agewheretheoutputimagesatisfiestheconstraints,andsetittozerowheretheoutputimageviolatesthe

1January2013/Vol.52,No.1/APPLIEDOPTICS

47

constraints.Thisisreferredtoasthe“error-reduction”approach.The“input–output”approachwouldbetosetthenextinputimagetothepreviousinputimagewheretheoutputimagesatisfiestheconstraints,andsetittothepreviousinputimageminusaconstanttimestheoutputimagewheretheoutputimageviolatestheconstraints.Anotherapproachwasbasedontheinterestingpropertyofthisnonlinearsystem,thatifonetakesanoutputofthesystemandusesthatasanewinput,thenthenewoutputisthesameasthenewinput:thesys-temleavesitunchangedbecausethenewinputalreadysatisfiestheFourier-domainconstraint.Hence,nomatterwhatinputproducesagivenout-put,onecanpretendthattheoutputresultedfromitselfasaninput.The“output–output”approach,then,wouldbetosetthenextinputequaltotheout-putwheretheoutputsatisfiestheconstraints,andsetittotheoutputminusaconstanttimestheoutputwheretheoutputviolatestheconstraints.Ialsotriedothervariations,andtriedmixingandmatchingdifferentoperationsfromdifferentapproachestohandlingthevalueswheretheoutputimageeithersatisfiesorviolatestheconstraints.ThiswasnotthebeautifulmathematicsofanEinsteinthatpredictedwhatwouldhappenlongbeforeanexperimentwasperformed;thiswasthetrialanderrorapproachthatEdisonusedtoinventapracticallightbulb:keeptry-ingdifferentthings(guidedbyphysics,mathematics,andintuition)untilyoufindsomethingthatworks;andthenrefinethat.Thereisbeautifulmathematicssurroundingthephaseretrievalproblem,anditiscenteredaroundthezerosoftheFouriertrans-formanalyticallyextendedtothecomplexplane[17,18,22,23],forexample];butthatbeautifulmathe-maticshadyieldednopracticalphaseretrievalalgo-rithms.MorethanoneofthevariationsItriedworkedtoadegree;butthebestone,bothinthe1DexperimentsatStanfordandthe2DexperimentsatERIM,wasthe“HIO”algorithm.TheHIOapproachistosetthenextinputequaltotheoutputwheretheoutputsatisfiestheconstraints,andsetittotheinputminusaconstanttimestheoutputwheretheoutputviolatestheconstraints;itisahybridbetweentheoutput–output(firstline)andinput–output(sec-ondline)approaches.ItisgivenbyEq.(44)inRef.[1],andwasdescribedinwordsintermsofEq.(2)andEq.(5)inRef.[19],

󰀁

gk󰀆1󰀁x;y󰀂󰀃

g0gk󰀁x;y󰀂;

󰀁x;y󰀂∉γk󰀁x;y󰀂−βg0

y󰀂∈γ

;(1)

k󰀁x;y󰀂;󰀁x;wheregistheoutputk󰀁x;y󰀂isatthetheinputkthiteration,atthekthβiteration,isthefeedbackg0k󰀁x;y󰀂constant,andγisthesetofpointsforwhichtheout-putviolatestheobject-domainconstraints.Foranon-negativityandsupportconstraint,thecondition󰀁wherex;y󰀂∉γScanisthebeexpressedsetofpointsasinside󰀁x;y󰀂∈theS&supportg0k󰀁x;y󰀂con-≥0,straint.Avalueofβsomewherebetween0.5and1.0,say0.7,usuallyworkswell.Ithinkofthevalue

48

APPLIEDOPTICS/Vol.52,No.1/1January2013

ofβasbeingliketheforcewithwhichonedepressestheacceleratorwhiledrivingacarupanarrowmountainroad,seekingthetop.Presstoogently(e.g.,βlessthan0.5),andthecarwillmakesteadyprogress,buttooslowly;presstooforcefully(e.g.,βgreaterthan1.0),andthecarwillprogressmuchmorequickly,butislikelytoveeroffacliffandcrash.The2Dresults,usingsupportandnonnegativityconstraintsintheobjectdomain,weredramatic.Thereconstructedimages,whilenotperfect,wereverygoodrepresentationsoftheobject,muchbetterthanthe1Dcase.Thisimpliedthatthe2Dphasepro-blemwasunique—orelseIwouldhavebeenveryluckyforthealgorithmtohavestumbledontotheso-lutionthatmatchedtheobjectIhadstartedwithratherthanoneoftheothersolutions—incontrasttothenonuniquenesstypicalofthe1Dcase.Hereweconsiderthesolutiontobeuniqueifitisthesametowithinatranslationora180°rotation,sincethoseoperationsdonotchangetheFouriermodulus,andonestillgetsthesamepictureoftheobject.Theseresultscreatedsubstantialinterestatthe1977OSAAnnualMeetinginToronto[24]andwerepublishedinOpticsLettersin1978[19],whichistheseminalpaperontheapproach,althoughitscitationrateislessthanhalfthatofthe1982AppliedOpticspaper.Withgoodimagereconstructionresultsinhand,searchingforexternalfundingimmediatelycom-menced.Onepotentialsponsor,skepticalofthevera-cityoftheresults,arrangedforB.L.McGlamerytosimulateFouriermodulusdatafromstellarspeckleinterferometryofaphotographofasatelliteandsendittomeinablindtest,whichwasasuccess,asde-scribedin[25,26],thelatterofwhichwontheSPIE’sRudolphKingslakeMedalandPrizeforbestpaperinOpticalEngineeringthatyear.Papersontheeffectofnoise[27],resultswithrealstellarspeckleinterfero-metrydata[28],understandingtheuniquenessofphaseretrieval[29],estimatingthesupportoftheobjectfromitsautocorrelationfunction[30],andonawidevarietyofapplicationsoftheiterativetransformalgorithm[14]werepublishedalongwithsummarypapersonthephaseretrievalalgorithm[31,32],allbeforethe1982AppliedOpticspaper.Sowhatwasnewinthatpaper,andwhyisthatpapersohighlycited?

The1982AppliedOpticspaper[1]wasanex-tendedversionofapresentationatthe1981AnnualMeetingoftheOSA[33],whosemainnewpointwasthattheerror-reductionapproach(satisfyingconstraintsineachdomain)wasequivalenttoasteepest-descentgradientsearchalgorithmwithaparticularline-searchstepsize,minimizinganerrormetric,whichwasthesumofsquareddifferencesbe-tweenthecomputedFouriermodulusandthemea-suredone.Aspointedoutin[1],“Therelationshipbetweenagradientsearchmethodandtheerror-reductionalgorithmforaproblemindigitalfilterde-signisdiscussedinRef.13,”i.e.,in[34].[1]alsogivesaproofofconvergenceintheweaksensethattheerrorcouldonlydecreaseorstaythesameateach

iteration.LiuandGallagher[11]showedthisforthecaseofintensitiesinimageandFourierdomains,butin[1]itwasprovenforthegeneralproblemofarbi-trarydataandconstraints.Italsogavethename“transformHIO”tothealgorithm,versionofbuttheitmostwasthesuccessfulsamealgorithmiterativealreadydescribedin[19],whichdidnotgointothatdetailonaccountofthenecessarybrevityofOpticsLetters(oneresearcherusingHIOadmittedtomethathedidnotrealizethatitwassamealgorithmasdescribedin[19]).Itfurthershowedthataconju-gategradientmethodwassuperiortoasteepest-descentmethod.Italsogaveanexamplewithhelpfultipstomakingthealgorithmworksuccessfully.Whilethiswasallgood,itprobablydoesnotdeservetohavemorecitationsthantheseminalpaper[19].Somepossibleexplanationsforthisareasfollows.Perhapstheword“Comparison”inthetitlemadesomepeoplewhodidnotreaditthoroughlythinkthatitwasareviewpaperonphaseretrievalalgo-rithms,whichitwasnotmeanttobe;itwasmeanttocompareiterativetransformalgorithmswithgra-dientsearchalgorithms.Ontheotherhand,sincethecompetingphaseretrievalalgorithmsatthetimewerenoteffectiveforgeneralobjects,itwasineffectcomparingallthedominantphaseretrievalalgo-rithms.Perhapsitisbecauseithadagreatdealofmathematicaldetailonthealgorithms,although[14]hadquiteabitofdetailaswell.Perhapsitisbecauseitdiscussesboththeimagereconstructionandthewavefrontsensingapplications,although[14]didthisaswell.Perhapsafewauthorsofpapers,fortheseorsomeotherreasons,referenced[1]butnot[19],andsubsequentauthorsreadingthesepapersjustreferenced[1]withoutreadingitindetailtofindoutthatitwasjustoneofseveralearlierpapers[14,19,26,27,28,31,32]inwhichIhadwrittenaboutthealgorithm.

ThatthisgroupofpapersissohighlycitedpartlyarisesfromthegeneralityoftheGerchberg–Saxtonalgorithmandthesederivativealgorithms,aswasthemainpointof[14]:

“Thispaperdiscussesaniterativecomputermethodthatcanbeusedtosolveanumberofproblemsinop-tics.Thismethodcanbeappliedtotwotypesofpro-blems:(1)synthesisofaFouriertransformpairhavingdesirablepropertiesinbothdomains,and(2)recon-structionofanobjectwhenonlypartialinformationisavailableinanyonedomain.…

Boththesynthesisandthereconstructionproblemscanbeexpressedasfollows:

Givenasetofconstraintsplacedonanobjectandan-othersetofconstraintsplacedonitsFouriertransform,findaFouriertransformpair(i.e.,anobjectanditsFour-iertransform)thatsatisfiesbothsetsofconstraints.”

Thispaper[14]wasnotjustashowingofresultsforafewdifferentapplications,butwasalsoacalltoarmstotheopticscommunitytoapplyrelatedal-gorithmstomanydifferentproblemsindifferent

fields;yetithasreceivedonly1∕5thecitationsofthe1982AppliedOpticspaper.

Whatfollowsnextarebriefdiscussionsofsomeoftheapplicationareasexploredinthepapersthatcite[1],withwhatiscurrentlythemostimportantsuchapplication(asmeasuredbycitations)savedforlast.

3.ApplicationAreasCitingthe1982AppliedOpticsPaper

Inthissectionwementionsomeofthemorepopularapplicationsareasresultingincitationstothe1982AppliedOpticspaper.Someofthemwerealreadymentionedabove:reconstructionofphasefromtheintensitydistributionofelectronbeamsintwoplanes;imagereconstructionforastronomicalimag-ingincludingfromstellarspeckleinterferometrydata,amplitudeinterferometrydata,andintensityinterferometrydata;andvariousformsofspectrumshapingforCGHs,andforthereductionofquantiza-tionnoise.Inwhatfollowsaresomeadditionalareas.Thisisnotmeanttobeacomprehensiverevieworevenlistingofalltheseareas,butismerelydesignedtogivethereaderanappreciationforthewiderangeofpossibilities.TheparticularreferencescitedaremeantonlytobeexampleswithwhichIwasfamiliarandwhichcitedthe1982AppliedOpticspaper,ratherthannecessarilybeingthefirstormostnote-worthypapersonthetopics.

A.SynthesisProblems

1.BeamShaping

Theiterativealgorithmhasbeenusedbymanyforotherapplicationsofspectrumshaping,alsoknownasbeamshaping.Typicallyonewantsaphase-onlytransparencyortransparencies,toavoidabsorptionoflight,toproduceadesiredintensitypatternoflight.Anexampleofbeamshapingisthedesignofaphaseplatethathassmoothlyvaryingphasethatproducesahigh-powerlaserbeamhavingauniformfar-fieldspeckledistributionforuseininertialcon-finementfusion[35].Three-dimensional(3D)beamshapinghasalsobeenperformed[36].

2.OpticalEncryption

Onecandesignadiffractiveopticalelementthatallowsfortheencryptionofdataforsecurityapplica-tions[37].Theprobleminvolvesjointlydesigningtwodiffractiveelementshavingquasi-randomphases,withfinitepupils,thattogetherreconstructanimagealthoughneitherdiffractiveelementbyit-selfgivesanyhintsastowhatisintheimage.3.OpticalCommunication

Bydesigningthetemporalphaseofalightbeamandtransmittingitthroughafiber,onecancompensateforthedispersionofthefiberandtemporallyconcen-tratetheenergyattheoutputtogiveadesiredbitpattern[38].

1January2013/Vol.52,No.1/APPLIEDOPTICS

49

4.AntireflectionCoatings

Onecaniterativelydesignantireflectioncoatings,whereonewantscertainfeaturesinadesiredspec-tralresponsebuthasconstraintsonthenumberoflayersandtheindicesofrefractionofthemultilayerstructure[39].Thiscanbeextendedtodesigningothertypesofmultilayercoatingsaswell.

B.

ReconstructionProblems

1.WavefrontSensingforRadioAntennas

Bymakingasimplepowermeasurementfromapointsourceonasatellite,onecanmeasurethefar-fieldpat-ternofthetelescope.That,combinedwithknowledgeofthetransverseshapeoftheantenna,allowsthephase(i.e.,longitudinalshapeoftheantenna)tobereconstructedwithaphaseretrievalalgorithm[40],therebydiagnosingthedeformationsoftheradiodish.2.WavefrontSensingforOptics

Similartotheproblemforradiodishes,measuringapoint-spreadfunction(PSF)ofanopticalsystem,to-getherwithknowledgeoftheshapeoftheexitpupiloftheopticalsystem,allowsonetodeterminetheaberrationsoftheopticalsystemwithaphaseretrie-valalgorithm.Thiswasdonefordeterminingtheaberrationsduetoatmosphericturbulence[41],fordeterminingtheaberrationsoftheflawedHubbleSpaceTelescope[42],andhasbeendevelopedforphasingupthesegmentsofthefutureJamesWebbSpaceTelescope[43],foropticalmetrologyinthemanufactureofopticalsurfaces[44],andformeasur-ingx-rayfocusedbeams[45].Withsufficientformsofmeasurementdiversity,itispossibletoreconstructtheamplitudeofthepupilaswellasthephase,i.e.,withoutanypriorknowledgeofthepupil[46].Therearemanyformsofdiversity,mostlymodifyingthephaseintheexitpupilmakingthetotalphasetheunknownphaseplusaknownphaseperturbation.Thismakesthephaseretrievalalgorithmsmorerobusttonoise,toalgorithmstagnation,andtothepossibilityofnonuniquenessandisimportantforapplications,suchaswavefrontsensingforspacetelescopesorforopticalmetrology,whereoneusuallyneedsaveryaccurate,reliablesolution.Themostcommontypeofmeasurementdiversityisfocusdi-versity,aswillbeusedfortheJamesWebbSpaceTelescope[43,47].Otherformsofdiversityincludewavelengthdiversity,pistondiversity(forsegmentedsystems),actuatorpokingdiversity,andtransversetranslationdiversity(ofastructureoranillumina-tionbeamrelativetotheobject)[48,49]anddiversityoffieldpositiontoassessmisalignments[50].Di-versemeasurementsareimportantunderstressingconditions,suchaswhendealingwithbroadbandorundersampleddata[50,51]orwhenreconstructingamplitudeaswellasphase[46].Whenonemeasurestwoplanesofintensitythatareveryneartoonean-other,suchthatonecanestimatethepartialderiva-tiveofthe3Dintensitywithrespecttotheaxialcoordinate,thenonecanalsousewhatiscommonlycalledthetransport-of-intensityapproach[52].

50

APPLIEDOPTICS/Vol.52,No.1/1January2013

3.FROG

Frequency-resolvedopticalgating(FROG)deter-minesthetemporalcharacteristicsoffast(femtose-cond)laserpulses[53,54].FROGtraces,asafunctionoffrequencyandtimedelay,arethesquaredmagnitudeoftheFouriertransformofa2Dsignal,hencesolvablebyaphaseretrievalalgorithm.4.BlindDeconvolution

WhenoneormoreblurredimageshaveunknownPSFs,thenstraightforwardimagerestorationbyde-convolutionisnotpossible.Givenconstraintsonboththeobject,suchassupportandnonnegativityandthePSF(supportandnonnegativityagain),thenonecanuseanalgorithmoftheiterativetransformtypeoragradientsearchalgorithm,butwithanaddi-tionalWienerfilteringstep[55].

5.Tomography

Tomographicimagingcansufferfrommissingprojec-tions[56],orunknownphasesinopticalrefractiontomography[57]anddiffractiontomography[58],whichiterativealgorithmscanfillin.

6.Miscellaneous

Therearealsoanumberofcitingpapersinareasout-sidemyknowledgebasethatfindphaseretrievalalgorithmspertinent,forexamplefordeterminingcomplexGinzburg–Landauequations[59]andcur-rentdistributionsinJosephsonjunctions[60].

ThemostfunisElser’sapplicationofanHIO-likealgorithmtosolvingtheSudokuproblems[61]thatonecanfindinmanydailynewspapers.Initsmostcommonform,onemustfindnumbers1through9toplaceina9×9gridofsquares,separatedinto3×3boxesofsize3×3squareseach,suchthatallthenumbers1through9appearexactlyonceineachlength-9row,onceineachlength-9column,andonceineach3×3box.AlthoughtherearenoFouriertransformsorphases,theproblemdoesinvolvesolv-ingforsystemsofequations,withtheconstraintsmentionedaboveaswellastheconstraintsgivenbythestartingnumbersgiveninsomeofthesquares.7.LenslessImaging

Holographyisanapproachtoimagingwithoutlenses,relyingontheinterferenceofacoherentfield,reflectedfromortransmittedthroughanobjectandpropagatedtothedetectorplane,withareferencebeam.Ifthereisnoreferencebeam,however,thenitisstillpossibletoreconstructanimagefromasin-gleintensitypatternofthepropagatedfieldiftherearestrongenoughconstraintsontheobject,suchasasharplydefinedsupportconstraint[62],whichcanbenaturaltotheobject(abrightobjectonadarkback-ground)orbyvirtueofanilluminationpattern[63],orhavingalow-resolutionimage[64].Alternatively,bycorrelatingthemeasuredspeckleintensity,bythesameprocessasHanbury–BrownandTwissinten-sityinterferometryonecanestimatetheFourier

magnitudeoftheunderlyingintensityreflectivityoftheobjectandwithaphaseretrievalalgorithmreconstructanincoherentimageofthecoherentlyilluminatedobject[65].EmmettLeithoncetoldme,inafriendly,jokingway,thathecalledtheseap-proaches“anti-holography,”sincetheydidawaywiththeneedforholographytoreconstructcomplex-valuedfieldsinsomeinstances.

Mostpapershaveaninitialsurgeincitations,followedbyadecay.The1982AppliedOpticspaper,incontrast,hadarelativelysteadycitationrate(15to30peryear)formanyyears,butthenstartingin2002experiencedasurgethatcontinuestothisday.Thissurgewasaresultofthefinalapplicationareadescribednext.

8.X-rayCoherentDiffractiveImaging(CDI)

Aparticularkindoflenslessimagingistoilluminateamicroscopicobjectwithacoherentbeamofxrays,measuretheintensityofitsfar-fielddiffractionpat-tern,andreconstructanimagefromthatdatausingaphaseretrievalalgorithm(employingsupportandpossiblynonnegativityconstraintsontheobject).Thephaseprobleminx-raydiffractionhasalonghis-tory,andmultipleNobelprizeshavebeenawardedtothosewhosolveditforcrystals.Formanyyearsitwaslimitedtocrystals,inwhichcasethex-rayillu-minationbeamneededtobespatiallycoherentonlyoveramodestnumberofunitcellsinthecrystal.The1982AppliedOpticspapermentionedx-raycrystal-lographyasanapplicationofthephaseretrievalalgorithm.Sayre[66]pointedouttheneedtosamplethediffractionpatternatintervalstwiceasfineastheusualreciprocal-lattice(Braggreflection)points,whichbythemselvesgiveundersampleddata.Theabilitytoavoidtheundersamplingistrivialwhenasmallobjectisnotaperiodiccrystalstructure,sincethereisdataeverywhereinthefarfield,ratherthanjustatreciprocal-spacepoints.Eventuallywithbrighter,more-coherentx-raybeamsfromsynchro-tronradiationandmorerecentlyx-rayfree-electronlasersandeven“table-top”x-raysources,itispossi-bletoobtainbrightbeamswithspatialcoherencewidthsgreaterthanamicrometer,enablingx-raydif-fractionexperimentstobeperformedonnoncrystal-linesamples,andthefieldofx-rayCDIgrew[67].Itwasobviousthatimagescouldbereconstructedfromthisdata,sinceithadbeendonealreadywithlongeropticalwavelengths,bothincomputersimulationexperiments[62]andwithdatagatheredinthelaboratory,evenforcomplex-valuedobjects[68].Nevertheless,itrequiredasuccessfulexperimentwithxrays[69]togalvanizethefield.Reference[70]givesanexcellentaccountofthephaseretrievalapproachtox-rayCDI.

4.SomeOtherAlgorithmDevelopments

Anumberofdevelopmentsintheunderstandingofandinpotentialimprovementsintheiterativealgo-rithmshavetakenplace.

WhytheHIOalgorithmcouldseeminglyclimboutoflocalminimawhiletheerror-reductionalgorithmisoftendoomedtobetrappedinthesamelocalmini-mawasonlypartlyunderstoodatthebeginning.LaterwewereabletodemonstrateconclusivelythatHIOcouldclimboutofsuchlocalminima[71],althoughitwasnotguaranteedtodoso[72].TakajoandTakahashishedlightontheconvergenceproper-tiesofHIO[73,74,75].

Onlybrieflyexploredinthe1982AppliedOpticspaper,theconjugategradientnonlinearoptimizationalgorithmwasshownbyLanetobeeffectiveforim-agereconstruction[76].Gradient-searchnonlinearoptimizationtechniquesweregenerallyfoundtobesuperiortoiterativetransformalgorithmsfortheapplicationofwavefrontsensing[42,77,78],pre-sumablybecausethebulkofthephasecanberepre-sentedbyatenstoafewhundredsofbasis-functioncoefficients,amuchsmallersearchspacethanthethousandstohundredsofthousandsofunknownsrepresentedbyapoint-by-pointphasemap.Theexpressionofaphasefunctionbyabasis-functionex-pansionwithamoderatenumberoftermsalsoservesasaregularizationofthephaseretrievalproblemandavoidsmanylocalminimaassociatedwithnon-physicalphases[42].

Havingagoodsupportconstraintgreatlyimprovestheconvergenceofthealgorithms.Approachestore-constructingupperboundsonthesupportoftheob-jectfromthesupportofitsautocorrelationfunction(whichcanbecomputedfromthegivenFouriermod-ulusdata)wereimproved[30,79]andthe“shrink-wrap”techniqueforrefiningthesupportconstraintduringtheiterationswasdeveloped[70].

Toavoidalgorithmstagnation(beingcaughtinalocalminimum),ithelpsto“sneakuponthesolution”whensolvingthephaseretrievalproblem.Forexam-ple,inthe“expandingFouriermodulus”method[64]thealgorithmconvergesmoresuccessfullyifonefirstreconstructsalow-resolutionimagefromthelowerspatialfrequencies,thengraduallyaddshigherspa-tialfrequenciesreconstructingasuccessivelyfiner-resolutionimage.Forwavefrontsensingapplica-tions,ithelpstoretrievethelarge,low-orderZernikecoefficientsfirstandthenworkuptothehigher-orderZernikecoefficients.

Theerror-reductionalgorithmwasknowntocon-vergeinaweaksense,asdiscussedearlier.Later,Youla[80]setforthaformalismforamoregeneralsetofproblemsandthepopularmethodofprojec-tionsontoconvexsetswasdeveloped[81],includingaproofofconvergenceinastrongsense.Theerror-reductionalgorithmisindeedaprojectionontosetsalgorithm,butitwasnotdescribedinthisHilbert-spaceformalism.Forphaseretrieval,thesetoffunctionhavingthesameFouriermodulusishighlynonconvexandtheerror-reduction/projections-onto-setsalgorithmworkspoorlyforit,asdescribedearlier.

AdditionalvariationsontheHIOalgorithmweredeveloped.ItwasshownthatHIOcouldbe

1January2013/Vol.52,No.1/APPLIEDOPTICS

51

understoodintermsoftheprojectionsontosetsthe-oryandwasaspecialcaseoftheDouglas–Rachfordalgorithm[82].Thehybridprojection–reflection(HPR)algorithm[83]isageneralizationoftheHIOalgorithmwithcomparableperformance.Elser[84]developedthe“differencemap”algorithm,whichalsohasHIOasaspecialcase.

AnothervariationisacontinuousversionoftheHIOalgorithm(CHIO).Itwasdocumentedonlybrieflyina1-pageconferencepaper[85]andneverdiscussedinanarchivaljournal,soafulleraccountisgivenhere.CHIOwasdesignedtoovercomeadrawbackofHIO.Withsuccessiveiterations,HIOhasatendencyforthevaluesatagivenpixeltoos-cillatesomewhatwithincreasingiterationnumber.Theconjecturewasthattheoscillationshadtodowiththefactthattheinputimageatthenextitera-tionisadiscontinuousfunctionoftheoutputimage.Figure1showstherelationshipbetweenthenextin-putvalue,ggk󰀆1󰀁x󰀂asa0functionofthepreviousinputofk󰀁thex󰀂anditerativeitoutputalgorithmgk󰀁x󰀂forwhenthreeemployingdifferentaversionsnonne-gativityconstraintforapoint󰀁x;y󰀂insidethesupportconstraint.InFig.1(a)weseethatfortheerror-reductionalgorithm,thenextinputiszerowhentheoutputvalueisnegativeandequaltotheoutput

Fig.1.Nextinputvalueasafunctionoftheoutputvaluefor(a)error-reduction,(b)HIO,and(c)CHIOalgorithms.52

APPLIEDOPTICS/Vol.52,No.1/1January2013

valuewhereitisnonnegative.InFig.1(b)weseetherelationshipdescribedinEq.(1)forHIO.Thereisadiscontinuousrelationshipbetweenthevalueofthenextinputgoutputg0k󰀆1󰀁x;y󰀂asafunctionofthecurrentoutputvaluek󰀁x;yis󰀂,greaterdependingthanonorwhetherlessthanthezero.currentThisdiscontinuitymightmakethealgorithmmoreviolentthanwhatisoptimal.ThefourthstepoftheCHIOalgorithm,theupdateoftheinput,isillustratedinFig.1(c)andisgivenby

8>>>g󰀂

󰀃∈S&αgk󰀁x;y󰀂≤g0k󰀁x;y󰀂k󰀆1󰀁:k󰀁x;y󰀂−1−αg0k󰀁x;y󰀂;0≤g0k󰀁x;y󰀂≤αgk󰀁x;ygα󰀂:k󰀁x;y󰀂−βg0k

󰀁x;y󰀂;otherwise

(2)

Otherformsarepossible;forexample,byemploy-ingtermsofhigherordering0curvesthathavecontinuousvaluesk󰀁x;yand󰀂,onecontinuouscangetderivativeseverywhere.Theequationabovehascontinuousvaluesbutnotcontinuousderivatives.TotesttheCHIOalgorithm,thesatellitemodelshowninFig.2wasusedastheobject.Itwasem-beddedinanarrayofgreaterthantwiceitswidthandheighttoensurethattheFourierintensityissampledbetterthanNyquist.Figure3showsthemagnitudeofitsFouriertransform,thedatafromwhichwewilltrytoreconstructtheobject.Figure4showsthesupportconstraintusedforthisexperi-ment.Abettersupportconstraintcouldbederivedfromthesupportoftheautocorrelationoftheobject[79],butthismuchloosersupportconstraintwaschosenpurposelytomakethereconstructionmoredifficultforthealgorithms(otherwisetheHIOalgo-rithmreconstructedittooeasily).Figure5showsimagesreconstructedfrom(a)HIO,usingβ󰀃0.7,and(b)CHIO,usingβ󰀃0.7andα󰀃0.4after160iterations.Notethatinbothcasesthereconstructedimageisthetwinimage(rotated108°),whichis

Fig.2.Object.

Fig.3.MagnitudeoftheFouriertransformoftheobject.

consideredtobeanacceptablesolution.ForthisnumberofiterationstheimagefromHIOisconsid-erablyworsethanfromCHIO,suggestingthesuper-iorityofCHIOoverHIO,althoughwithmoreiterationsHIOeventuallyconvergedaswell.

Figure6showstheconvergenceofthetwoalgo-rithms.Thetopcurvesshowtheobject-domainerrormetric,

PE2

o󰀃󰀁Px;y󰀂∈γjg0k󰀁x;y󰀂j2jg0;(3)

k󰀁x;y󰀂j2󰀁x;y󰀂

whereγisthesetofpointswheretheobject-domainconstraints(ofsupportandnonnegativity)arevio-lated;thisishowwellthereconstructedimagesatis-fiesthedataandtheconstraints,andcanbecomputedinreal-worldscenariosasthealgorithmproceeds.Thebottomcurvesshowtheabsoluteerror[86],

P

E2abs

󰀃󰀁x;y󰀂jg0

k󰀁x

P−xo;y−yo󰀂−f󰀁x;y󰀂j2󰀁min

xo;yo󰀂

󰀁x;y󰀂

jf󰀁x;y󰀂j2;(4)

Fig.4.Supportconstraint.

Fig.5.Reconstructedimagesafter160iterationsby(a)HIOand(b)CHIO.

whichisthenormalizedmean-squareddifferencebetweenthetrueobject,f,andthereconstructedimage.Thismetriciscomputedforboththerecon-structedimageanditstwin,andthesmallerofthetwonumbersisreported.Theminimizationovertranslationsisdonetosubpixelaccuracy[87].Thismetricisknownonlyforcomputer-simulationexperi-mentsforwhichthetrueobjectisknown.FromthesecurveswecanseethatCHIOconvergedmuchmorerapidlythanHIOforthisparticularcase;HIOdideventuallyconvergetothesolutionaftermoreiterations.

Fig.6.(Coloronline)Convergenceasafunctionofiterationnum-berforHIOandCHIO.Top:object-domainerrormetric,bottom:absoluteerror(withrespecttothetrueobject).

1January2013/Vol.52,No.1/APPLIEDOPTICS

53

Fig.7.NextinputvalueasafunctionoftheoutputvaluefortheHPRalgorithm.

ThefourthstepoftheHPRalgorithm[83,Eq.(21)]canbewritten

gk󰀆1󰀁󰀁x;y󰀂

󰀃

g0

k󰀁x;y󰀂;󰀁x;y󰀂∈S&gk󰀁x;y󰀂∕󰀁1󰀆β󰀂≤g0k󰀁x;y󰀂

g;(5)k󰀁x;y󰀂−βg0k󰀁x;y󰀂;otherwiseandisillustratedinFig.7.FromthisweseethatHPRisaspecialcaseofCHIOwithα󰀃1∕󰀁1󰀆β󰀂.

5.ConcludingRemarks

TheiterativealgorithmsinventedbyGerchbergandSaxtonandthoseworkingincomputerholographywereadaptedandimprovedforimagereconstructionandwavefrontsensing,includingthedevelopmentoftheHIOalgorithmandgradient-basednonlinearoptimizationalgorithms,andwereexpandedtonumerousdifferentapplicationareasbecauseoftheubiquityofFouriertransformsinphysicsandengi-neeringandthegeneralityandsimplicityofthealgo-rithms,allowingthemtoeffectivelysolveamultitudeofreconstructionandsynthesisproblems.Theseareasandalgorithmscontinuetobeactivelydeveloped,withtheapplicationtox-raycoherentdiffractiveimagingasthecurrentareaofmostrapidgrowth.Formoredetailedreviewsofphaseretrieval,thereaderisreferredto[88,89]forastronomicalimaging,[90]forelectrondiffraction,[91]forcrystallography,and[92]forcoherentdiffractiveimaging.

IwouldliketothankmymanycollaboratorsatERIM/VeridianSystemsandmystudentsandpost-docsattheUniversityofRochesterformakingthissuchamemorablejourney.

References

1.J.R.Fienup,“Phaseretrievalalgorithms:acomparison,”Appl.Opt.21,2758–2769(1982).

2.J.R.Fienup,“Improvedsynthesisandcomputationalmethodsforcomputer-generatedholograms,”Ph.D.Thesis(StanfordUniversity,1975)(ProQuest,UMINo.7525523,orathttp://www.optics.rochester.edu/workgroups/fienup/Professor.htm).3.R.J.Collier,C.B.Burkhardt,andL.H.Lin,OpticalHologra-phy(Academic,1971).

4.A.W.LohmannandD.P.Paris,“BinaryFraunhoferholo-grams,generatedbycomputer,”Appl.Opt.6,1739–1748(1967).54

APPLIEDOPTICS/Vol.52,No.1/1January2013

5.L.B.Lesem,P.M.Hirsch,andJ.A.Jordan,Jr.,“Thekinoform:anewwavefrontreconstructiondevice,”IBMJ.Res.Devel.13,150–155(1969).

6.J.W.Goodman,IntroductiontoFourierOptics(McGraw-Hill,1968).

7.J.W.Goodman,IntroductiontoFourierOptics,3rded.(Roberts,2005).

8.PaulSimon,“Kodachrome”.

9.D.Kermisch,“Imagereconstructionfromphaseinformationonly,”J.Opt.Soc.Am.60,15–16(1970).

10.N.C.GallagherandB.Liu,“Methodforcomputingkinoforms

thatreducesimagereconstructionerror,”Appl.Opt.l2,2328–2335(1973).

11.B.LiuandN.C.Gallagher,“Convergenceofaspectrumshap-ingalgorithm,”Appl.Opt.l3,2470–2471(1974).

12.P.M.Hirsch,J.A.Jordan,Jr.,andL.B.Lesem,“Methodof

makinganobject-dependentdiffuser,”U.S.patent3,619,022(9Nov.1971).

13.R.W.GerchbergandW.O.Saxton,“Apracticalalgorithmfor

thedeterminationofphasefromimageanddiffractionplanepictures,”Optik35,237–246(1972).

14.J.R.Fienup,“Iterativemethodappliedtoimagereconstruc-tionandtocomputer-generatedholograms,”Opt.Eng.l9,297–305(1980).

15.R.HanburyBrownandR.Q.Twiss,“Atestofanewtypeof

stellarinterferometeronSirius,”Nature178,1046–1048(1956).

16.A.Labeyrie,“Attainmentofdiffractionlimitedresolutionin

largetelescopesbyFourieranalysingspecklepatternsinstarimages,”Astron.Astrophys.6,85–87(1970).

17.E.Wolf,“Isacompletedeterminationoftheenergyspectrum

oflightpossiblefrommeasurementsofthedegreeofcoher-ence,”Proc.Phys.Soc.London80,1269–1272(1962).

18.A.Walther,“Thequestionofphaseretrievalinoptics,”Opt.

Actal0,41–49(1963).

19.J.R.Fienup,“Reconstructionofanobjectfromthemodulusof

itsFouriertransform,”Opt.Lett.3,27–29(1978).

20.D.C.Chu,J.R.Fienup,andJ.W.Goodman,“Multiemulsion

on-axiscomputergeneratedhologram,”Appl.Opt.12,1386–1388(1973).

21.B.R.FriedenandD.G.Currie,“Onunfoldingtheautocorrela-tionfunction,”J.Opt.Soc.Am.66,1111(1976)(Abstract).22.R.H.T.Bates,“Contributionstothetheoryofintensity

interferometry,”Mon.Not.R.Astron.Soc.142,413–428(1969).

23.P.J.NapierandR.H.T.Bates,“Inferringphaseinformation

frommodulusinformationintwo-dimensionalaperturesynthesis,”Astron.Astrophys.Suppl.l5,427–430(1974).24.J.R.Fienup,“Reconstructionofanobjectfromthemodulusofits

Fouriertransform,”presentedattheAnnualMeetingoftheOSA,Toronto,Ontario,October1977,Abstract:J.Opt.Soc.Am.67,1389(1977).

25.J.R.Fienup,“Spaceobjectimagingthroughtheturbulent

atmosphere,”Proc.SPIE149,71–81(1978).

26.J.R.Fienup,“Spaceobjectimagingthroughtheturbulent

atmosphere,”Opt.Eng.18,529–534(1979).

27.G.B.FeldkampandJ.R.Fienup,“Noisepropertiesofimages

reconstructedfromFouriermodulus,”Proc.SPIE231,84–93(1980).

28.J.R.FienupandG.B.Feldkamp,“Astronomicalimagingby

processingstellarspeckleinterferometrydata,”Proc.SPIE29.243T.R.,95Crimmins–102(1980).

andJ.R.Fienup,“Ambiguityofphaseretrie-valforfunctionswithdisconnectedsupport,”J.Opt.Soc.Am.30.71J.,R.1026Fienup,–1028T(1981).

.R.Crimmins,andW.Holsztynski,“Recon-structionofthesupportofanobjectfromthesupportofitsautocorrelation,”J.Opt.Soc.Am.72,610–624(1982).

31.J.R.Fienup,“Phaseretrievalinastronomy,”inSignalRecov-eryandSynthesiswithIncompleteInformationandPartialConstraints,digestofpapers(OpticalSocietyofAmerica,1983),paperThA8-1-5.

32.J.R.Fienup,“Imagereconstructionforstellarinterferometry,”

inCurrentTrendsinOptics,F.T.ArecchiandF.R.Aussenegg,eds.(TaylorandFrancisandHalsted,1981),InvitedPapers

fromICO-12Meeting,Graz,Austria,September1981,pp.95–102.

33.

J.R.Fienup,“Comparisonofphaseretrievalalgorithms,”presentedattheAnnualMeetingoftheO.S.A.,Kissimmee,Florida,October1981,Abstract:J.Opt.Soc.Am.71,1641(1981).

34.M.T.ManryandJ.K.Aggarwal,“Thedesignofmultidimen-sionalFIRdigitalfiltersbyphasecorrection,”IEEETrans.CircuitsSyst.23,185–199(1976).

35.

J.A.Marozas,“Fouriertransform-basedcontinuousphase-platedesigntechnique:ahigh-passphase-platedesignasanapplicationforOMEGAandtheNationalIgnitionFacility,”J.Opt.Soc.Am.A24,74–83(2007).

36.S.BuhlingandF.Wyrowski,“Solvingtolerancingandthree-dimensionalbeamshapingproblemsbymultifunctionalwaveopticaldesign,”Opt.Eng.40,1590–1597(2001).

37.E.G.JohnsonandJ.D.Brasher,“Phaseencryptionofbio-metricsindiffractiveopticalelements,”Opt.Lett.21,1271–1273(1996).

38.Y.IvankovskiandD.Mendlovic,“High-rate-long-distancefi-ber-opticcommunicationbasedonadvancedmodulationtech-niques,”Appl.Opt.38,5533–5540(1999).

39.J.Skaar,“Iterativedesignofantireflectioncoatingsbasedonthedirectandinversescatteringtransform,”Opt.Commun.40.232D.Morris,,45–48“Phase(2004).

retrievalintheradioholographyofreflectorantennasandradiotelescopes,”IEEETrans.AntennasPro-pag.33,749–755(1985).

41.

J.N.Cederquist,J.R.Fienup,C.C.Wackerman,S.R.Robinson,andD.Kryskowski,“Wave-frontphaseestima-tionfromFourierintensitymeasurements,”J.Opt.Soc.Am.A42.6J.,R.1020Fienup,–1026J.(1989).

C.Marron,T.J.Schulz,andJ.H.Seldin,“Hub-bleSpaceTelescopecharacterizedbyusingphaseretrievalalgorithms,”Appl.Opt.32,1747–1767(1993).

43.B.H.Dean,D.L.Aronstein,J.S.Smith,R.Shiri,andD.S.Acton,“PhaseretrievalalgorithmforJWSTflightandtestbedtelescope,”Proc.SPIE6265,626511(2006).

44.G.R.BradyandJ.R.Fienup,“Nonlinearoptimizationalgorithmforretrievingthefullcomplexpupilfunction,”Opt.Express14,474–486(2006).

45.M.Guizar-SicairosandJ.R.Fienup,“Measurementofcoher-entx-rayfocusedbeamsbyphaseretrievalwithtransversetranslationdiversity,”Opt.Express17,2670–2685(2009).46.

S.T.Thurman,R.T.DeRosa,andJ.R.Fienup,“Amplitudemetricsforfieldretrievalwithhard-edgeanduniformlyilluminatedapertures,”J.Opt.Soc.Am.A26,700–709(2009).

47.B.H.DeanandC.W.Bowers,“Diversityselectionforphase-diversephaseretrieval,”J.Opt.Soc.Am.A20,1490–1504(2003).

48.H.M.L.FaulknerandJ.M.Rodenburg,“Movableaperturelenslesstransmissionmicroscopy:anovelphaseretrievalalgorithm,”Phys.Rev.Lett.93,023903(2004).

49.M.Guizar-SicairosandJ.R.Fienup,“Phaseretrievalwithtransversetranslationdiversity:anonlinearoptimizationapproach,”Opt.Express16,7264–7278(2008).

50.

J.S.Smith,D.L.Aronstein,B.H.Dean,andD.S.Acton,“forPhasetheretrievalJWSTtestbedonbroadbandtelescope,and”Proc.under-sampledSPIE7436,images7436D(2009).

51.G.R.BradyandJ.R.Fienup,“Effectofbroadbandillumina-tiononreconstructionerrorofphaseretrievalinopticalmetrology,”Proc.SPIE6617,66170I(2007).

52.M.R.Teague,“Deterministicphaseretrieval:aGreen’sfunc-tionsolution,”J.Opt.Soc.Am.73,1434–1441(1983).

53.D.J.KaneandR.Trebino,“Characterizationofarbitraryfemtosecondpulsesusingfrequency-resolvedopticalgating,”IEEEJ.QuantumElectron.29,571–579(1993).

54.

R.TrebinoandD.J.Kane,“Usingphaseretrievaltomeasuretheintensityandphaseofultrashortpulses:frequency-resolvedopticalgating,”J.Opt.Soc.Am.A10,1101–1111(1993).

55.

R.G.Lane,“Blinddeconvolutionofspeckleimages,”J.Opt.Soc.Am.A9,1508–1514(1992).56.C.M.VestandI.Prikryl,“Tomographybyiterativeconvolu-tion:empiricalstudyandapplicationtointerferometry,”Appl.Opt.23,2433–2440(1984).

57.G.K.DattaandR.M.Vasu,“Non-interferometricmethods

ofphaseestimationforapplicationinopticaltomography,”J.Mod.Opt.46,1377–1388(1999).

58.M.H.MalekiandA.J.Devaney,“Phase-retrievalandinten-sity-onlyreconstructionalgorithmsforopticaldiffractiontomography,”J.Opt.Soc.Am.A10,1086–1092(1993).

59.R.P.Yu,D.M.Paganin,andM.J.Morgan,“Inferringgeneral-izedtime-dependentcomplexGinzburg-Landauequationsfrommodulusandgauge-fieldinformation,”Phys.Rev.B.60.77M.,Carmody134512(2008).

,E.Landree,L.D.Marks,andK.L.Merkle,“De-terminationofthecurrentdensitydistributioninJosephsonjunctions,”Phys.C315,145–153(1999).

61.V.Elser,I.Rankenburg,andP.Thibault,“Searchingwith

iteratedmaps,”Proc.Natl.Acad.Sci.104,418–423(2007).62.J.R.Fienup,“Reconstructionofacomplex-valuedobjectfrom

themodulusofitsFouriertransformusingasupportcon-straint,”J.Opt.Soc.Am.A4,118–123(1987).

63.J.R.Fienup,“Lenslesscoherentimagingbyphaseretrieval

withanilluminationpatternconstraint,”Opt.Express14,498–508(2006).

64.J.R.FienupandA.M.Kowalczyk,“Phaseretrievalforacom-plex-valuedobjectbyusingalow-resolutionimage,”J.Opt.Soc.Am.A7,450–458(1990).

65.P.S.Idell,J.R.Fienup,andR.S.Goodman,“Imagesynthesis

fromnonimagedlaserspecklepatterns,”Opt.Lett.12,858–860(1987).

66.D.Sayre,“SomeimplicationsofatheoremduetoShannon,”

ActaCryst.5,843(1952).

67.K.A.Nugent,D.Paganin,andT.E.Gureyev,“Aphaseodys-sey,”Phys.Today54,27–32(2001).

68.J.N.Cederquist,J.R.Fienup,J.C.Marron,andR.G.Paxman,

“Phaseretrievalfromexperimentalfar-fielddata,”69.13J.,Miao,619–621Opt.Lett.P.Charalambous,(1988).

J.Kirz,andD.Sayre,“Extending

themethodologyofx-raycrystallographytoallowimagingofmicrometre-sizednon-crystallinespecimens,”Nature400,342–344(1999).

70.H.N.Chapman,A.Barty,S.Marchesini,A.Noy,S.P.

Hau-Riege,C.Cui,M.R.Howells,R.Rosen,H.He,J.C.H.Spence,U.Weierstall,T.Beetz,C.Jacobsen,andD.Shapiro,“microscopyHigh-resolution,”J.Opt.abinitioSoc.Am.three-dimensionalA23,1179–2000x-ray(2006).

diffraction71.J.H.SeldinandJ.R.Fienup,“Numericalinvestigationofthe

uniquenessofphaseretrieval,”J.Opt.Soc.Am.A7,412–427(1990).

72.J.R.FienupandC.C.Wackerman,“Phaseretrievalstagna-tionproblemsandsolutions,”J.Opt.Soc.Am.A3,1897–1907(1986).

73.H.Takajo,T.Takahashi,H.Kawanami,andR.Ueda,“Numer-icalinvestigationoftheiterativephase-retrievalstagnationproblem:territoriesofconvergenceobjectsandholesintheirboundaries,”J.Opt.Soc.Am.A14,3175–3187(1997).

74.H.Takajo,T.Takahashi,R.Ueda,andM.Taninaka,“Studyon

theconvergencepropertyofthehybridinputoutputalgorithmusedforphaseretrieval,”J.Opt.Soc.Am.A15,2849–2861(1998).

75.H.Takajo,T.Takahashi,andT.Shizuma,“Furtherstudyon

theconvergencepropertyofthehybridinput–outputalgo-rithmusedforphaseretrieval,”J.Opt.Soc.Am.A16,2163–2168(1999).

76.R.G.Lane,“Phaseretrievalusingconjugategradientminimi-zation,”J.Mod.Opt.38,1797–1813(1991).

77.J.R.Fienup,“Phase-retrievalalgorithmsforacomplicated

opticalsystem,”Appl.Opt.32,1737–1746(1993).

78.J.R.Fienup,“Wavefrontsensingbynonlinearoptimization,”

inFrontiersinOptics,OSATechnicalDigest(CD)(OpticalSocietyofAmerica,2006),paperFML2.

79.T.R.Crimmins,J.R.Fienup,andB.J.Thelen,“Improved

boundsonobjectsupportfromautocorrelationsupportandapplicationtophaseretrieval,”J.Opt.Soc.Am.A7,3–13(1990).

1January2013/Vol.52,No.1/APPLIEDOPTICS

55

80.D.C.Youla,“Generalizedimagerestorationbymethodof

alternatingorthogonalprojections,”IEEETrans.CircuitsSyst.25,694–702(1978).

81.D.C.YoulaandH.Webb,“Imagerestorationbythemethodof

convexprojections:Part1—theory,”IEEETrans.Med.Imag.1,81–94(1982).

82.H.H.Bauschke,P.L.Combettes,andD.R.Luke,“Phasere-trieval,errorreductionalgorithms,andFienupvariants:aviewfromconvexoptimization,”J.Opt.Soc.Am.A19,1334–1345(2002).

83.H.H.Bauschke,P.L.Combettes,andD.R.Luke,“Ahybrid

projectionreflectionmethodforphaseretrieval,”J.Opt.Soc.Am.A20,1025–1034(2003).

84.V.Elser,“Phaseretrievalbyiteratedprojections,”J.Opt.Soc.

AmA20,40–55(2003).

85.J.R.Fienup,“Phaseretrievalwithcontinuousversion

ofhybridinput–output,”inFrontiersinOptics,OSATechnicalDigest(CD)(OpticalSocietyofAmerica,2003),paperThI3.

86.J.R.Fienup,“Invarianterrormetricsforimagereconstruc-tion,”Appl.Opt.36,8352–8357(1997).

87.M.Guizar-Sicairos,S.T.Thurman,andJ.R.Fienup,“Efficient

subpixelimageregistrationalgorithms,”Opt.Lett.33,156–158(2008).

88.R.H.T.Bates,“Astronomicalspeckleimaging,”Phys.Rep.90,

203–297(1982).

89.J.C.DaintyandJ.R.Fienup,“Phaseretrievaland

imagereconstructionforastronomy,”ImageRecovery:TheoryandApplication,H.Stark,ed.(Academic,1987),pp.231–275.

90.W.O.Saxton,ComputerTechniquesforImageProcessingin

ElectronMicroscopy(Academic,1978).

91.R.P.Millane,“Phaseretrievalincrystallographyandoptics,”

J.Opt.Soc.Am.A7,394–411(1990).

92.K.A.Nugent,“Coherentmethodsinthex-raysciences,”Adv.

Phys.59,1–99(2010).

56APPLIEDOPTICS/Vol.52,No.1/1January2013