Optimization Algorithms on Matrix Manifolds.pdf
- 文档编号:18809852
- 上传时间:2023-11-26
- 格式:PDF
- 页数:237
- 大小:2.04MB
Optimization Algorithms on Matrix Manifolds.pdf
《Optimization Algorithms on Matrix Manifolds.pdf》由会员分享,可在线阅读,更多相关《Optimization Algorithms on Matrix Manifolds.pdf(237页珍藏版)》请在冰点文库上搜索。
00AMSSeptember23,2007OptimizationAlgorithmsonMatrixManifolds00AMSSeptember23,2007OptimizationAlgorithmsonMatrixManifoldsP.-A.AbsilR.MahonyR.SepulchrePRINCETONUNIVERSITYPRESSPRINCETONANDOXFORD00AMSSeptember23,2007Copyrightc?
2008byPrincetonUniversityPressPublishedbyPrincetonUniversityPress41WilliamStreet,Princeton,NewJersey08540IntheUnitedKingdom:
PrincetonUniversityPress3MarketPlace,Woodstock,OxfordshireOX201SYAllRightsReservedLibraryofCongressControlNumber:
2007927538ISBN:
978-0-691-13298-3BritishLibraryCataloging-in-PublicationDataisavailableThisbookhasbeencomposedinComputerModerninLATEXThepublisherwouldliketoacknowledgetheauthorsofthisvolumeforprovidingthecamera-readycopyfromwhichthisbookwasprinted.Printedonacid-freepaper.press.princeton.eduPrintedintheUnitedStatesofAmerica1098765432100AMSSeptember23,2007Toourparents00AMSSeptember23,2007ContentsListofAlgorithmsxiForeword,byPaulVanDoorenxiiiNotationConventionsxv1.Introduction12.MotivationandApplications52.1Acasestudy:
theeigenvalueproblem52.1.1Theeigenvalueproblemasanoptimizationproblem72.1.2Somebenefitsofanoptimizationframework92.2Researchproblems102.2.1Singularvalueproblem102.2.2Matrixapproximations122.2.3Independentcomponentanalysis132.2.4Poseestimationandmotionrecovery142.3Notesandreferences163.MatrixManifolds:
First-OrderGeometry173.1Manifolds183.1.1Definitions:
charts,atlases,manifolds183.1.2Thetopologyofamanifold*203.1.3Howtorecognizeamanifold213.1.4Vectorspacesasmanifolds223.1.5ThemanifoldsRnpandRnp223.1.6Productmanifolds233.2Differentiablefunctions243.2.1Immersionsandsubmersions243.3Embeddedsubmanifolds253.3.1Generaltheory253.3.2TheStiefelmanifold263.4Quotientmanifolds273.4.1Theoryofquotientmanifolds273.4.2Functionsonquotientmanifolds293.4.3TherealprojectivespaceRPn1303.4.4TheGrassmannmanifoldGrass(p,n)303.5Tangentvectorsanddifferentialmaps3200AMSSeptember23,2007viiiCONTENTS3.5.1Tangentvectors333.5.2Tangentvectorstoavectorspace353.5.3Tangentbundle363.5.4Vectorfields363.5.5Tangentvectorsasderivations373.5.6Differentialofamapping383.5.7Tangentvectorstoembeddedsubmanifolds393.5.8Tangentvectorstoquotientmanifolds423.6Riemannianmetric,distance,andgradients453.6.1Riemanniansubmanifolds473.6.2Riemannianquotientmanifolds483.7Notesandreferences514.Line-SearchAlgorithmsonManifolds544.1Retractions544.1.1Retractionsonembeddedsubmanifolds564.1.2Retractionsonquotientmanifolds594.1.3Retractionsandlocalcoordinates*614.2Line-searchmethods624.3Convergenceanalysis634.3.1Convergenceonmanifolds634.3.2Atopologicalcuriosity*644.3.3Convergenceofline-searchmethods654.4Stabilityoffixedpoints664.5Speedofconvergence684.5.1Orderofconvergence684.5.2Rateofconvergenceofline-searchmethods*704.6Rayleighquotientminimizationonthesphere734.6.1Costfunctionandgradientcalculation744.6.2CriticalpointsoftheRayleighquotient744.6.3Armijolinesearch764.6.4Exactlinesearch784.6.5Acceleratedlinesearch:
locallyoptimalconjugategradient784.6.6Linkswiththepowermethodandinverseiteration784.7Refiningeigenvectorestimates804.8BrockettcostfunctionontheStiefelmanifold804.8.1Costfunctionandsearchdirection804.8.2Criticalpoints814.9RayleighquotientminimizationontheGrassmannmanifold834.9.1Costfunctionandgradientcalculation834.9.2Line-searchalgorithm854.10Notesandreferences865.MatrixManifolds:
Second-OrderGeometry915.1NewtonsmethodinRn915.2Affineconnections9300AMSSeptember23,2007CONTENTSix5.3Riemannianconnection965.3.1Symmetricconnections965.3.2DefinitionoftheRiemannianconnection975.3.3RiemannianconnectiononRiemanniansubmanifolds985.3.4Riemannianconnectiononquotientmanifolds1005.4Geodesics,exponentialmapping,andparalleltranslation1015.5RiemannianHessianoperator1045.6Secondcovariantderivative*1085.7Notesandreferences1106.NewtonsMethod1116.1Newtonsmethodonmanifolds1116.2RiemannianNewtonmethodforreal-valuedfunctions1136.3Localconvergence1146.3.1Calculusapproachtolocalconvergenceanalysis1176.4Rayleighquotientalgorithms1186.4.1Rayleighquotientonthesphere1186.4.2RayleighquotientontheGrassmannmanifold1206.4.3Generalizedeigenvalueproblem1216.4.4Thenonsymmetriceigenvalueproblem1256.4.5Newtonwithsubspaceacceleration:
Jacobi-Davidson1266.5AnalysisofRayleighquotientalgorithms1286.5.1Convergenceanalysis1286.5.2Numericalimplementation1296.6Notesandreferences1317.Trust-RegionMethods1367.1Models1377.1.1ModelsinRn1377.1.2ModelsingeneralEuclideanspaces1377.1.3ModelsonRiemannianmanifolds1387.2Trust-regionmethods1407.2.1Trust-regionmethodsinRn1407.2.2Trust-regionmethodsonRiemannianmanifolds1407.3Computingatrust-regionstep1417.3.1Computinganearlyexactsolution1427.3.2ImprovingontheCauchypoint1437.4Convergenceanalysis1457.4.1Globalconvergence1457.4.2Localconvergence1527.4.3Discussion1587.5Applications1597.5.1Checklist1597.5.2Symmetriceigenvaluedecomposition1607.5.3Computinganextremeeigenspace1617.6Notesandreferences1658.AConstellationofSuperlinearAlgorithms16800AMSSeptember23,2007xCONTENTS8.1Vectortransport1688.1.1Vectortransportandaffineconnections1708.1.2Vectortransportbydifferentiatedretraction1728.1.3VectortransportonRiemanniansubmanifolds1748.1.4Vectortransportonquotientmanifolds1748.2ApproximateNewtonmethods1758.2.1Finitedifferenceapproximations1768.2.2Secantmethods1788.3Conjugategradients1808.3.1Application:
Rayleighquotientminimization1838.4Least-squaremethods1848.4.1Gauss-Newtonmethods1868.4.2Levenberg-Marquardtmethods1878.5Notesandreferences188A.ElementsofLinearAlgebra,Topology,andCalculus189A.1Linearalgebra189A.2Topology191A.3Functions193A.4Asymptoticnotation194A.5Derivatives195A.6Taylorsformula198Bibliography201Index22100AMSSeptember23,2007ListofAlgorithms1AcceleratedLineSearch(ALS)632ArmijolinesearchfortheRayleighquotientonSn1763ArmijolinesearchfortheRayleighquotientonGrass(p,n)864GeometricNewtonmethodforvectorfields1125RiemannianNewtonmethodforreal-valuedfunctions1136RiemannianNewtonmethodfortheRayleighquotientonSn11197RiemannianNewtonmethodfortheRayleighquotientonGrass(p,n)1218RiemannianNewtonmethodfortheRayleighquotientonGrass(p,n)1249Jacobi-Davidson12710Riemanniantrust-region(RTR)meta-algorithm14211TruncatedCG(tCG)methodforthetrust-regionsubproblem14412TruncatedCGmethodforthegeneralizedeigenvalueproblem16413GeometricCGmethod18214RiemannianGauss-Newtonmethod18600AMSSeptember23,2007ForewordConstrainedoptimizationisquitewellestablishedasanareaofresearch,andthereexistseveralpowerfultechniquesthataddressgeneralproblemsinthatarea.Inthisbookaspecialclassofconstraintsisconsidered,calledgeometricconstraints,whichexpressthatthesolutionoftheoptimizationproblemliesonamanifold.Thisisarecentareaofresearchthatprovidespowerfulalternativestothemoregeneralconstrainedoptimizationmethods.Classicalconstrainedoptimizationtechniquesworkinanembeddedspacethatcanbeofamuchlargerdimensionthanthatofthemanifold.Optimizationalgorithmsthatworkonthemanifoldhavethereforealowercomplexityandquiteoftenalsohavebetternumericalproperties(see,e.g.,thenumericalintegrationschemesthatpreserveinvariantssuchasenergy).Theauthorsrefertothisasunconstrainedoptimizationinaconstrainedsearchspace.TheideathatonecandescribedifferenceordifferentialequationswhosesolutionliesonamanifoldoriginatedintheworkofBrockett,Flaschka,andRutishauser.Theydescribed,forexample,isospectralflowsthatyieldtime-varyingmatriceswhichareallsimilartoeachotherandeventuallyconvergetodiagonalmatricesoforderedeigenvalues.Theseideasdidnotgetasmuchattentioninthenumericallinearalgebracommunityasintheareaofdynamicalsystemsbecausetheresultingdifferenceanddifferentialequationsdidnotleadimmediatelytoefficientalgorithmicimplementations.AnimportantbooksynthesizingseveraloftheseideasisOptimizationandDynamicalSystems(Springer,1994),byHelmkeandMoore,whichfocusesondynamicalsystemsrelatedtogradientflowsthatconvergeexponentiallytoastationarypointthatisthesolutionofsomeoptimizationproblem.Thecorrespondingdiscrete-timeversionofthisalgorithmwouldthenhavelinearconvergence,whichseldomcomparesfavorablywithstate-of-the-arteigenvaluesolvers.Theformulationofhigher-orderoptimizationmethodsonmanifoldsgrewoutoftheseideas.SomeofthepeoplethatappliedthesetechniquestobasiclinearalgebraproblemsincludeAbsil,Arias,Chu,Dehaene,Edelman,Elden,Gallivan,Helmke,Huper,Lippert,Mahony,Manton,Moore,Sepulchre,Smith,andVanDooren.Itisinterestingtosee,ontheotherhand,thatseveralbasicideasinthisareawerealsoproposedbyLuenbergerandGabayintheoptimizationliteratureintheearly1980s,andthiswithoutanyuseofdynamicalsystems.Inthepresentbooktheauthorsfocusonhigher-ordermethodsandincludeNewton-typealgorithmsforoptimizationonmanifolds.Thisrequires00AMSSeptember23,2007xivFOREWORDalotmoremachinery,whichcannotcurrentlybefoundintextbooks.Themainfocusofthisbookisonoptimizationproblemsrelatedtoinvariantsubspacesofmatrices,butthisissufficientlygeneraltoencompasswellthetwomainaspectsofoptimizationonmanifolds:
theconceptualalgorithmanditsconvergenceanalysisbasedonideasofdifferentialgeometry,andtheefficientnumericalimplementationusingsta
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Optimization Algorithms on Matrix Manifolds