Optimal Kronecker product approximation of block T

OPTIMALKRONECKERPRODUCTAPPROXIMATIONOFBLOCKTOEPLITZMATRICESJULIEKAMMANDJAMESG.NAGYyAbstract.ThispaperconsiderstheproblemofndingnnmatricesAkandBkthatminimizejjTPAkBkjjF,wheredenotesKroneckerproduct,andTisabandednnblockToeplitzmatrixwithbandednnToeplitzblocks.ItisshownthattheoptimalAkandBkarebandedToeplitzmatrices,andanecientalgorithmforcomputingtheapproximationisprovided.AnimagerestorationproblemfromtheHubbleSpaceTelescopeisusedtoillustratetheeectivenessofanapproximatesvdpreconditionerconstructedfromtheKroneckerproductdecomposition.Keywords.blockToeplitzmatrix,conjugategradientmethod,Kroneckerproduct,imagerestoration,preconditioning,singularvaluedecompositionAMSsubjectclassications:65F20,65F30.1.Introduction.AToeplitzmatrixischaracterizedbythepropertythatitsentriesareconstantoneachdiagonal.ToeplitzandblockToeplitzmatricesarisenaturallyinmanysignalandimageprocessingapplications;see,forexample,Bunch[4]andJain[17]andthereferencestherein.Inimagerestoration[21],forinstance,oneneedstosolvelarge,possiblyill-conditionedlinearsystemsinwhichthecoecientmatrixisabandedblockToeplitzmatrixwithbandedToeplitzblocks(bttb).Iterativealgorithms,suchasconjugategradients(cg),aretypicallyrecommendedforlargebttbsystems.Matrix-vectormultiplicationscanbedoneecientlyusingfastFouriertransforms[14].Inaddition,convergencecanbeacceleratedbyprecondi-tioningwithblockcirculantmatriceswithcirculantblocks(bccb).AcirculantmatrixisaToeplitzmatrixinwhicheachcolumn(row)canbeobtainedbyacircularshiftofthepreviouscolumn(row),andabccbmatrixisanaturalextensionofthisstructuretotwodimensions;c.f.Davis[10].Circulantandbccbapproximationsareusedextensivelyinsignalandimageprocessingapplications,bothindirectmethodswhichsolveproblemsinthe\Fourierdomain[1,17,21],andaspreconditioners[7].TheoptimalcirculantpreconditionerintroducedbyChan[8]ndstheclosestcirculantmatrixintheFrobeniusnorm.ChanandOlkin[9]extendthistotheblockcase;thatis,abccbmatrixCiscomputedtominimizejjTCjjF:bccbapproximationsworkwellforcertainkindsofbttbmatrices[7],especiallyiftheunknownsolutionisalmostperiodic.Ifthisisnotthecase,however,theperformanceofbccbpreconditionerscandegrade[20].Moreover,Serra-CapizzanoandTyrtyshnikov[6]haveshownrecentlythatitmaynotbepossibletoconstructabccbpreconditionerthatresultsinsuperlinearconvergenceofcg.Hereweconsideranalternativeapproach:optimalKroneckerproductapproxi-mations.AKroneckerproductABisdenedasAB=264a11Ba1nB......an1BannB375RaytheonSystemsCompany,Dallas,TX75266(email:[e-mail])yDepartmentofMathematicsandComputerScience,EmoryUniversity,Atlanta,GA30322([e-mail]).12J.KAMMANDJ.NAGYInparticular,weconsidertheproblemofndingmatricesAk,BktominimizejjTsXk=1AkBkjjF;(1.1)whereTisann2n2bandedbttbmatrix,andAk,BkarennbandedToeplitzmatrices.AgeneralapproachforconstructingsuchanoptimalapproximationwasproposedbyVanLoanandPitsianis[25](seealsoPitsianis[23]).Theirapproach,whichwedescribeinmoredetailinSection2,requirescomputingprincipalsingularvaluesandvectorsofann2n2matrixrelatedtoT.AnalternativeapproachforcomputingaKroneckerproductapproximationTABforcertaindeconvolutionproblemswasproposedbyThirumalai[24].AsimilarapproachforbandedbttbmatriceswasconsideredbyNagy[22].AsopposedtothemethodofVanLoanandPitsianis,theschemesdescribedin[22,24]requirecomputingprincipalsingularvaluesandvectorsofanarrayhavingdimensionatmostnn,andthuscanbesubstantiallylessexpensive.Moreover,KammandNagy[20]showhowtheseapproximationscanbeusedtoecientlyconstructapproximatesvdpreconditioners.Numericalexamplesin[20,22,24]indicatethatthismoreecientapproachcanleadtopreconditionersthatperformbetterthanbccbapproximations.However,theoreticalresultsestablishingoptimalityoftheapproximations,suchasinequation(1.1),werenotgiven.Inthispaper,weprovidetheseresults.Inparticular,weshowthatsomemodicationstothemethodproposedin[22,24]areneededtoobtainanapproximationoftheform(1.1).OurtheoreticalresultsleadtoanecientalgorithmforcomputingKroneckerproductapproximationsofbandedbttbmatrices.Thispaperisorganizedasfollows.Somenotationisdened,andabriefreviewofthemethodproposedbyVanLoanandPitsianisisprovidedinSection2.InSection3weshowhowtoexploitthebandedbttbstructuretoobtainanecientschemeforcomputingtermsintheKroneckerproductdecomposition.AnumericalexamplefromimagerestorationisgiveninSection4.2.PreliminariesandNotation.Inthissectionweestablishsomenotationtobeusedthroughoutthepaper,anddescribesomepreviousworkonKroneckerproductapproximations.Tosimplifynotation,weassumeTisannnblockmatrixwithnnblocks.2.1.BandedbttbMatrices.WeassumethatthematrixTisablockbandedToeplitzmatrixwithbandedToeplitzblocks(bttb),soitcanbeuniquelydeterminedbyasinglecolumntwhichcontainsallofthenon-zerovaluesinT;thatis,somecentralcolumn.ItwillbeusefultodeneannnarrayPast=vec(PT),wherethevecoperatortransformsmatricesintovectorsbystackingcolumnsasfollows:A=a1a2an,vec(A)=26664a1a2...an37775:TOPELITZKRONECKERPRODUCTAPPROXIMATION3SupposefurtherthattheentryofPcorrespondingtothediagonalofTisknown1.Forexample,suppos