The-Split-Bregman-method-for-L1-regularized-proble

THESPLITBREGMANMETHODFORL1REGULARIZEDPROBLEMSTOMGOLDSTEIN,STANLEYOSHERAbstract.Theclassofl1-regularizedoptimizationproblemshasreceivedmuchattentionre-centlybecauseoftheintroductionof\compressedsensing,whichallowsimagesandsignalstobereconstructedfromsmallamountsofdata.Despitethisrecentattention,manyl1-regularizedprob-lemsstillremaindiculttosolve,orrequiretechniquesthatareveryproblem-specic.Inthispaper,weshowthatBregmaniterationcanbeusedtosolveawidevarietyofconstrainedoptimizationprob-lems.Usingthistechnique,weproposea\SplitBregmanmethod,whichcansolveaverybroadclassofl1-regularizedproblems.WeapplythistechniquetotheROFfunctionalforimagedenoising,andtoacompressedsensingproblemthatarisesinMagneticResonanceImaging.Keywords.ConstrainedOptimization,l1regularization,compressedsensing,totalvariationdenoising.1.Introduction.Thecategoryofl1-regularizedproblemsincludesmanyim-portantproblemsinengineering,computer,andimagingscience.Thegeneralformforsuchproblemsisminuj(u)j+H(u)(1.1)wherej
jdenotesthel1-norm,andbothj(u)jandH(u)areconvexfunctions.Manyimportantproblemsinimagingscience(andothercomputationalareas)canbeposedasl1-regularizedoptimizationproblems.Somecommonexamplesofthisincludethefollowing:\TV/ROFDenoising:minukukBV+2kufk22(1.2)\BasisPursuit/CompressedSensing:minuJ(u)+2kAufk22(1.3)whereJ(u)issomeregularizingfunctional,usuallyintheformofaBVorBesovnorm.TheRudin-Osher-Fatemi(ROF)functional(1.2),despiteitssimpleform,hasprovedtobeverydiculttominimizebyconventionalmethods.Totalvariationbasedimagerestorationwasrstintroducedin[22].Inthatpaper,theauthorsproposetominimizethisenergyusingagradientprojectionmethod.Whilethisapproachissimple,thenon-linearityandpoorconditioningoftheproblemmakethisapproachveryslow.Severalauthorshaveproposedimprovedtime-steppingschemesthatresultinbetterperformance,suchasthosepresentedin[26,15].AmoreecientclassofsolversarethosebasedonNewton'smethod.Onesuchalgorithmwaspresentedin[9],inwhichthepreconditionedconjugategradientmethodisusedtoinverttheHessianateachstep.Asomewhatmoreecientimplementationofasecond-ordermethodwasproposedbyVogelet.al.in[25],whereanalgebraicmultigridpreconditionerisusedtoacceleratethemethod.Still,themostecientsolverfortheROFproblemwasproposedbyDarbonandSigellein[10].Inthiswork,theROFfunctionalwasapproximatedusingananisotropicBVnorm.Itwasshownthat,usingthisformulation,theresultingproblemcouldbesolvedveryquicklyusinggraphcuts[3].1Problemsoftheform(1.3)havereceivedalotofattentionrecentlybecauseoftheintroductionofcompressedsensingtechniques,whichallowhighresolutionimagesandsignalstobereconstructedfromasmallamountofdata[7,6,11].Thisformulationhasbeenshowntobeusefulinmanyareas,includingmedicalimaging[16,17],radar[1],andothersignalprocessingapplications.Compressedsensingisbasedontheideathatasignalcanbereconstructedfromaverysmallnumberofmeasurements,providedthatthesemeasurementsareobtainedinthecorrectbasis.TheparticularapplicationofcompressedsensingwhichwewillfocusonisMRimagereconstruction,or\SparseMRI[16,14].ThegoalofsparseMRIistosolveminuJ(u)suchthatkFufk2=0:Here,frepresentstheso-called\compressedsensingdata,whichconsistsofsamplesoftheFouriertransformoftheunknownimage.FcomprisesasubsetoftherowsofaFouriermatrix,urepresentstheunknownimagethatwewishtoreconstruct,andJ(
)isaproperlychosenl1-regularizationterm.Theunconstrainedformulationforthisproblemwasintroducedin[14],whereaBregmaniterativeapproach[4]wasusedtoobtainsolutionsto\denoisingproblemsoftheformminuJ(u)suchthatkFufk2:(1.4)Becauseofthepresenceofanl1-regularizationterm,optimizationproblemsoftheform(1.4)arestillverydiculttosolve.Severalauthorshaveappliedclassicalopti-mizationschemes,suchasinteriorpointmethods,toproblemsoftheseforms.In[23],CSproblemswerereformulatedasquadraticprogrammingproblemswhichwerethensolvedusingthecode\l1ls,whichisclaimedtobeoneofthemostecientsolversforgeneralcompressedsensingproblems.Anothernotableinterior-pointapproachisthecode\l1-magic,whichformulatesaCSproblemasasecondorderconeprogram,andenforcesinequalityconstraintsusingalogarithmicbarrierpotential[7].InthespecialcasewheretheCSproblemcanbewrittenintheformminujujsuchthatkAufk2(1.5)arelativelynewclassofmethodscanbeusedthatreducetheCSproblemtosetofsimplerproblemsusinglinearization.Therstofthesemethodsisthe\FixedPointContinuationmethod(FPC)introducedin[13]byHale,Yin,andZhang.Thismethodsolvestheunconstrainedproblemminujuj+2kAufk22(1.6)byiterativelyperforminggradientdescentsteps.ByapplyingtheBregmaniterationschemein[21,14],itisalsopossibletosolvetheconstrainedproblem(1.5)usingFPC/Bregman.Thisisdonebyiterativelysolvingtheunconstrainedproblem(1.6),andthenmodifyingthevalueoffusedinthenextiteration.RatherthansolvingtheunconstrainedproblemandthenperformingaBregmanupdateseparately,thesetwostepswereelegantlycombinedintheLinearizedBregmanAlgorithm[30].LinearizedBregmansolvestheproblem(1.5)byiterativelysolvingvk+1=vk+AT(fAuk)uk+1=shrink(vk+1;1=)2fork=1;2;


n:Thealgorithmisterminatedwhenthedenoisingconstraintin(1.5)ismet.Itwasshownin[5,20]that