memorygraphsearch

3548IEEETRANSACTIONSONSIGNALPROCESSING,VOL.
56,NO.
8,AUGUST2008SparseRepresentationinStructuredDictionariesWithApplicationtoSyntheticApertureRadarKushR.
Varshney,StudentMember,IEEE,Müjdatetin,Member,IEEE,JohnW.
Fisher,III,Member,IEEE,andAlanS.
Willsky,Fellow,IEEEAbstract—Sparsesignalrepresentationsandapproximationsfromovercompletedictionarieshavebecomeaninvaluabletoolrecently.
Inthispaper,wedevelopanew,heuristic,graph-struc-tured,sparsesignalrepresentationalgorithmforovercompletedictionariesthatcanbedecomposedintosubdictionariesandwhosedictionaryelementscanbearrangedinahierarchy.
Aroundthisalgorithm,weconstructamethodologyforadvancedimageformationinwide-anglesyntheticapertureradar(SAR),deninganapproachforjointanisotropycharacterizationandimageformation.
Additionally,wedevelopacoordinatedescentmethodforjointlyoptimizingaparameterizeddictionaryandrecoveringasparserepresentationusingthatdictionary.
Themo-tivationistocharacterizeaphenomenoninwide-angleSARthathasnotbeengivenmuchattentionbefore:migratoryscatteringcenters,i.
e.
,scattererswhoseapparentspatiallocationdependsonaspectangle.
Finally,weaddressthetopicofrecoveringsolutionsthataresparseinmorethanoneobjectivedomainbyintroducingasuitablesparsifyingcostfunction.
Weencodegeometricobjec-tivesintoSARimageformationthroughsparsityintwodomains,includingthenormalparameterspaceoftheHoughtransform.
IndexTerms—Houghtransforms,inverseproblems,optimiza-tionmethods,overcompletedictionaries,sparsesignalrepresenta-tions,syntheticapertureradar,treesearching.
I.
INTRODUCTIONWHETHERforltering,compression,orhigherleveltaskssuchascontentunderstanding,thetransformationofsignalstodomainsandrepresentationswithdesirableprop-ertiesformstheheartofsignalprocessing.
Thelastdecadeshaveseenovercompletedictionariesandsparserepresentationstakeaplaceintheprocessingofsignalssuchasthosethataremultiscaleinnatureorcanbetracedtophysicalphenomena.
Bysparse,itisexplicitlymeantthatasignalcanbeadequatelyrep-resentedusingasmallnumberofdictionaryelements.
SparseManuscriptreceivedJune29,2007;revisedJanuary5,2008.
ThisworkwassupportedinpartbytheAirForceResearchLaboratorybyGrantFA8650-04-1-1719,andGrantFA8650-04-C-1703(throughsubcontract04079-6918fromBAESystemsAdvancedInformationTechnologies),andbyaNationalScienceFoundationGraduateResearchFellowship.
TheassociateeditorcoordinatingthereviewofthismanuscriptandapprovingitforpublicationwasDr.
YoninaC.
Eldar.
K.
R.
VarshneyandA.
S.
WillskyarewiththeLaboratoryforInformationandDecisionSystems,MassachusettsInstituteofTechnology,Cambridge,MA02139USA(e-mail:krv@mit.
edu;willsky@mit.
edu).
M.
etiniswiththeFacultyofEngineeringandNaturalSciences,SabancUniversity,Orhanl,Tuzla34956˙Istanbul,Turkey(e-mail:mcetin@sabanci-univ.
edu).
J.
W.
Fisher,III,iswiththeComputerScienceandArticialIntelligenceLab-oratory,MassachusettsInstituteofTechnology,Cambridge,MA02139USA(e-mail:sher@csail.
mit.
edu).
Colorversionsofoneormoreoftheguresinthispaperareavailableonlineathttp://ieeexplore.
ieee.
org.
DigitalObjectIdentier10.
1109/TSP.
2008.
919392signalrepresentationandapproximationhasprovensuccessfulinsolvinginverseproblemsarisinginavarietyofapplicationareassuchasarrayprocessing[1],time-delayestimation[2],coherentimaging[3],electroencephalography[4],astronom-icalimagerestoration[5],andothers.
Inverseproblemsmaybecastassparsesignalrepresentationorapproximationprob-lemsinconjunctionwithdictionarieswhoseelementshaveaphysicalinterpretation,havingbeenconstructedbasedontheobservationmodelofaparticularapplication.
Representingasignalusinganovercompletedictionary,involvesndingcoef-cientssuchthat.
Sincethedictionaryisovercomplete,thereisnouniquesolutionforthecoefcients;additionalconstraintsorobjectives,e.
g.
,sparsity,areneededtospecifyauniquesolution.
Amongotherproperties,sparsityandovercompletedictionarieshavebeenknowntodealwellwithundersampleddata,andprovidesuperresolution,parsimony,androbustnesstonoise.
Traditionally,sparsityismeasuredusingthecriterion,whichcountsthenumberofnonzerovalues.
Theproblemofndingtheoptimallysparserepresentation,i.
e.
,withminimumwhereisthesetofcoefcientstakenasavectorin,isacombinatorialoptimizationproblemingeneral.
Duetothedifcultyinsolvinglargecombinatorialproblems,greedyalgorithmssuchasmatchingpursuit[6]andrelaxedformula-tionssuchasbasispursuit[7]thatarecomputationallytractablehavebeendevelopedforgeneralovercompletedictionaries.
Methodologiessuchasthesehavebeenproventoproduceopti-mallysparsesolutionsundercertainconditionsonthedictionary[8]–[10].
Asparsesignalapproximationisasetofcoefcientssubjecttoasparsepenaltysuchthatislessthanasmallpositiveconstant.
Oftentimes,thedictionaryelements,termedatoms,arechosentohaveaphysicalinterpretation.
Atomsmaycorrespondtodifferentscales,translations,frequencies,androtationsorthedictionarymaycomprisesubdictionaries,oftengiventhenamemolecules[11].
Manypopularsparsesignalrepresenta-tionmethodsandalgorithmsaregeneralanddonotexploitnat-uraldecompositionsofthedictionaryintomoleculesorhierar-chicalstructurethatmaybepresentinthecollectionofatoms.
Someapproachesdoexistintheliteraturethattakeadvantageofstructureddictionaries,e.
g.
,[11]–[16].
Amaincontributionofthispaperisanapproximatealgorithmforsparsesignalrep-resentation,relatedtoheuristicsearch,thatusesgraphs,onepermolecule,constructedwithatomsasnodesconnectedaccordingtohierarchicalstructure.
Inthecontextofsolvinginverseproblemsusingsparsesignalrepresentationtechniques,thedesignofatomsbasedontheob-1053-587X/$25.
002008IEEEVARSHNEYetal.
:SPARSEREPRESENTATIONINSTRUCTUREDDICTIONARIES3549servationmodelispredicatedoncompleteknowledgeoftheob-servationprocess.
However,itmaybethecasethatthefunc-tionalformoftheobservationprocessisknown,butthereisde-pendenceonsomeparameterorparametersthatisnotknownapriori.
Inthiscase,itisofinteresttobothoptimizethedictio-naryovertheunknownparametersandtondsparsesolutioncoefcients.
Inovercompleterepresentationcontextsotherthaninverseproblems,thiscanbeviewedassignal-dependentdictio-naryrenement.
Asecondcontributionofthisworkisacoordi-natedescentapproachthatsimultaneouslyrenesthedictionaryanddeterminesasparserepresentation.
Notationally,wetaketobeamatrixwhosecolumnsareatomsfromtheovercompletedictionary,andtoreectparametricdependenceonthesetofparameters.
Thema-trixforadictionarywithmoleculesistheconcatenationofblocks:or.
Afundamentalpremiseofsparsesignalrepresentationisofun-derlyingsparsityinsomedomain,butsignalsmaybesparseinmorethanonecomplementary,orlooselyspeaking'orthogonal,'domain.
Accountingforandimposingsimultaneoussparsityinmultipledomainsisimportantforrecoveringparsimoniousrep-resentations.
Representationalredundancythatmaynotbeap-parentinonedomain,butapparentinsomeotherdomain,canbeappropriatelyreducedthroughsparsityinthatotherdomain.
Weconsiderthisproblemofsparsityinmorethanonedomainand,asathirdcontribution,developaformulationwhoseobjectiveHerewedevelopageneralapproachforsparsesignalrep-resentationorapproximationinwhichweexploitbothmolec-ularstructureindictionariesandhierarchicalstructurewithinmolecules.
Additionally,weincorporatedictionaryoptimiza-tionandsimultaneouslysparsityinmultipledomains.
Whilethemethodshavewiderapplicability,wefocusonmodelingwide-anglespotlight-modesyntheticapertureradar(SAR)asanillustrativeapplication.
Asaconsequence,weadvancethestateoftheartinradarimagingaswell.
SARisatechnologyforproducinghighqualityimageryofthegroundusingaradarmountedonamovingaircraft.
Radarpulsesaretransmittedandreceivedfrommanypointsalongtheightpath.
Thefullcollectionofmeasurementsisusedtoformimages;conventionalimageformationtechniquesarebasedontheinverseFouriertransform.
Inprinciple,verylongightpaths—wide-anglesyntheticapertures—whichhavebecomepossibleduetoadvancesinsensortechnologies,shouldallowforthereconstructionofimageswithhighresolution.
However,phe-nomenasuchasanisotropyandmigratoryscattering,describedinthesequel,whichariseinwide-angleimagingscenariosarenotaccountedforbyconventionalimageformationtechniquesandcauseinaccuraciesinreconstructedimages.
Asweproceedinthedevelopmentofnovelsparsesignalrepresentationmethodsforstructureddictionaries,weusethemethodsdescribedhereininawaythatdoesaccountforsuchphenomenology.
InSectionII,wedescribeaheuristicgraph-structuredalgo-rithmforproducingsparserepresentationsinhierarchicalover-completedictionaries.
SectionIIIexpandsthescopeoftheal-gorithmtodictionariescomposedofmolecules.
ThemotivatingapplicationinSectionIIandSectionIIIisthecharacterizationofanisotropyinwide-angleSARmeasurements,ahurdlethatoncecleared,notonlyrelievesinaccuraciesinimagereconstruction,Fig.
1.
Illustrationofmatrix888forN=5.
Thesoliddots()indicateanonzerovalueandtheemptydots()indicateazerovalue.
butalsoprovidesawealthofinformationforunderstandingandinferencetaskssuchasautomatictargetrecognition.
SectionIVdiscussesparameterizeddictionariesandthejointoptimizationoftheexpansioncoefcientsandtheatomsthemselves.
TheSARprobleminvestigatedinthissectionisofextractingob-ject-levelinformationaspartoftheimageformationprocessfrommigratoryscatterers.
SectionVintroducestheobjectiveofsparsityinmultipledomains,focusingprimarilyonthetwodo-maincase,specicallywiththeHoughtransformdomainandtheSARmeasurementdomain.
TheapplicationsinSectionIVandSectionVtakestepstowardsbridginglow-levelradarsignalprocessingandhigher-levelobject-basedprocessinginwaysnotseenintheSARliteraturebefore.
SectionVIprovidesasum-maryofourcontributions.
II.
GRAPH-STRUCTUREDALGORITHMFORHIERARCHICALDICTIONARIESAttheoutset,weconsideradictionarythatdoesnotdecom-poseintomoleculesandisknownandxed.
Welookatapartic-ulartypeofdictionarywithahierarchicalarrangementofatomsthatpermitstheconstructionofagraphwiththeatomsasnodes.
Then,wedescribeanalgorithmbasedonhill-climbingsearch,aheuristicsearchmethodalsoknownasguideddepth-rstsearch.
Thenalpartofthesectionappliesthealgorithmtothecharac-terizationofanisotropyofapoint-scatteringcenterfromwide-angleSARmeasurements.
A.
GraphStructureOftentimesinovercompletedictionaries,includingforex-amplewaveletpacketdictionaries[17],B-splinedictionaries[18],anddiscretecomplexGabordictionaries[6],theatomshaveanotionofscaleandconsequentlyacoarse-scaletone-scalehierarchy.
Translationsorrotationsareappliedatnerscalestocreatesetsofatomsthathaveacommonsizebutaredifferentiatedintheplacementoftheirregionofsupport;there-gionsofsupportmayormaynotoverlap.
Somedictionariesareconstructeddyadicallysuchthatthesupportofacoarseratomistwicethesizeofthenextneratomoratoms.
Inthispaper,weconsiderdictionariesinwhichthesizeofthesupportchangesarithmeticallyratherthangeometricallybe-tweenscales.
Thematrixofsuchadictionaryforone-dimen-sionalsignalsoflengthisillustratedinFig.
1;thecoarsestatomistherstcolumnandthenestatomsaretheright-mostcolumns.
Afullsetofsuchatomswithallwidthsandallshiftshaslargecardinality[atoms],butisappealingforinverseproblemsbecauseofthepossibilitythatasuperposi-tionofveryfewatoms,perhapsjustone,correspondstoaphys-icalphenomenonofinterest.
AsdiscussedinSectionII-C,forSARanisotropycharacterization,thesignalandatomsare3550IEEETRANSACTIONSONSIGNALPROCESSING,VOL.
56,NO.
8,AUGUST2008Fig.
2.
Illustrationofgraphstructureforovercompletedictionary,N=5.
Coarse-scaleatomsareatthetopandne-scaleatomsareatthebottom.
Dif-ferenttranslationsareinorderfromlefttoright.
Fig.
3.
Illustrationofsearch-basedalgorithmforN=7,G=3.
Theguidinggraph,asubgraphofthefullmoleculargraphindicatedbytriangularoutline,ismovediterativelytondasparserepresentation.
Theinitializationandrsttwoiterationsareshown.
Moleculargraphedgesandnodelabelsareomitted.
suchthatisnonzeroforcontiguousintervalsandzeroforotherpartsofthedomain,andiswellrepresentedbyfewatoms.
Duetotheregularstructureofthistypeofdictionary,wecantaketheatomsasnodesandarrangetheminagraph.
AsshowninFig.
2,thecoarsestatomistherootnode,thenestatomsareleaves,andthegraphhaslevels.
Eachnodehastwochildren(exceptforthoseatthenestlevel).
Itisaweaklyconnecteddirectedacyclicgraph,withatopologicalsortthatisexactlytheorderingfromlefttorightofthecolumnsinillustratedinFig.
1.
Asweproceed,wemakeuseofthegraphstructure,whichwetermthemoleculargraph,treatingthesparsesignalrepresentationproblemasagraphsearch.
B.
AlgorithmBasedonHill-ClimbingAsmentionedinSectionI,manygeneralmethodsforob-tainingsparserepresentationsgiveprovablyoptimalsolutions(undercertainconditions),butrequirethesamecomputationandmemoryregardlessofwhetherthedictionaryhasstructure.
Asanalternativeapproachforstructureddictionaries,wepro-poseaheuristicallybasedtechniquewithreducedcomplexity.
Theideatohaveinmindduringtheexpositionofthealgorithmisofasmallsubgraph,giventhenameguidinggraph,itera-tivelymovingthroughan-levelmoleculargraph,searchingforaparsimoniousrepresentation.
Thespecicsoftheguidinggraph,thesearchstrategy,andsearchstepsarepresentedhere.
Fig.
3illustratesthecentralideaofthealgorithmforasmalldictionary;inpractice,thedictionaryandthereforemoleculargraphareofmuchlargercardinality.
Weassumethat,thesignaltoberepresentedorapproxi-mated,canbecomposedusingafewatomswhosenodesareclosetogetherinthemoleculargraphunderacommonparentnode.
Thisassumptionisnotasrestrictiveasitmayseem:thatthesignalhasarepresentationwithafewatomsisbasicforspar-sity.
Contributingnodesareclosetogetherinthegraphwhenthesignalislocalizedinthedomain.
Priorknowledgecanguidethechoiceofatomshapeandstandardfamiliesofatomsmaybeused.
TheassumptionsarereasonableforSARandotherappli-cationsthatlendthemselvestosuchhierarchicalstructures.
Theproblemofndingcoefcientssuchthatequalsorwellapproximateswithfewnonzeromaybereformulatedasasearchforanodeorafewnodesinthemoleculargraph.
Inadditiontondingnodes,i.
e.
,atomsthatcontributetotheexpansion,thecorrespondingcoefcientvaluesmustalsobedetermined.
Numeroussearchalgorithmsexisttondnodesinagraph.
Blindsearchalgorithmsincorporatenopriorinformationtoguidethesearch.
Incontrast,heuristicsearchalgorithmshavesomenotionofproximitytothegoalavailableduringthesearchprocess,allowingthesearchtoproceedalongpathsthatarelikelytoleadtothegoalandreduceaverage-caserunningtime.
Hill-climbingsearchisanalgorithmsimilartodepth-rstsearchthatmakesuseofaheuristic.
Indepth-rstsearch,onepathisfollowedfromroottoleafinapredeterminedway,suchas:"alwaysproceedtotheleft-mostunvisitedchild.
"Incon-trast,hill-climbingsearchwill"proceedtothemostpromisingunvisitedchildbasedonaheuristic.
"Inbothalgorithms,ifthegoalisnotfoundonthewaydownandthebottomisreached,thereisback-tracking.
Theapproachpresentedherehashill-climbingsearchasitsfoundation.
Instandardgraphsearchproblems,nodesarelabeledandthegoalofthesearchisxedandspeciedwithalabel,e.
g.
,"ndnodeK.
"Thusthestoppingcriterionforthesearchissimplywhetherthelabelofthecurrentnodematchesthegoalofthesearch.
Also,thereisoftenanotionofintrinsicdistancebetweennodesthatleadstosimplesearchheuristics.
Whenthesparsesignalrepresentationproblemisreformu-latedasasearchonan-levelmoleculargraph,stoppingcri-teriaandheuristicsarenotobvious.
Onecleardesideratumisthatcalculationofbothshouldrequirelessmemoryandcompu-tationthansolvingthefullproblem.
Theguidinggraph,chosentobea-levelmoleculargraph,,withitsrootatthecurrentnodeofthesearch,guidesthesearchbyprovidingsearchheuristicsandstoppingconditions.
Intuitionabouttheproblemsuggeststhatiftheatomoratomsthatwouldcontributeinanoptimallysparsesolutionarenotin-cludedintheguidinggraphwhensolvingforcoefcientsinasparsityenforcingmanner,thentheresultingsolutionwillhaveanonzerocoefcientfortheatommost'similar'tothesignal.
Intermsofthe-levelmoleculargraph,thissuggeststhatiftheoptimalsparserepresentationisfardowninthemoleculargraph,buttheproblemissolvedwithasmalldictionarycon-tainingatomsfromaguidinggraphnearthetopofthemolec-ulargraph,thencoefcientsintherstlevelswillbezeroandoneormorecoefcientsinlevelnonzero.
Inthesamevein,iftheguidinggraphisrootedbelowtheoptimalrep-resentation,thentherootcoefcientmaybenonzeroandthecoefcientsinlevelstwothroughwillbezero.
IftheguidingVARSHNEYetal.
:SPARSEREPRESENTATIONINSTRUCTUREDDICTIONARIES3551graphissuchthatitcontainstheoptimalatoms,thenthecorre-spondingcoefcientswillbenonzeroandtherestofthecoef-cientszero.
Thisintuitionisdemonstratedempirically;detailsareintheAppendix.
Asimpleheuristicforthesearchbasedonthecoefcientvaluesofthenodesinlevelisapparentfromtheintuitionandexperimentalvalidation.
Duetothestructureofthemolec-ulargraph,eachnodehastwochildren,sotheheuristicisusedtodeterminewhethertoproceedtotheleftchildortherightchild.
Wendthecenterofmassofthebottomlevelcoefcientmagnitudes—thesearchisguidedtowardsthesidethatcontainsthecenterofmass.
Astoppingcriterionisalsoapparent:stop-pingwhenallofthenodesinlevelarezeroduringthesearch.
Hill-climbingsearchndsasinglenode—asingleatom.
However,thealgorithmthatweproposeisabletondasmallsubsetofatomsduetotheguidinggraph.
Whenthestoppingcriterionismet,i.
e.
,whenthenest-scalecoefcientsareallzerointhesparsesolutionoftherepresentationproblemwithatomsfromthecurrentguidinggraph,thenthatsparsesolutionistakenasthesolutiontothefullproblem.
Consequently,theguidinggraphallowsasubsetofatomsratherthanasingleatomtobeusedintherepresentation.
Insummary,thealgorithmbasedonthemoleculargraphandhill-climbingsearchisasfollows.
(1)Initialization:Leti1and888(i)atomsfromthetopGlevelsofthemoleculargraph.
(2)Findasparsea(i)suchthat888(i)a(i)approximatesg.
(3)Calculateweightedsumofbottomrowcoefficientmagnitudes:Gm=1mja(i)(G0G)=2+mj.
(4)If=0thenstop.
Otherwise,ii+1.
Ifbottomrownodesareleavesofthemoleculargraphorbothchildrenoftheguidinggraphhavebeenvisitedbefore,then888(i)atomsfromthehighestunvisitedguidinggraph.
Else,888(i)(<((G+1)=2)Gm=1ja(i)(G0G)=2+mjandleftchildunvisitedatomsfromtheleftchildguidinggraph:atomsfromtherightchildguidinggraph).
Iteratetostep(2).
Thegraph-structuredalgorithmthatweproposeisabletoproducerepresentationsinwhichtherearecontributionsfromatomsthatliewithinthespanofaguidinggraph.
Theapprox-imatenatureoftheapproachiscontrolledby;byincreasingthesizeoftheguidinggraphwemay,attheexpenseofincreasedcomplexity,drawfromalargersubsetofatomsinthesolution.
Thesmallerproblemwithismoretractablethanthelargeproblemwith.
Whileanyofanumberofformulationsandtechniquesmaybeusedtosolvethesmallerproblem,hereweuseanonconvex,,relaxation,minimizingthecostfunction(1)byaquasi-Newtontechniquedetailedin[19]toobtainasparsevectorofcoefcients.
Eachstepofthequasi-Newtonmin-imizationinvolvessolvingasetoflinearequations,whereFig.
4.
Comparisonofgraph-structuredalgorithmandmatchingpursuit.
(a)Signalg.
(b)Atomsscaledbycoefcientsinsolutionobtainedwithgraph-structuredalgorithm.
(c)Atomsscaledbycoefcientsinsolutionobtainedwithmatchingpursuit.
isthenumberofatomsintheguidinggraph.
Directso-lutionrequirescomputations.
However,theparticularmatrixinvolvedisHermitian,positivesemidenite,andusuallysparse,sotheequationsmaybesolvedefcientlyviaiterativealgorithms.
Weusetheconjugategradientmethodandterminateitwhentheresidualbecomessmallerthanathreshold.
Theparametertradesdatadelity,therstterm,andspar-sity,thesecondterm.
Thechoiceofisimportantpracticallyandisanopenareaofresearch.
Withtoosmall,thesolu-tioncoefcientvectorisnotsparseandtheheuristicisnotmeaningful;theguidinggraphstraysawayfromgoodsearchpaths.
Withtoolarge,thealgorithmincorrectlyterminatesearlywithallzerocoefcientsinthesolution.
Inthispaper,wechoosetheparametersubjectivelyandcanusuallysetitonceforagivenproblemsize.
Wekeepconstantforalliterationsofthegraph-structuredalgorithm.
Generally,solutionsinstep(2)ofthealgorithmarenotverysensitivetosmallperturbationsof.
Itispossible,however,forasmallchangeintocausethenumberofnonzeroelementsinthesolutiontochange,butsuchachangeinsolutionisnotnecessarilyaccompaniedbyachangeintheheuristicandstoppingcriterion.
Inallexamplesinthispaper,theoftherelaxationis0.
1;forthehighlyre-dundantdictionarythatisemployed,asmallvalueofresultsinsuitablesparsity.
Thesearch-basedprocedurewehavepresentedisgreedy,butnotinthesamewayasmatchingpursuitandrelatedalgorithms[6],[14]–[16].
Acommitmentisnotmadetoincludeanatomintherepresentationuntilthenaliterationwhenthestoppingcri-terionismet,andalso,atomswithinaguidinggraphareconsid-eredjointly.
Astheguidinggraphslidesdownward,anysubsetofne-scaleatomscanstartcontributingtotherepresentation.
Thisbehaviordiscouragestheassignmentofacoarse-scaleatomtorepresentwhatwouldbebetterrepresentedusingafewclosene-scaleatoms.
Insomelateriteration,amatchingpursuit-likealgorithmincludesane-scaleatomwithanegativecoefcienttocancelextraenergyfromthecoarse-scaleatomincludedear-lier.
AnexampleofthisbehaviorisgiveninFig.
4.
Forapartic-ularsignalandanovercompletedictionaryofboxcar-shapedatoms,solutionsareobtainedusingboththegraph-structuredal-gorithmpresentedinthissectionandthebasicmatchingpursuitalgorithm[6],andcompared.
Boththegraph-structuredalgo-rithmandmatchingpursuitproducesolutionsthatsumtoap-proximate,butthedecompositionofthegraph-structuredal-gorithmismoreatomic.
3552IEEETRANSACTIONSONSIGNALPROCESSING,VOL.
56,NO.
8,AUGUST2008Fig.
5.
Groundplanegeometryinspotlight-modeSAR.
Thealgorithmfordictionarieswithoutmoleculardecomposi-tionisstraightforward;itsoperationindictionarieswithmolecules,whichwediscussinSectionIII,ismoreinteresting.
Beforereachingthatpointhowever,weillustratetheapplicationofthismethodtoanisotropycharacterizationinSAR.
C.
ApplicationtoWide-AngleSARSpotlight-modeSARhasaninterpretationasatomographicobservationprocess[20].
AsmentionedinSectionI,SARusesaradarmountedonanaircrafttocollectmeasurements.
Fromonepointalongtheaircraft'sightpath,theradartransmitsamodulatedsignalinacertaindirection,illuminatingaportionofthegroundknownasthegroundpatch,andreceivesbackscat-teredenergy,whichdependsonthecharacteristicsofthegroundpatch.
Radarsignalsaresimilarlytransmittedandreceivedatmanypointsalongtheightpath.
Theradarantennacontinuallychangesitslookdirectiontoalwaysilluminatethesamegroundpatch.
Thegeometryofdatacollectioninspotlight-modeSARisillustratedinFig.
5.
Coordinatesonthegroundplane,range,and,cross-range,arecenteredinthegroundpatch.
Measurementsaretakenatequallyspacedaspectanglesastheaircrafttraversestheightpath.
Thegroundpatch,withradius,isshaded.
Thescatteringfromthegroundpatchunderobservationismanifestedasanamplitudescalingandphaseshiftthatcanbeex-pressedasacomplexnumberateachpoint.
Thus,scatteringfromtheentiregroundpatchcanbecharacterizedbyacomplex-valuedfunctionoftwospatialvariables,whichisreferredtoasthescatteringfunction.
Duetothedesignoftheradarsignalandthephysicsoftheobservationprocess,thecollectionofreceivedsignalsisnotdirectly.
Proceduresforobtainingfromthemeasurementsareknownasimageformation.
Inwide-angleSAR,measurementscomefromvastlydifferentviewpointsandconsequently,scatteringbehaviorshowsdepen-denceon,referredtoasanisotropy,aswellason[21].
Forexample,amirror-likeatmetalsheetreectsstronglywhenviewedstraighton,butbarelyreectsfromanobliqueangle.
Therelationshipbetweenthemeasurements,obtainedoveranitebandwidthoffrequenciesandoverarangeofaspectangles,andtheanisotropicscatteringfunctionisgivenby(2)whereisthespeedatwhichelectromagneticradiationprop-agates.
Thesetofaspectanglesisinherentlydiscrete,be-causepulsesaretransmittedfromadiscretesetofpointsalongtheightpath.
Themeasurementsaresampledinfrequencytoallowdigitalprocessing.
Thecollectionofmeasurementsisknownasthephasehistory.
Thescatteringresponseofobjectssuchasvehiclesonthegroundiswell-approximatedbythesuperpositionofre-sponsesfrompointscatteringcenterswhenusingfrequenciesandaperturelengthscommonlyemployedinSAR[22].
Theanisotropicscatteringfromasinglepoint-scatterertakestheformandthemeasurementmodelis(3)Thephenomenonofanisotropyoftenmanifestsaslargemag-nitudescatteringinacontiguousintervalofandsmall,closetozeromagnitudescatteringelsewhere.
Consequently,thedic-tionarydescribedinSectionII-Acontainingallwidthsandallshiftsofcontiguousintervalsiswellsuitedforobtainingparsi-moniousrepresentationsofanisotropicscattering.
Anovercom-pleteexpansionisasfollows:(4)Atomsare,wherearedilationsandtranslationsofacommonpulseshape.
Wecanuseboxcarpulses,Hammingpulses,orothershapesthatweexpecttoencounter.
Anisotropyofnarrowangularextentcomesfromphysicalobjectsdistributedinspaceandanisotropyofwideangularextentcomesfromphysicalobjectslocalizedinspace;hence,theatomsprovideadirectlymeaningfulphys-icalinterpretation.
Appropriatelystackingthemeasurementsatdifferentfrequencies,wehavethesparsesignalrepresentationproblemwithanonmolecularhierarchicaldictionaryandcanobtainsolutionsusingthegraph-structuredalgorithmdescribedabove.
D.
AnisotropyCharacterizationofSinglePoint-ScattererWenowshowanisotropycharacterizationonSARphasehis-torymeasurementsfromXPatch,astate-of-the-artelectromag-neticpredictionpackage,usingthegraph-structuredheuristicmethoddescribedinthissection.
Ascenecontainingasinglescattererismeasuredataspectanglesspacedonedegreeapart.
ThescatteringmagnitudeasafunctionofaspectangleisthegraylineplottedinFig.
6(a).
(Thelineshowsthemeasurementsatoneparticularfrequencywithinthefrequencybandcoveredbytheradarpulse;frequencydependenceismin-imalandscatteringmagnitudeatallfrequenciesisnearlythesame.
)Usingboxcarpulsesforatomsintheovercompletedictionaryandaguidinggraphofsize,weobtainasparseapprox-imationfortheaspect-dependentscatteringgivenbytheblacklineinFig.
6(a).
Thesearchpathofthegraph-structuredalgo-rithmisshowninFig.
6(b).
Thelineindicatesthelocationoftherootnodeoftheguidinggraphwithinthefullmoleculargraph.
VARSHNEYetal.
:SPARSEREPRESENTATIONINSTRUCTUREDDICTIONARIES3553Fig.
6.
Singlepoint-scattererexample:(a)Aspect-dependentscatteringmag-nitudemeasurement(grayline)andsolution(blackline).
(b)Searchpathofgraph-structuredalgorithm.
Whenthestoppingcriterionismet,theatomattherootoftheguidinggraphisofwidth34samples.
Thenestatomsthatcon-tributetotheapproximationhavewidth4samples.
Thesparsesolutionhas14nonzerocoefcientsoutofapossiblecoefcientsfor.
Fromthesolution,itispossibletoinferphysicalpropertiesabouttheobjectbeingimagedbecausethinanisotropycorre-spondstoobjectsoflargephysicalsizeandwideanisotropytoobjectsofsmallphysicalsize.
Sparsityandtheparticularovercompletedictionaryareimportantbecausetheyallowthischaracterizationdirectlybyidentifyingthecoarsestnonzerocoefcient.
III.
ALGORITHMFORMOLECULARDICTIONARIESIntheprevioussection,wedescribedasearch-basedalgo-rithmfordictionarieswhoseatomshaveahierarchy,butdidnotconsiderdictionariesthathaveamoleculardecompositionintosubdictionaries.
Inthissection,theheuristicalgorithmisex-tendedbyapplyingittodictionarieswithmolecules,eachindividuallyhavingahierarchicalstructureofatoms.
Wehavecoexistingmoleculargraphsandthusnotjustonesearch,butsimultaneoussearches.
Asweshallsee,thesesearchesarenotperformedindependently,butratherinteractandinuenceeachother.
Forjointanisotropycharacterizationandimageforma-tion,themoleculescorrespondtodifferentpoint-scatterersorspatiallocationsinthegroundpatchbeingimaged.
A.
MolecularDictionariesOvercompletedictionariescomposedofmoleculesarefairlycommon,arisinginoneoftwoways.
Therstisastheunionoftwoormoreorthogonalbasesandthesecond,throughde-pendenceonsomeparameterthattakesthesamevalueforonesubsetofatoms,anothervalueforasubsetdisjointfromtherst,andsoon.
Anexampleoftherstinstanceisadictionarymadeupoftheunionofanorthogonalbasisoflappedcosinesandanorthog-onalbasisofdiscretewaveletsthatprovidesatomstorepresenttonalandtransientcomponentsinaudiosignals[11];thesameideaisusedforimagesaswell,takingtwodifferentbasesto-getherasanovercompletedictionary,oneforperiodictexturesandoneforedges[23].
Anexampleinaudioofthesecondin-stanceismoleculeswhoseatomsshareacommonfundamentalfrequency[12].
IntheradarimagingexampleinSectionIII-D,atomswithinmoleculesshareacommonlocationanddif-ferentmoleculescorrespondtodifferentspatiallocations.
Thetwotypesofdecompositionsintomoleculespresentdif-ferentproperties.
Inthersttype,differentmoleculesaimtorep-resentverydifferentphenomenaandareincoherentfromeachother,whereasinthesecond,themoleculescorrespondtodif-ferentinstancesofthesamephenomenonandmaybehighlyco-herent.
Inthispaper,weconsiderdictionarieswhosemoleculesallhavehierarchicalstructurethatpermitstheconstructionofmoleculargraphs,regardlessofdecompositiontype.
Weusesimultaneoussearchesonallmoleculargraphs;thedifcultyoftheproblemincreasesasthecoherencebetweenmoleculesincreases.
B.
InteractingSearchesonMultipleGraphsThegeneralframeworkforthegraph-structuredalgorithmwithdictionariescontainingmorethanonemoleculeisthesameasfordictionarieswithoutmolecules,butwithafewkeydiffer-ences.
Herethedictionaryisoftheformwitheachmoleculehavingamoleculargraph.
Weassumethatallatomsinthedictionaryaredistinctandthatmoleculesdonotshareatoms.
guidinggraphsiteratethroughthemoleculargraphs,oneguidinggraphpermoleculargraph.
Thevectorofcoefcientsalsopartitionsas.
searchesareperformedsimultaneously,asfollows.
(1)Initialization:Leti1andforallmoleculesl=1;.
.
.
;L,888(i)latomsfromthetopGlevelsofmoleculargraphl.
888(i)[888(i)1111888(i)L].
(2)Findasparsea(i)suchthat888(i)a(i)approximatesg.
(3)Foralll=1;.
.
.
;L,calculateweightedsumofbottomrowcoefficientmagnitudes:lGm=1mja(i)l;(G0G)=2+mj.
(4)IfLl=1l=0thenstop.
Otherwise,ii+1.
Foralll=1;.
.
.
;L,ifl=0,then888(i)l888(i01)l.
Elseifbottomrownodesareleavesofmoleculargraphlorbothchildrenofguidinggraphlhavebeenvisitedbefore,then888(i)latomsfromthehighestunvisitedguidinggraph.
Else,888(i)l(l<((G+1)=2)Gm=1ja(i)l;(G0G)=2+mjandleftchildunvisitedatomsfromtheleftchildguidinggraph:atomsfromtherightchildguidinggraph).
Iteratetostep(2).
Letusemphasizethatalthoughthesearchesareperformedsimultaneously,theyarenotperformedindependently.
Thesearchesarecoupledbecausetheinverseproblemissolvedjointlyforallmoleculesoneveryiteration;contributionstothereconstructionoffromallofthemoleculesinteract.
Thereisnonotionofmoleculeswhensolvingthesmallerinverseproblem.
Themolecularstructureonlycomesintoplayafterhasbeensolved,andtheheuristics,stoppingcriteria,andupdatesaretobecalculated.
Sincewecon-siderallmoleculesjointlyratherthanoneatatimeasmatchingpursuit-likealgorithmswoulddo,weseesimilaradvantagesoftheformulationpresentedheretothoseseeninFig.
4forthesinglemoleculecase.
Thedictionaryusedincalculatingtheheuristicandstoppingcriterionhasatomspermoleculeandatomsformolecules,insteadofatomsusedifonewereto3554IEEETRANSACTIONSONSIGNALPROCESSING,VOL.
56,NO.
8,AUGUST2008solvethefullinverseproblem.
However,thegraph-structuredalgorithmrequiresiterations,whereassolvingthefullinverseproblematoncerequiresjustoneiteration.
isasmallconstantthatisfairlyindependentof.
Forjointanisotropycharacterizationandimageformation,andmaybeinthethousands.
TherealisticexamplegiveninSectionIII-Ewouldhaveeighty-ninemillionatomsifthefullproblemweresolvedatonce,butthegraph-structuredapproachallowsustoonlycon-siderasmallfractionofthem.
Inthefollowingsection,wedis-cussvariationstothealgorithmpresentedthusfarthatfurtherreducecomputationormemoryrequirements.
C.
AlgorithmicVariationsThegraph-structuredalgorithmdescribedthusfarusesthefullhill-climbingsearchincludingbacktracking,takingstepsofsinglelevelsperiterationbasedonaheuristicemployingguidinggraphstakingtheformof-levelmoleculargraphs.
Anumberofvariationstothebasicalgorithmmaybemade;wepresentafewhere,butmanyothersarealsopossible.
Al-gorithmsthatuseonevariationoruseafewvariationstogethercanbeusedtosolvethesparsesignalrepresentationproblem.
Dependingonthesizeoftheproblemandtherequirementsoftheapplication,onealgorithmcanbeselectedfromthissuiteofpossiblealgorithms.
1)Hill-ClimbingWithoutBack-Tracking:Hill-climbingsearchalwaysndsthegoalnodebecauseofbacktracking.
Inarstvariation,welimitthesearchtodisallowbacktracking.
Thisreducestheiterationsfromto,butresultsinagreediermethod.
If,onaparticularexample,hill-climbingwithbacktrackingweretoterminateontherstpassdownmoleculargraphsbeforereachingleaves,thenthesameoper-ationwouldbeachievedwhethertheoriginalalgorithmorthevariationwereused.
Inpractice,weoftenobserveterminationontherstdownwardsearch,includingintheexampleseeninSectionII-DandanexamplepresentedbelowinSectionIII-D.
2)ModiedMolecularGraph:Moleculargraphsarestruc-turedsuchthatinhill-climbingwithoutbacktracking,onewrongstepeliminatesmanynearbynodesandpathsbecauseeachnodehasonlytwochildren.
Thegraphmaybemodiedtoincreasethenumberofchildrenpernodetofourforinteriornodesandthreefornodesontheedgesofthegraph,consequentlynotdis-allowingasmanynodesandpathspersearchstep.
Amodiedheuristictogoalongwiththismodiedgraphistousethecoefcientsinleveloftheguidinggraphasbefore,butinsteadofdeterminingwhetherthecenterofmassofthecoefcientmagnitudesisinthelefthalfortherighthalf,determiningwhichquarteritisin.
Iftheleft-mostquadrant,thenthesearchproceedstothenodeinthenextlevelthatistwototheleftofthecurrentnode.
Ifthemiddleleftquadrant,thenthenextnodeisonetotheleftinthenextlevel,andsoon.
Withtheseadditionaledges,searchwithoutbacktrackingislessgreedywithnoadditionalcost,sincecalculatingthismodiedheuristicisnomorecostlythancalculatingtheoriginalheuristic.
3)ModiedGuidingGraphandLargerSteps:Theguidinggraphneednotbea-levelmoleculargraph;forexample,thegraphmaybethinnedandincludethetopnode,nodesinlevel,andnodesinafewintermediatelevelsratherthanallinterme-diatelevels,furtherreducingthenumberofatomsin.
Theseatomsaresufcientforcalculatingtheheuristicandstoppingcondition.
Also,searchesmaytakelargerstepsthanmovingguidinggraphsdownjustonelevelperiteration.
4)RemovalofStoppedMolecules:Thegraph-structuredalgorithmreducesthenumberofatomspermoleculefromto,butdoesnothingtoreducethenumberofmolecules.
Afurthervariationtothehill-climbingsearchwithoutbacktrackingmaybeintroducedthatreducestheaverage-casedependenceofthenumberofatomson.
Itisobservedthat,despiteinteractionsamongcontributionsfromdifferentmolecules,oncethesearchonaparticularmoleculestopsitdoesnotrestartingeneral,butmayoccasionallyrestartafterafewiterations.
Itisthusnaturaltoconsiderxingthecontributionfromamoleculeuponndingitscoefcients.
Inthealgorithm,thisimpliesthatoncethestoppingcriterionismetatmolecule,thesignalisupdatedtobe,andisremovedfrom,therebyreducingthenumberofatomsin.
Weperformtheremovalsomeiterationsafterthestoppingcriterionismetandmaintainedtoallowforapossiblerestart.
Thisvariation,thoughdistinct,hassomesimilaritytomatchingpursuit.
D.
JointAnisotropyCharacterizationandImageFormationTheproblemofjointanisotropycharacterizationandimageformationinwide-angleSARtakestheproblemofcharacter-izinganisotropyofasinglepoint-scattererseeninSectionIIandextendsittodoingsoforallpointsinthegroundpatch.
Inotherwords,whereasstandardimageformationattemptstore-coverassumingnodependenceon,weaimtorecover.
Theobservationmodelfrommorethanonepointisasuper-positionoftermslike(3)(5)Theobservationmodel(5)lendsitselftoanovercompleteex-pansionoftheform(6)inasimilarmannertothesinglepoint-scatterercase.
Herethedictionaryisnaturallydecomposedintomolecules,witheachmoleculecorrespondingtoadifferentspatiallocation.
Wecanthususethemethodsdescribedaboveforjointanisotropycharacterizationandimageformation[24].
Whenperformingjointanisotropycharacterizationandimageformation,agridofpixelsintheimagetoberecon-structedorpointsofinterestidentiedthroughpreprocessingmaybeusedasthespatiallocations.
Wenowpresentanexamplewithspatiallocationsinavebyvegrid,withrowsandcolumnsspacedonemeterapart.
UnlikeSectionII-DwhichusesXPatchdata,thesyntheticdatainthisexampleismatchedtothedictionaryforillustrativepurposes.
Thisexamplehasaspectanglesequallyspacedovera110aperture.
Fig.
7showsthescatteringmagnitudeateachofthe25spatiallocationsarrangedasinanimage;veoftheVARSHNEYetal.
:SPARSEREPRESENTATIONINSTRUCTUREDDICTIONARIES3555Fig.
7.
Scatteringmagnitudeateachspatiallocation.
Fig.
8.
Phasehistorymeasurementmagnitude.
Fig.
9.
Searchpathsofbasicalgorithmformoleculardictionaries.
spatiallocationscontainboxcar-shapedscatteringandtheothertwentydonothavescatterers.
Thecoherentsumofthescatterersisthephasehistorymeasurement,plottedinFig.
8foronefrequency.
Werecoverasignalrepresentationfromthephasehistorymeasurementsusingthebasicalgorithmformoleculardictio-narieswithguidinggraphsofsizeandboxcar-shapedatoms.
ThesearchpathsforthedifferentlocationsareshowninFig.
9.
Theovercompletedictionaryfor,has322000atoms.
Inthesolutionofthesparsesignalrepresenta-tionproblem,contributionscomefromexactlytheveatomsFig.
10.
Backhoe-loaderexample.
(a)Illustrationofthescene;L=75spatiallocationsofinterestshadedaccordingto(b)maximummagnitude,(c)centerangleofanisotropy(degrees),and(d)angularextentofanisotropy(degrees)insolution.
(e),(f)Aspect-dependentscatteringsolutionfortwospatiallocations.
usedtogeneratethesyntheticdata;thecoefcientvaluesarealsorecovered.
IfthesolutionweretobeoverlaidonFig.
7andFig.
8,itwouldnotbedistinguishable.
Lookingatthesearchpaths,despitenotcontainingscatterers,acoupleofmoleculesinitiallyiteratenonetheless,butintheendcorrectlygiveallzerocoefcients.
Thiseffectisaresultoftheinteractionbetweendif-ferentmolecules.
Thealgorithmoperatescorrectlyonthissyn-theticexample;alargerexampleonXPatchdataisgivenlaterandothersmaybefoundin[24]and[25].
E.
ApproachestoWide-AngleSARandaRealisticExampleToconcludethissection,alarge,realisticexamplewithXPatchdataispresented.
Thescenebeingimagedcontainsabackhoe-loader,illustratedinFig.
10(a)[26];measurementsaretakenatequallyspacedanglesoveranaperturerangingfromto100.
spatiallocationsareiden-tiedfromacompositesubapertureimageusingthemethodof[27],forwhichanisotropyisthenjointlycharacterized.
Thefulldictionaryforthisexamplehas89108325atoms.
Weapplythegraph-structuredalgorithmwithallofthevariationslistedinSectionIII-Ctotheproblemandobtain75functionsofaspectangle.
ThemagnitudesoftwoofthesefunctionsareplottedinFig.
10(e)andFig.
10(f).
Inordertoprovidespatialvisual-izationofthescatteringbehavior,themagnitude,centerangleofanisotropy,andangularextentofanisotropyforeachofthespatiallocationsisindicatedbytheshadingofthemarkersinFig.
10(b)–(d).
3556IEEETRANSACTIONSONSIGNALPROCESSING,VOL.
56,NO.
8,AUGUST2008Inthemagnitudevisualization,lightgrayissmallmagnitudeandblackishighmagnitude.
Pointscorrespondingtothefrontbucketofthebackhoe-loaderhavehighmagnitude.
Inthevi-sualizationofcenterangle,theleftsideofthefrontbuckethasresponsescloserto(lightgray)andtherightsideofthefrontbuckethasresponsescloserto(black).
Inthean-gularextentvisualization,itcanbeseenthatnarrowandwideanisotropyisdistributed,butthepointsonthefrontbucketwithhighmagnitudealsohavenarrowextent.
Overall,onecannotefromthevisualizationsthatthefrontbucketashesonitstwosidesandtheotherpartsofthebackhoe-loaderhavescatteringwithsmallermagnitudeandwideranisotropy.
Throughjointanisotropycharacterizationandimageforma-tion,weobtainmuchmoreinformationthanasimpleimagewouldprovide,namelyanentiredimensionofaspect-depen-dence.
Thereectivitiesofscattererswithnarrowangularpersistence,whicharelostinFourier-basedimageformation,areobtained.
Theformulationpresentedheresolvesfortheanisotropyofallspatiallocationswithinonesystemofequa-tions,takinginteractionsamongscatteringcentersintoaccount.
Theformulationismoreexiblethanparametricmethodsforanisotropycharacterizationsuchas[28],[29].
Also,solu-tionshavemoredetailinaspectanglethansubaperturemethodssuchas[30]–[33],inwhichthemeasurementsaredividedintosmallersegmentscoveringonlypartsofthewide-angleaper-ture.
Consequently,usingthemethodpresentedhere,angularpersistenceinformationcanbeextractedasinFig.
10(d),whichisnotpossiblefromsubaperturemethods.
Also,sincedatafromthefullwide-angleapertureisusedherethroughout,cross-rangeresolutionisnotreducedasitiswithsubaperturemethods.
IV.
DICTIONARYREFINEMENTInSectionIIandSectionIII,thedictionaryisknownandxed,butthisneednotalwaysbethecase.
Amoreambitiousgoalistondthebestdictionaryundersomecriteriaandanop-timallysparserepresentationjointly.
Theideaoflearningover-completedictionarieshasbeenappliedinthecasethatonehasmanyexamplesofsignals,muchmorethanthenumberofatomsin,andadictionaryistobedeterminedthatisabletomostsparselyrepresentallofthesignals,usuallyforcompres-siontasks[34],[35].
Ininverseproblems,wheretheinterestisinextractingphysicalmeaningfromtheobtainedsparserep-resentationforeachinputsignal,ratherthancompressionofanentiresignalclass,itisofinteresttolookatthebestdictio-naryforeachinputratherthanthebestdictionarytorepresentanentiresetoftrainingsignals.
Atthispoint,onecouldconcludethatadictionarywithisoptimalandstop.
However,wewouldliketoconsiderdictionariesderivedfromaparameter-izedobservationmodelandonlyconsiderparameterizedatoms,notarbitraryatoms.
Inthissection,weproposeanddemonstrateaformulationforjointoptimizationtoachieveasparsecoef-cientvectorandoptimalparametersettingsforadictionarywithparameterizedatomsormolecules.
A.
JointDictionaryandSparseCoefcientOptimizationWebeginwithadictionarywhoseatomsdependonasetofparameters;eachparametermayormaynotbesharedbyatomsormolecules.
Furthermore,weconsidertherelaxationtothesparsesignalrepresentationproblemmentionedinSec-tionII-B[19].
Theoptimizationproblemathandthenistomin-imizethefollowingcostfunction:(7)jointlydeterminingadictionaryandcoefcients.
Tocarryoutthejointminimization,wetakeacoordinatede-scentapproach,alternatelyoptimizingoverthecoefcientsanddictionaryparameters.
Thetwooptimizationsare(8)(9)Theapplicationwillguidetheparticularinitializationfor.
Thenonconvexminimization(8)maybeperformedusingthegraph-structuredalgorithmsofSectionIIandSectionIII,orusingquasi-Newtonoptimization[19].
Theminimization(9)mayberecognizedasnonlinearleast-squares;manytechniquesexistintheliteratureincludingthetrust-regionreectiveNewtonalgorithmthatweuse[36].
Linearinequalityconstraintsontheparametervectormaybehandledwithinthisframework.
Terminationoftheprocedureisuponthechangeinfallingbelowasmallconstant.
B.
CharacterizationofMigratoryScatteringCentersWedemonstratejointdictionaryparameterandsparserepre-sentationoptimizationonthecharacterizationofaphenomenoninwide-angleSARimagingdifferentfromanisotropy.
Certainscatteringmechanismsmigrateasafunctionofaspectangleinwide-angleimaging[37],[38].
Migrationoccurswhenradarsignalsbouncebackfromtheclosestsurfaceofaphysicalob-ject,buttheclosestsurfaceoftheobjectisdifferentfromdif-ferentviewingangles;thephysicalobjectisnotreallymoving,butappearstomoveinthemeasurementdomain.
Byaccountingforthiseffectinsolvingtheinverseproblem,aphysicallymean-ingful,parsimoniousdescriptioncanbeextracted.
Forexample,consideringacircularcylinder,thepointofre-ectiononthesurfaceclosesttotheradarcanbeparameterizedasafunctionofaroundthecenterofthecylinderusingtheradiusofthecylinder.
When,thescattererappearstobeat,whichwedeneas.
Theobservationmodelformigratorypointscatterersis(10)Adictionaryexpansionfortheobservationmodelis(11)Inthisinstance,theatomsareparameterizedbytheradius,andmoreover,allatomsinmoleculeshareacommonradiusVARSHNEYetal.
:SPARSEREPRESENTATIONINSTRUCTUREDDICTIONARIES3557Fig.
11.
Tophatexample.
(a)Aspect-dependentscatteringmeasurement(grayline)andsolution(blackline).
(b)Conventionallyformedimagewithmigrationsolutionoverlaid.
;henceisan-vectorofparameters.
Theinverseproblemistojointlyrecovertheanisotropyandradiusofmigrationofallscatterersinthegroundpatch.
Theradiusisconstrainedtobenonnegative,i.
e.
,.
Mostscatterersarenotmigratory,andthusweinitializewithallze-roes.
Ofteninpractice,thecoefcientvectorretainsitsspar-sitystructureoneveryiterationbecauseevenfor,char-acterizedanisotropymaybeclosetocorrect,oratleasthavethecorrectsupport.
Theproceduremaybeenvisionedassimulta-neouslyinatingballoons.
Asanexample,welookatdatafromXPatchofascenecon-tainingatophatthatexhibitscircularmigratoryscattering.
Intheaperturewithaspectanglesspacedonedegreeapart,thetophatalsohasanisotropy,asshowninFig.
11(a).
Themagnitudesaswellastherealandimaginarypartsofthemeasurementsareshown,asmigratoryscatteringaffectsphase,notmagnitude.
Animageofthesceneformedusingthepolarformatalgorithm,aconventionalmethodbasedontheinverseFouriertransform,isshowninFig.
11(b).
Afteridentifyingthespatiallocationwithlargestmagnitudeintheconventionallyformedimage,thecoordinatedescentde-scribedinthissectionisappliedwith.
Araisedtriangleshapeisusedfortheatoms.
Thesolutionhasradius5.
314me-tersandanisotropyasplottedinFig.
11(a).
Thecircularmi-grationofradius5.
314metersisoverlaidonandmatcheswellwiththeconventionalimageinFig.
11(b).
Coordinatedescenttojointlyoptimizeoverradiusandanisotropyiseffectivewithrealisticdataseenhere,andwithseveralscatterersinascene,see[25].
Byallowingforanonzeroradius,imageformationisnotsimplypixel-basedbutmoreregion-based.
Al-thoughpointscattererscanbeequatedtospatiallocations,ifinformationaboutmigrationisconsidered,thescattererismoreofanobject-levelconstruct.
Wehavelookedatcharacterizingthemigrationofscattererswhenthemigrationiscircularinshape.
Circlesareanimportantsubsetofmigratoryscatteringbecausemanyman-madeobjectscontainscattererswithcircularmigration.
However,anyshapedenedbyaradiusfunctionaroundacenteriseasilyex-pressedintheobservationmodel(12)Underthismodel,isnotconstantacrossallangles,soalengthvectorofparametersisnotsufcient.
Oneoptionistotakeafunctionalformforwithmoredegreesoffreedomthanjustaconstantfunction,suchasapolynomial,andlengthentheparametervector.
Anotheroptionistolocally,i.
e.
,insmallsegmentsof,approximatewithpiecesofcircles[25].
Thephenomenonofmigratoryscattering,whichhasrarelybeenexploredintheliterature,isasourceofinformationthatcanbeminedfordetailsaboutobjectshapeandsize.
V.
SIMULTANEOUSSPARSITYINMULTIPLEDOMAINSIntheprevioussections,weuseanovercompletedictionarytorepresentasignal,assumingthatasparserepresentationex-istsandthenndingit.
Ourassumptioninthosesectionsisthatissparseinthedomainoftheatoms.
Inthissection,revertingtoaknownandxeddictionary,welookatsignalsthataresparseinthedomainofthatknownandxeddictionary,butarealsosparseinoneormoreotherdomains.
Thegoalistodevelopaformulationthatrecoversparsimoniousrepresentations,seman-ticallyinterpretableinthecaseofinverseproblems,makinguseofsparsityinalldomains.
Notethatintheend,solutionswillstillberepresentationsintermsoftheatomsofthedictionary.
A.
AdditionalSparsityTermsForsparsityinthedomainofthedictionary,therelaxationasanobjectivefunctionis(13)Letusassumethatisalsosparseinatransformeddomainandthatthatsparsityistobeexploitedaswell.
Firstnotethattakinganorthonormaltransformationofboththesignalanddictio-narydoesnotchangethecostfunction.
Also,thedictionaryisxed;consequently,wekeepthedatadelitytermasis,andappendadditionalsparsityterms.
(14)Thefunctionsreturnvectorsrelatedtothedomaininwhichsparsityistobefavored.
Forthedomainofthedictionaryatoms,isanidentityoperation.
Fordomainsthataretrans-formationsoftheoriginaldomain,isconstructedasfollows.
Theoperationisthecompositionofthreesimpleropera-tions.
First,sincethecoefcientsthemselveshavenoparticularmeaninguntilpairedwiththeircorrespondingatoms,initiallytakesthecoefcientsthroughtheatoms.
Thereafter,thesecondoperationistransformationtoanotherdomain.
Finally,furtheroperationsinthetransformeddomainmayfollow.
Ifallarelinear,i.
e.
,matrix-vectorproducts,thenthecostfunc-tionmaybeoptimizedusingquasi-Newtonoptimization[19]orthegraph-structuredalgorithmusingquasi-Newtonoptimiza-tionineachiteration.
Aconcreteapplicationgivenbelowcon-structssuch.
B.
ParsimoniousRepresentationRecoveryofGlintAnisotropyScatteringbehaviorknownasglintisproducedbylong,atmetalplatesandisnotmigratory,hasverynarrowanisotropy,andcorrespondstoalinesegmentinthedomainori-entedatthesameangleasthecenterangleoftheanisotropy.
Fig.
12(a)showsaspect-dependentscatteringofglintanisotropyfromXPatchdataandFig.
12(b)showsaconventionallyformed3558IEEETRANSACTIONSONSIGNALPROCESSING,VOL.
56,NO.
8,AUGUST2008Fig.
12.
Glintexample.
(a)Aspect-dependentscatteringmeasurement.
(b)Conventionallyformedimage.
image.
Aparsimoniousrepresentationoughttoexplainscat-teringwithasinglescatteringcenter,notwithacollectionofscattererslocatedonthelinesegment.
Weapplytheformula-tion(14)bothtofavorsparsityamongatomsandtofavorspar-sityalonglines[38].
Tofavorsparsityamongatoms,istheidentity.
Wenowndadomaininwhichsparsityalongalinecanbefavored.
ThenormalparameterspaceoftheHoughtransform,theplane,andimagespace,theplane,arerelatedbythepropertythatasetofpointslyingonthesamelineinimagespacecorrespondstoasetofsinusoidsthatintersectatacommonpointinparameterspace[39].
Thussparsityamongscatterersinindividualcellsachievesthegoalofsparsityamongpointsonaline.
In[40],aHoughspacesparsifyingregularizationapproachisemployedtoenhanceanddetectstraightlinesinpositivereal-valuedimagesbyimposingsparsitywhentakingtheimagedatatotheplane.
Parameterspacecellswithsmallcountsaresuppressedandcellswithlargecountsareenhanced;thus,non-linefeaturesaresuppressedandlinefeaturesareenhancedinimagespace.
Thegoalsinourworkaredifferentandconse-quently,thesparsitytermsareofadifferentavoraswell.
TherangeproledomaininSAR,aone-dimensionalinverseFouriertransformofthephasehistorymeasurementdomain,isequivalenttotheparameterspaceoftheHoughtransform.
Itfollowsthatforsparsityamongscatterersincell,asparsitytermoftheformisused,whereisalinearoperatorthatisacompositionofablock-diagonalversionofthedictionarytobringthecoefcientstothephasehistorydomain,adiscreteFouriertransformoperatortogototherangeproledomain,andaselectionoperatortoselectcell.
Theresultingvectorisoflength.
Favoringsparsityinallrangeprolecells,theoverallsparsitycostfunctionis(15)Theparametersandcontroltheinuenceofthetwospar-sityterms.
When,thecostfunctionreducesto(13).
WesolvetheinverseproblemwithpixelsofinterestidentiedbyhavinglargemagnitudeintheconventionalimageFig.
12(b).
These24pixelsarealongadiagonallinemoreorless.
Themeasurementsareataspectanglesovera19aperturewiththeglintat5.
5.
TABLEILANDMASAFUNCTIONOFTHEPARAMETERSANDLetusdenetwocountsrelatedtothesparsityofthesolutionandlookattheirbehaviorasandarevaried.
Wedeneasthenumberofmoleculesoutofthepossiblethathaveatleastonenonzerocoefcientinthesolution.
Also,isdenedastheaveragenumberofnonzerocoefcientspermoleculeinthosemoleculesthathaveatleastonenonzerocoefcient.
Themaximumpossiblevalueofis,whichis210for.
Wheniszero,isdenedtobezero.
Solutionsareobtainedusingthequasi-Newtonmethodtominimize(15).
ThetwocountsandaregiveninTableIfordifferentvaluesofand.
First,itshouldbenotedthatwhenandgettoolarge,allofthecoefcientsgotozero.
Themainthingtotakenoteofisthatwhen,,i.
e.
,allspatiallocationsprovidecontributionstothesolution,butasincreases,sparsityalongalineisagreaterinuenceandthenumberofcontributingspatiallocationsdecreasestoone.
Spar-sityamongatomsisnotenoughforthesolutiononXPatchdatatobeparsimoniousinthenumberofspatiallocations,sparsityalongalineisalsorequired.
Itcanbeseenthatwhen,39atomsperspatiallo-cationcontribute,notverysparse.
Forlarger,justoneatomperspatiallocationcontributes.
Consideringthebehaviorofandtogether,wenotethatthetwosparsitytermsarefairlyorthogonal;themaineffectofsparsityamongatomsisonthenumberofatomsperspatiallocationandthemaineffectofspar-sityalongalineisonthenumberofspatiallocations,asperthedesignobjective.
Asparseandphysicallyinterpretableapproximationoughttoassignallofthescatteringtotheleafatomat5.
5ofasinglespatiallocation.
SuchasolutionwithonenonzerocoefcientisrecoveredforthepairsmarkedwithanasteriskinTableI.
Throughtheexample,ithasbeenseenthatbothtypesofsparsityarenecessarytorecoverasolutionthatrepresentsthescatteringascomingfromasinglepointandwithverythinanisotropyexplainedbyasingleatom.
Withthisrepresentation,spatialpropertiesabouttheobjectbeingimaged,suchasorien-tationandphysicalextent,maybeinferred.
Althoughthesameobject-levelinferencescouldhavebeenmadewith,inthatcase,suchobjectswouldbeindicatedratherthanone,VARSHNEYetal.
:SPARSEREPRESENTATIONINSTRUCTUREDDICTIONARIES3559Fig.
13.
Coefcientmagnitudesin8-levelguidinggraphassignalgisvariedfromcoarsetone.
whichdoesnotmakephysicalsense.
Pointshavemoremeaningthanjustpixelswithaspect-dependentamplitudes.
VI.
CONCLUSIONWelookedatmethodsofobtainingsparsesignalrepresen-tationsandapproximationsfromovercompletedictionarieswithhierarchicalstructureswithinsubdictionaries,focusingonthecontextofcoherentinverseproblemswithphysicallyinterpretabledictionaryelements.
Wedevelopedaheuristicmethodofsolutionforsuchproblemsthattakesadvantageofthestructurebyrelatingtheproblemtosearchongraphs.
Wealsotookastepbackfromtheclassicsparsesignalrepresen-tationproblemtoconsiderdictionaryrenementaswellasobtainingsolutionssimultaneouslysparseinmultipledomains.
Underdictionaryrenement,acoordinatedescentapproachwasdevelopedtojointlyoptimizeparameterizedatomsandcoefcients,whereasundersimultaneoussparsity,anextendedsparsifyingcostfunctionwasminimized.
Themethodsweredemonstratedonvariousfacetsofwide-angleSAR,butaregeneralenoughtotransfertootherapplicationswithappropriatedictionaries.
IntheSARcon-text,startingfromthesamelow-levelmeasurementsusedbyconventionalimageformationtechniques,wehavetakenastepfartherinsceneunderstandingwhilealsotakingintoaccountphenomenasuchasanisotropythatcauseinaccuraciesinconventionalmethods.
Wehavestartedtomoveawayfromapixelrepresentationtomoreofanobject-levelrepresentationthroughtheuseofaphysicallymeaningfuldictionary.
APPENDIXTwoexperimentalresultsaregivenasempiricalvalidationforthesearchheuristicandstoppingcriteriondescribedinSec-tionII-B.
Weshowthatsolutionsfromsubdictionariesdoinfacthavenonzerocoefcientsforatomsmost'similar'tothesignal,particularlywhenisnotcontainedinthesubdictionary.
Fortheexperiments,themoleculargraphhaslevelsandtheguidinggraphhaslevels.
Keepingtheguidinggraphxedwithinthemoleculargraph,thebehaviorofthesolutionisobservedasthesignalisvaried.
Quasi-Newtonoptimiza-tionisusedtoobtainthesparsesolutioncoefcients.
Intherstexperiment,withresultsinFig.
13,theguidinggraphisxedwithrootattheleft-mostnodeoflevel200inthemoleculargraph.
Thetruesignalisvariedfromcoarsetonesupport.
Intermsofthemoleculargraph,thetruecoefcientisvaried,startingattherootnode,throughallnodesalongtheleftedgeofthegraph,totheleft-mostnodeoflevel400.
Intheplot,therowinthemoleculargraphwhichcontainsisplottedontheFig.
14.
Coefcientmagnitudesin8-levelguidinggraphassignalgisshiftedfromlefttoright.
horizontalaxis.
Themagnitudesofthe36coefcientsinareindicatedbyshading(whiteiszero);eachhorizontalstripisforoneofthecoefcients.
Mostcoefcientsarezeroforallduetosparsity.
Intheregimewheretheguidinggraphisbelowthetruecoefcient,thecoefcientoftheguidinggraphrootnodeisnonzero.
Intheregimewheretheguidinggraphcoversthetruecoefcient,thecorrectcoefcientisnonzero.
Whentheguidinggraphisabovethetruecoefcient,thecoefcientofthebottomleftnode,thenodeinthelastlevelclosesttothetruth,isnonzeroandothersarezero.
Itshouldbenotedthattheinuenceofthenestsignalsdoesnotreachuptomakeanyguidinggraphnodecoefcientsnonzero(aconsequenceofregularization).
IntheexperimentyieldingtheresultsofFig.
14,theguidinggraphisxedwithrootatthecenternodeoflevel200insteadoftheleft-mostnode.
Thetruenodeisvariedfromlefttorightacrossthemoleculargraphatlevel210,threelevelsbelowthebottomoftheguidinggraph.
ThisgureisorganizedinthesamemannerasFig.
13,butthehorizontalaxisindicatesthecolumnofinthemoleculargraph.
Fromtheseresults,rstitisap-parentthatonlycoefcientsinthelastleveloftheguidinggrapharenonzero,reconrmingresultsfromthepreviousexperiment.
Second,itcanbeseenthatwhenthetruthistotheleftoftheguidinggraph,theleft-mostnodeoflevelisnonzero.
Simi-larly,whenthetruthistotheright,therightnodeisnonzero;whenthetruthisunderneaththe8-levelgraph,nodesinthein-teriorofthelastlevelarenonzero.
ACKNOWLEDGMENTXPatchdataprovidedbyR.
Bhalla.
PolarformatalgorithmimplementationprovidedbyR.
L.
Moses.
REFERENCES[1]D.
M.
Malioutov,M.
etin,andA.
S.
Willsky,"Asparsesignalrecon-structionperspectiveforsourcelocalizationwithsensorarrays,"IEEETrans.
SignalProcess.
,vol.
53,no.
8,pp.
3010–3022,Aug.
2005.
[2]J.
-J.
FuchsandB.
Delyon,"MinimumL-normreconstructionfunc-tionforoversampledsignals:Applicationstotime-delayestimation,"IEEETrans.
Inf.
Theory,vol.
46,no.
4,pp.
1666–1673,Jul.
2000.
[3]M.
etin,W.
C.
Karl,andA.
S.
Willsky,"Feature-preservingregular-izationmethodforcomplex-valuedinverseproblemswithapplicationtocoherentimaging,"Opt.
Eng.
,vol.
45,no.
1,p.
017003,Jan.
2006.
[4]I.
F.
GorodnitskyandB.
D.
Rao,"SparsesignalreconstructionfromlimiteddatausingFOCUSS:Are-weightedminimumnormalgo-rithm,"IEEETrans.
SignalProcess.
,vol.
48,no.
3,pp.
600–616,Mar.
1997.
[5]B.
D.
JeffsandM.
Gunsay,"Restorationofblurredstareldimagesbymaximallysparseoptimization,"IEEETrans.
ImageProcess.
,vol.
2,no.
2,pp.
202–211,Apr.
1993.
[6]S.
G.
MallatandZ.
Zhang,"Matchingpursuitswithtime-frequencydictionaries,"IEEETrans.
SignalProcess.
,vol.
41,no.
12,pp.
3397–3415,Dec.
1993.
3560IEEETRANSACTIONSONSIGNALPROCESSING,VOL.
56,NO.
8,AUGUST2008[7]S.
S.
Chen,D.
L.
Donoho,andM.
A.
Saunders,"Atomicdecompositionbybasispursuit,"SIAMJ.
Scientif.
Comput.
,vol.
20,no.
1,pp.
33–61,Aug.
1998.
[8]D.
L.
DonohoandM.
Elad,"Optimallysparserepresentationingeneral(nonorthogonal)dictionariesvia`minimization,"Proc.
Nat.
Acad.
Sci.
,vol.
100,no.
5,pp.
2197–2202,Mar.
4,2003.
[9]D.
M.
Malioutov,M.
etin,andA.
S.
Willsky,"Optimalsparserep-resentationsingeneralovercompletebases,"inProc.
IEEEInt.
Conf.
Acoust.
,Speech,SignalProcess.
,Montréal,Canada,May2004,vol.
2,pp.
793–796.
[10]J.
A.
Tropp,"Greedisgood:Algorithmicresultsforsparseapproxi-mation,"IEEETrans.
Inf.
Theory,vol.
50,no.
10,pp.
2231–2242,Oct.
2004.
[11]L.
Daudet,"Sparseandstructureddecompositionsofsignalswiththemolecularmatchingpursuit,"IEEETrans.
AudioSpeechLang.
Process.
,vol.
14,no.
5,pp.
1808–1816,Sep.
2006.
[12]R.
GribonvalandE.
Bacry,"Harmonicdecompositionofaudiosignalswithmatchingpursuit,"IEEETrans.
SignalProcess.
,vol.
51,no.
1,pp.
101–111,Jan.
2003.
[13]L.
GranaiandP.
Vandergheynst,"Sparsedecompositionovermulti-componentredundantdictionaries,"inProc.
IEEEMultimed.
SignalProcess.
Workshop,Siena,Italy,Sep.
2004,pp.
494–497.
[14]A.
ShoaandS.
Shirani,"Treestructuresearchformatchingpursuit,"inProc.
IEEEInt.
Conf.
ImageProcess.
,Genoa,Italy,Sep.
2005,vol.
3,pp.
908–911.
[15]C.
LaandM.
N.
Do,"Signalreconstructionusingsparsetreerepresen-tations,"inProc.
SPIE,Sep.
2005,vol.
5914,p.
591410W.
[16]P.
Jost,P.
Vandergheynst,andP.
Frossard,"Tree-basedpursuit:Algo-rithmandproperties,"IEEETrans.
SignalProcess.
,vol.
54,no.
12,pp.
4685–4697,Dec.
2006.
[17]R.
R.
Coifman,Y.
Meyer,S.
Quake,andM.
V.
Wickerhauser,"Signalprocessingandcompressionwithwavepackets,"inProc.
Int.
Conf.
Wavelets,Marseille,France,May1989.
[18]S.
Jaggi,W.
C.
Karl,S.
Mallat,andA.
S.
Willsky,"Highresolutionpursuitforfeatureextraction,"J.
Appl.
Comp.
Harmon.
Anal.
,vol.
5,pp.
428–449,1998.
[19]M.
etinandW.
C.
Karl,"Feature-enhancedsyntheticapertureradarimageformationbasedonnonquadraticregularization,"IEEETrans.
ImageProcess.
,vol.
10,no.
4,pp.
623–631,Apr.
2001.
[20]D.
C.
Munson,Jr.
,J.
D.
O'Brien,andW.
K.
Jenkins,"Atomographicformulationofspotlight-modesyntheticapertureradar,"Proc.
IEEE,vol.
71,no.
8,pp.
917–925,Aug.
1983.
[21]R.
L.
Moses,L.
C.
Potter,andM.
etin,"WideangleSARimaging,"inProc.
SPIE,Apr.
2004,vol.
5427,pp.
164–175.
[22]J.
B.
Keller,"Geometricaltheoryofdiffraction,"J.
Opt.
Soc.
Amer.
,vol.
52,no.
2,pp.
116–130,Feb.
1962.
[23]F.
G.
Meyer,A.
Z.
Averbuch,andR.
R.
Coifman,"Multilayeredimagerepresentation:Applicationtoimagecompression,"IEEETrans.
ImageProcess.
,vol.
11,no.
9,pp.
1072–1080,Sep.
2002.
[24]K.
R.
Varshney,M.
etin,J.
W.
Fisher,III,andA.
S.
Willsky,"Jointimageformationandanisotropycharacterizationinwide-angleSAR,"inProc.
SPIE,Apr.
2006,vol.
6237,p.
62370D.
[25]K.
R.
Varshney,"Jointanisotropycharacterizationandimageformationinwide-anglesyntheticapertureradar,"Master'sthesis,Mass.
Instit.
Technol.
,Cambridge,2006.
[26]BackhoeDataDomeandVisual-DChallengeProblemAirForceRe-searchLaboratorySensorDataManagementSystem[Online].
Avail-able:https://www.
sdms.
afrl.
af.
mil/main.
php,2004[27]M.
A.
KoetsandR.
L.
Moses,"Featureextractionusingattributedscat-teringcentermodelsonSARimagery,"inProc.
SPIE,Apr.
1999,vol.
3721,pp.
104–115.
[28]L.
C.
PotterandR.
L.
Moses,"AttributedscatteringcentersforSARATR,"IEEETrans.
ImageProcess.
,vol.
6,no.
1,pp.
79–91,Jan.
1997.
[29]L.
C.
Trintinalia,R.
Bhalla,andH.
Ling,"Scatteringcenterparam-eterizationofwide-anglebackscattereddatausingadaptiveGaussianrepresentation,"IEEETrans.
AntennasPropag.
,vol.
45,no.
11,pp.
1664–1668,Nov.
1997.
[30]R.
D.
Chaney,A.
S.
Willsky,andL.
M.
Novak,"Coherentaspect-de-pendentSARimageformation,"inProc.
SPIE,Apr.
1994,vol.
2230,pp.
256–274.
[31]L.
R.
Flake,S.
C.
Ahalt,andA.
K.
Krishnamurthy,"DetectinganisotropicscatteringwithhiddenMarkovmodels,"Inst.
Elect.
Eng.
P.
Radar,Son.
,Nav.
,vol.
144,no.
2,pp.
81–86,Apr.
1997.
[32]A.
J.
Kim,J.
W.
Fisher,III,andA.
S.
Willsky,"Detectionandanal-ysisofanisotropicscatteringinSARdata,"Multidimen.
Syst.
SignalProcess.
,vol.
14,no.
1–3,pp.
49–82,Jan.
2003.
[33]M.
etinandR.
L.
Moses,"SARimagingfrompartial-aperturedatawithfrequency-bandomissions,"inProc.
SPIE,Mar.
2005,vol.
5808,pp.
32–43.
[34]K.
Kreutz-Delgado,J.
F.
Murray,B.
D.
Rao,K.
Engan,T.
-W.
Lee,andT.
J.
Sejnowski,"Dictionarylearningalgorithmsforsparserepresenta-tion,"NeuralComp.
,vol.
15,no.
2,pp.
349–396,Feb.
2003.
[35]M.
Aharon,M.
Elad,andA.
M.
Bruckstein,"Ontheuniquenessofovercompletedictionaries,andapracticalwaytoretrievethem,"LinearAlgebraAppl.
,vol.
416,no.
1,pp.
48–67,Jul.
2006.
[36]T.
F.
ColemanandY.
Li,"AreectiveNewtonmethodforminimizingaquadraticfunctionsubjecttoboundsonsomeofthevariables,"SIAMJ.
Optimiz.
,vol.
6,no.
4,pp.
1040–1058,1996.
[37]R.
Bhalla,A.
M.
Raynal,H.
Ling,J.
Moore,andV.
J.
Velten,"Angulardescriptionfor3Dscatteringcenters,"inProc.
SPIE,Apr.
2006,vol.
6237,p.
623706.
[38]K.
R.
Varshney,M.
etin,J.
W.
Fisher,III,andA.
S.
Willsky,"Wide-angleSARimageformationwithmigratoryscatteringcentersandreg-ularizationinHoughspace,"inProc.
Adapt.
SensorArrayProcess.
Workshop,Lexington,MA,Jun.
2006.
[39]R.
O.
DudaandP.
E.
Hart,"UseoftheHoughtransformationtodetectlinesandcurvesinpictures,"Comm.
ACM,vol.
15,no.
1,pp.
11–15,Jan.
1972.
[40]N.
AggarwalandW.
C.
Karl,"Linedetectioninimagesthroughregu-larizedHoughtransform,"IEEETrans.
ImageProcess.
,vol.
15,no.
3,pp.
582–591,Mar.
2006.
KushR.
Varshney(S'00)wasborninSyracuse,NY,in1982.
HereceivedtheB.
S.
degreeinelectricalandcomputerengineeringwithhonorsfromCornellUni-versity,Ithaca,NY,in2004.
HereceivedtheS.
M.
de-greeinelectricalengineeringandcomputersciencein2006fromtheMassachusettsInstituteofTechnology,Cambridge.
HeisnowpursuingthePh.
D.
degreeattheMass-achusettsInstituteofTechnology.
HeisaNationalScienceFoundationGraduateResearchFellowandaresearchassistantwiththeStochasticSystemsGroupintheLaboratoryforInformationandDecisionSystems.
Hewasavisitingstu-dentwiththeLaboratoiredeMathématiquesAppliquéesauxSystèmesatcoleCentrale,Paris,France,in2006.
HewasaninternwithSunMicrosystemsduring2002–2003andwithSensisCorporationin2001.
Hisresearchinterestsincludestatisticalsignalprocessing,imageprocessing,andmachinelearning.
Mr.
VarshneyisamemberofEtaKappaNuandTauBetaPi,andastudentmemberofSIAM.
Müjdatetin(S'98–M'02)receivedthePh.
D.
de-greefromBostonUniversity,Boston,MA,in2001,inelectricalengineering.
From2001to2005,hewaswiththeLaboratoryforInformationandDecisionSystems,Massachu-settsInstituteofTechnology,Cambridge.
SinceSeptember2005,hehasbeenanAssistantProfessorwithSabancUniversity,˙Istanbul,Turkey.
Hisresearchinterestsincludestatisticalsignalandimageprocessing,inverseproblems,computervision,datafusion,wirelesssensornetworks,biomedicalinformationprocessing,radarimaging,braincomputerinterfaces,andsensorarraysignalprocessing.
Dr.
etinhasservedinvariousorganizationalcapacities,includingSpecialSessionOrganizer,SessionChair,andTechnicalProgramCommitteememberforanumberofconferencesincludingtheIEEEInternationalConferenceonAcoustics,Speech,andSignalProcessing;theSPIEConferenceonAlgorithmsforSyntheticApertureRadarImagery;theIEEEStatisticalSignalProcessingWorkshop;theIEEEInternationalConferenceonImageProcessing;andtheEURASIPEuropeanSignalProcessingConference.
HehasalsoservedastheTechnicalProgramCo-Chairforthe2006IEEETurkishConferenceonSignalProcessingandCommunicationsApplications.
VARSHNEYetal.
:SPARSEREPRESENTATIONINSTRUCTUREDDICTIONARIES3561JohnW.
Fisher,III(M'90)receivedthePh.
D.
de-greeinelectricalandcomputerengineeringfromtheUniversityofFlorida,Gainesville,in1997.
HeiscurrentlyaPrincipalResearchScientistwiththeComputerScienceandArticialIntelligenceLaboratoryandisafliatedwiththeLaboratoryforInformationandDecisionSystems,bothattheMassachusettsInstituteofTechnology(MIT),Cambridge.
PriortojoiningMIT,hewasafliatedwiththeElectronicCommunicationsLaboratory,UniversityofFlorida,from1987to1997,duringwhichtimeheconductedresearchintheareasofultrawidebandradarforgroundandfoliagepenetrationapplications,radarsignalprocessing,andautomatictargetrecognitionalgorithms.
Hiscurrentareaofresearchfocusincludesinformationtheoreticapproachestosignalprocessing,multimodaldatafusion,machinelearning,andcomputervision.
AlanS.
Willsky(S'70–M'73–SM'82–F'86)joinedtheMassachusettsInstituteofTechnology(MIT),Cambridge,in1973.
HeistheEdwinSibleyWebsterProfessorofElec-tricalEngineeringandActingDirectoroftheLabo-ratoryforInformationandDecisionSystems,MIT.
HewasafounderofAlphatech,Inc.
andChiefScien-ticConsultant,aroleinwhichhecontinuesatBAESystemsAdvancedInformationTechnologies.
From1998to2002,heservedontheU.
S.
AirForceSci-enticAdvisoryBoard.
HehasdeliverednumerouskeynoteaddressesandiscoauthorofthetextSignalsandSystems.
Hisresearchinterestsareinthedevelopmentandapplicationofadvancedmethodsofesti-mation,machinelearning,andstatisticalsignalandimageprocessing.
Dr.
Willskyhasreceivedseveralawardsincludingthe1975AmericanAuto-maticControlCouncilDonaldP.
EckmanAward,the1979ASCEAlfredNoblePrize,the1980IEEEBrowderJ.
ThompsonMemorialAward,theIEEEControlSystemsSocietyDistinguishedMemberAwardin1988,the2004IEEEDonaldG.
FinkPrizePaperAward,andDoctoratHonorisCausafromtheUniversitédeRennesin2005.