SOLVING SYSTEMS OF QUADRATIC EQUATIONS VIA EXPONENTIAL-TYPE GRADIENT DESCENT ALGORITHM

作     者：Meng Huang Zhiqiang Xu Meng Huang;Zhiqiang Xu

作者机构：LSECInst.Comp.Math.Academy of Mathematics and System ScienceChinese Academy of SciencesBeijing 100190China School of Mathematical SciencesUniversity of Chinese Academy of SciencesBeijing 100049China 

出 版 物：《Journal of Computational Mathematics》 (计算数学（英文）)

年 卷 期：2020年第38卷第4期

页      面：638-660页

核心收录：

学科分类：07[理学] 0714[理学-统计学（可授理学、经济学学位）] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：The research of the second author was supported by NSFC grant(91630203,11688101) by Youth Innovation Promotion Association CAS,Beijing Natural Science Foundation(Z180002) by National Basic Research Program of China(973 Program 2015CB856000) 

主　　题：Low-rank matrix recovery Non-convex optimization Phase retrieval 

摘      要：We consider the rank minimization problem from quadratic measurements,i.e.,recovering a rank r matrix X 2 Rn×r from m scalar measurements yi=ai XX⊤ai,ai 2 Rn,i=1,...,*** problem arises in a variety of applications such as quadratic regression and quantum state *** present a novel algorithm,which is termed exponential-type gradient descent algorithm,to minimize a non-convex objective function f(U)=14m Pm i=1(yi−a⊤i UU⊤ai)*** algorithm starts with a careful initialization,and then refines this initial guess by iteratively applying exponential-type gradient ***,we can obtain a good initial guess of X as long as the number of Gaussian random measurements is O(nr),and our iteration algorithm can converge linearly to the true X(up to an orthogonal matrix)with m=O(nr log(cr))Gaussian random measurements。