基于Rademacher测量的相位恢复SAF算法_庄智涛.pdf

第 32 卷第 1 期河南教育学院学报(自然科学版)Vol.32No.12023 年 3 月Journal of Henan Institute of Education(Natural Science Edition)Mar.2023收稿日期:2022-05-27基金项目:河南省高等学校青年骨干教师培养计划项目(2019GGJS100)作者简介:庄智涛(1981),男,山东利津人,华北水利水电大学数学与统计学院副教授,主要研究方向为小波分析。doi:10.3969/j.issn.1007-0834.2023.01.004基于 Rademacher 测量的相位恢复 SAF 算法庄智涛,王芊芊(华北水利水电大学 数学与统计学院,河南 郑州 450046)摘要:研究了在 Rademacher 测量下的相位恢复 SAF 算法。数值实验表明,在给定 m4n 测量值的情况下,SAF算法具有良好的经验成功率和鲁棒性。关键词:相位恢复;SAF 算法;Rademacher 分布;梯度下降法;损失函数;优化中图分类号:O224文献标志码:A文章编号:1007-0834(2023)01-0016-060引言相位恢复是从无相位测量中恢复信号的理论和方法,一般通过优化理论和方法解决,其损失函数具有非凸和非光滑的特点,使得它在各种应用中较难解决。相位恢复问题1-2在信号恢复3、全息成像4、微镜、天文学等领域 5-7有广泛应用。近年来,相位恢复与代数几何、低秩矩阵恢复和压缩感知等学科密切相关,研究主要分为理论研究和算法研究。尽管在相位恢复研究方向的发展中已经取得了许多重要研究成果,但相位恢复在算法方面仍有许多问题有待解决。本文讨论了相位恢复问题,其目的是恢复信号 xRn,x 来自一系列仅限振幅的测量值yi=ai,x,i=1,2,m,其中aiRn,i=1,2,m 是 Rademacher 随机向量,m 是测量的数量。在许多科学和工程领域,由于光学探测器的物理局限性,只能记录信号的大小,不能记录相位信息。尽管其数学形式简单,但研究证明,从傅里叶变换的幅度重建有限维离散信号通常是一个 NP(non-deterministic polynomial)完全问题。到目前为止,人们已经开发了许多算法去解决相位恢复问题8-10。这些算法通常分为两类:凸算法和非凸算法。凸算法通常依赖于“matrix-lifting”技术11,将相位恢复问题提升为低秩矩阵恢复问题12,并通过证明矩阵恢复问题在某些条件下等价于凸优化问题进行凸松弛。尽管凸方法在某些特殊条件下有很好的理论保证能收敛到真解,但对于大规模问题来说,它们往往计算效率低。相比之下,许多非凸算法13不需要提升步骤,直接在较低维度的环境空间中运行,效率更高。早期的非凸算法主要基于交替投影,例如 GERCHBERG R W 14和 FIENUP J R 15提出的算法,但是缺乏理论保证。后来,NETRAPALLI P 等16基于谱初始化(spectral initialization)技术提出了 AltMinPhase 算法研究相位恢复问题,他们证明了该算法在重新采样 O(nlog(3n)个高斯随机测量的情况下线性收敛于真解。这项工作进一步发展了其他几种基于谱初始化的非凸算法。他们的共同想法是,首先使用谱初始化选择一个好的初始估计,然后通过梯度下降求解一个优化模型。两种常用的优化模型是强度流模型minzRd F(z)=1mmj=1(aj,z2-y2j)2,(1)和振幅流模型minzRd F(z)=1mmj=1(aj,z-yj)2。(2)具体而言,CANDES E J 17-19等人在(1)的基础上发展了 Wirtinger Flow(WF)方法20,并证明了 WF 算法可以在 O(nlog n)高斯随机测量下实现线性收敛。最近,CHEN Y X 等通过合并截断,即 Truncated Wirtinger 第 1 期庄智涛,等:基于 Rademacher 测量的相位恢复 SAF 算法17 Flow(TWF)算法21,将结果改进为 O(n)高斯随机测量。BAHMANI S 等提出 PhaseMax 算法22,将相位恢复问题转化为一个线性规划问题而求解。ZHANG H 等通过最小化幅度测量的二次损失开发了一种梯度下降法 Reshaped Wirtinger Flow(RWF)算法23。后来,WANG G 等提出 Truncated Amplitude Flow(TAF)算法24,不仅证明从接近最佳数量的无噪声随机测量数中直接恢复 n 维未知信号 x,而且在噪声环境中也具有接近完美的统计性能。基于(1)的其他方法包括高斯-牛顿法、信赖域方法等。本文基于振幅流将问题(2)转化为经验损失函数,该函数是基于强度的经验损失函数。本文尝试探究随机向量服从 Rademacher 分布,通过谱初始化能否成功实现恢复,并对 WF 算法与Smoothed Amplitude Flow(SAF)算法进行对比。SUN J 等研究损失函数(1)的全局几何结构25,结果表明损失函数 F(z)是在 O(nlog(3n)高斯随机测量下,没有任何虚假的局部极小值。它意味着所有最小值都是直到全局相位和损失函数的目标信号在每个鞍点周围具有负的方向曲率。因此,任何算法可以避免鞍点以大概率收敛到真解。他们也开发了一种信赖域方法寻找具有随机初始化的全局解。为了降低采样复杂度,学者研究的结果表明损失函数(1)和激活函数的组合在 O(n)高斯随机测量下也具有良好的几何结构19。本文的主要部分组织如下:第 1 节详细讨论相位恢复两个算法的损失函数;第 2 节对 SAF 算法研究进行详细说明;第 3 节进行了数值计算,实验证明了 SAF 算法具有良好的经验成功率和鲁棒性。关于本文中使用的符号,粗体大写字母和小写字母,例如 x、z 表示向量,粗体大写字母如 A 表示矩阵,x,y表示向量 x、y 的内积,可由x,y=xTy 计算,x表示欧几里得范数。1相位恢复的损失函数1.1WF 算法设 xRn是预期的目标信号,获得的测量结果是 yi=ai,x,i=1,2,m,其中aiRn,i=1,2,m是 Rademacher 随机向量。对于 x 的恢复,考虑损失函数F(z)=12mmi=1(ai,z2-aTix2)2,其中 yi=aTix,即F(z)=12mmi=1(ai,z2-yi2)2,令 fi(z)=12(ai,z2-yi2)2,可以得到 fi(z)=2(zTaiaTiz-y2i)aiaTiz,从而 F(z)=1mmi=1 fi(z)。1.2SAF 算法基于振幅流模型(2),设 xRn是预期的目标信号。获得的测量结果是yi=ai,x,i=1,2,m,其中aiRn,i=1,2,m 是 Rademacher 随机向量。对于 x 的恢复,考虑损失函数F(z)=12mmi=1aTizaTix()-1()2 aTix2,(3)其中函数(t)为(t)=t,t 12t2+2,t|。(4)为了简单起见,只考虑实数情况下的几何结构,该结构也适用于复数情况。寻找任意 xRn的问题来自具有 Rademacher 测量向量的无相位测量 yi=ai,x,i=1,2,m。考虑其损失函数F(z)=12mmi=1aTizaTix()-1()2 aTix2,18 河南教育学院学报(自然科学版)2023 年其中 yi=aTix,即F(z)=12mmi=1aTizyi()-1()2y2i,令 fi(z)=12aTizyi()-1()2y2i,可得 fi(z)=aTizyi()-1()yiaTizyi()ai,则 fi(z)=sgn(aTiz)(aTiz-yi)ai,aTiz yi(aTiz)322y2i+12-1()aTiz()ai,aTiz yi|,从而 F(z)=1mmi=1 fi(z)。本文对以上两种算法进行比较。SAF 算法很容易实现,因为它不需要像很多其他先进的方法那样对梯度或损失函数进行过多的操作。数值模拟实验表明,在给定 m4n 测量值的实数情况下,SAF 将收敛到全局最优,将来也可以推广应用到复数的情况。2SAF 的算法研究SAF 算法是基于精细的初始化和梯度下降法来最小化这一新的启发式算法而提出的,本节详细介绍了该算法的这两个阶段。为了具体起见,以下分析将集中在实数的情况,需要注意的是,该算法在复数情况下具有相同的优势。2.1初始化由于损失函数是非凸的,因此需要进行精心的初始化以获得全局收敛的良好初始估计。本文采用谱初始化进行比较。初始化方法不是本文的重点,不做过多说明。2.2梯度下降法梯度下降法是最优化算法,常用于机器学习和人工智能中用来递归性地逼近最小偏差,即沿梯度下降的方向求解极小值。该方法用负梯度方向作为搜索方向,梯度下降法越接近目标值,步长越小,前进越慢,可以用于求解非线性方程组。梯度下降法算法的主要步骤如下。Step 1取初始点x0Rn和参数 0,令 k=0;Step 2若gk,算法停止,否则,进入下一步;Step 3取dk=-gk,利用线搜索步长规则产生 k;Step 4令xk+1=xk+kdk,k=k+1,返回第二步。SAF 算法为损失函数引入了光滑性,从而使得目标函数可微,并大大简化了 SAF 模型的收敛性分析,使其不必像其他算法一样对梯度执行额外的操作。该方法基于振幅流法,通过梯度下降法对目标函数进行光滑处理,并细化估计的初始zk,即zk+1=zk-u F(zk),其中 u 是最优步长,F(zk)是损失函数的梯度。以上内容将在算法 1 中详述。3数值实验SAF 算法表明梯度下降法不会陷入局部极小值。该算法在谱初始猜测的情况下具有很好的性能。数值实验使用普通的梯度下降算法zk+1=zk-u F(zk)。本文将相对误差定义为Relative error =dist(zT,x)/x,即算法的性能指标。这里 dist(zT,x)是估计 z 到真解 x 的欧氏距离。dist(zT,x)被定义为 minzT-x。第 1 期庄智涛,等:基于 Rademacher 测量的相位恢复 SAF 算法19 用谱初始猜测最小化 SAF 的损失函数 F(z),如算法 1 所示。算法 1基于相位恢复算法的梯度下降法输入变量测量向量aiRn,i=1,2,m;观测值 yRn;参数;步长 u;误差 0。步骤 1)谱初始猜测 z0Rn;2)对 k=0,1,如果 F(zk),zk+1=zk-u F(zk);3)结束。输出变量向量zT。图 1实数情况中不同算法不同分布下 m/n 的经验成功率Fig.1Empirical success rate of m/n with different algorithms and different distributions in real numbers通过一系列数值实验对两个算法进行比较。这里采用谱初始化用于该 SAF 算法。在数值实验计算中,目标向量 xRn是随机选择的,测量向量ai,i=1,2,m 是由 Rademacher 分布随机生成的。例 1测试 WF 和 SAF 算法分别服从高斯分布和Rademacher 分布的经验成功率。分别对两个算法进行了实验。选择 n=128,最大迭代次数为 T=1 000;测量的数量 m 选择在n,8n内;对于每一个 m,运行50 次实验,计算成功率。成功率定义为成功实验次数与总实验次数的比率。在这里如果相对误差满足dist(zT-x)/x10-5,则认为实验已经成功地重建了一次目标信号。结果如图 1 所示,m/n=4 时 SAF算法的 Rademacher 无相位量测量足以精确恢复。例 2比较 WF 和 SAF 算法分别服从 Rademach-er 分布和高斯分布所需的迭代次数,从而获得相对误差。选择 n=1 000,m=8n;SAF 算法中步长为 u=0.8,WF 算法中步长为 u=0.009;对于 SAF 中的参数,考虑=0.8 的情况。对 WF 和 SAF 采用相同的谱初始化方法,初始猜测是通过 50 次迭代的幂法获得的。运行 50 次实验计算这些算法的平均误差。数值结果表明(表 1),在实数情况下,噪声越大,SAF 算法的误差越小。表 1n=1 000 时不同模型不同分布的误差对比Tab.1Error comparison of different distributions of different models at n=1 000算法噪声/dB10203040WF(对称伯努利)2.732 12.131 41.825 01.419 3WF(高斯)2.478 42.402 11.214 91.033 6SAF(对称伯努利)1.810 31.682 41.496 50.497 6SAF(高斯)1.819 71.633 61.560 40.533 4注:精度为 10-2例 3比较 SAF 与 WF 算法在 Rademacher 分布和高斯分布下的收敛速度。选择 n=128,m=5n。SAF算法中步长 u=0.8,参数=0.8;WF 算法中步长 u=0.009。为了证明 SAF 算法的稳健性,还考虑了噪声数据模型yi=ai,x+i,其中噪声分别为 10 dB、20 dB、30 dB、40 dB。结果如图 2 所示。4结论本文对相位恢复问题的 WF 和 SAF 算法进行比较研究,基于 Rademacher 测量的相位恢复 SAF 算法解决了其非光滑性的特点。数值实验表明,对于服从对称伯努利分布的随机向量,SAF 算法较 WF 算法更快实现精确恢复,在给定 m4n 测量值的情况下,SAF 算法具有良好的经验成功率和鲁棒性。SAF 算法还可能20 河南教育学院学报(自然科学版)2023 年扩展到其他应用方面,例如恢复稀疏性或非负性约束的信号等。图 2WF 和 SAF 算法在 Rademacher 分布和高斯分布情况下的相对误差与迭代次数Fig.2Relative error and number of iterations of the WF and SAF algorithms in case of Rademacher and Gaussian distributions 参 考 文 献1MONDELLI M,MONTANARI A.Fundamental limits of weak retrieval with applications to phase retrievalJ.Conference on Learning Theory,2018,75:1 445-1 4502DHIFALLAH O,THRAMPOULIDIS C,LU Y M.Phase retrieval via linear programming:Fundamental limits and algorithmic improvementsC.Allerton 2017 55th Annual Allerton Conference on Communication,Control,and Computing.IEEE,2017:1 071-1 0773OPPENHEIM A V,LIM J S.The importance of phase in signalsJ.Proceedings of the IEEE,1981,69(5):529-5414季瑾,黄飞,王亮,等.利用数字全息和相位恢复算法实现信息加密J.中国激光,2007,34(10):1 408-1 4125GHODS R,LAN A,GOLDSTEIN T,et al.Linear spectral estimators and an application to phase retrievalJ.International Conference on Ma-第 1 期庄智涛,等:基于 Rademacher 测量的相位恢复 SAF 算法21 chine Learning,2018,80:1 734-1 7436GAO B,SUN Q Y,WANG Y,et al.Phase retrieval from the magnitudes of affine linear measurementsJ.Advances in Applied Mathematics,2018,93:121-1417GAO B,LIU H X,WANG Y.Phase retrieval for sub-Gaussian measurementsJ.Applied and Computational Harmonic Analysis,2021,53:95-1158FOGEL F,WALDSPURGER I,DASPREMONT A.Phase retrieval for imaging problemsJ.Mathematical Programming Computation,2016,8(3):311-3359ELDAR Y C,HAMMEN N,MIXON D G.Recent advances in phase retrieval(lecture notes)J.IEEE Signal Processing Magazine,2016,33(5):158-16210 HYDER R,CAI ZK,ASIF M S.Solving phase retrieval with a learned referenceJ.European Conference on Computer Vision,2020:425-44111 CANDES E J,TAO T.The power of convex relaxation:Near-optimal matrix completionJ.IEEE Transactions on Information Theory,2010,56(5):2 053-2 08012 VASWANI N,NAYER S,ELDAR Y C.Low-rank phase retrievalJ.IEEE Transactions on Signal Processing,2017,65(15):4 059-4 07413 YONEL B,YAZICI B.A deterministic theory for exact non-convex phase retrieval J.IEEE Transactions on Signal Processing,2020,68:4 612-4 62614 GERCHBERG R W.A practical algorithm for the determination of phase from image and diffraction plane pictures J.Optik,1972,35:237-24615 FIENUP J R.Phase retrieval algorithms:A comparisonJ.Applied Optics,1982,21(15):2 758-2 76916 NETRAPALLI P,JAIN P,SANGHAVI S.Phase retrieval using alternating minimizationJ.IEEE Transactions on Signal Processing,2015,26:4 814-4 82617 CANDES E J,STROHMER T,VORONINSKI V.Phase lift:Exact and stable signal retrieval from magnitude measurements via convex program-mingJ.Communications on Pure&Applied Mathematics,2013,66(8):1 241-1 27418 CANDES E J,ELDAR Y C,STROHMER T,et al.Phase retrieval via matrix completionJ.Siam Journal on Imagingences,2015,57(2):199-22519 CANDES E J,LI X D.Solving quadratic equations via Phase lift when there are about as many equations as unknownsJ.Foundations of Compu-tational Mathematics,2014,14(5):1 017-1 02620 CANDES E J,LI X D,SOLTANOLKOTABI M.Phase retrieval via wirtinger flow:Theory and algorithmsJ.IEEE Transactions on Information Theory 2015,61(4):1 985-2 00721 CHEN Y X,CANDES E J.Solving random quadratic systems of equations is nearly as easy as solving linear systemsJ.Advances in Neural In-formation Processing Systems,2015,28:822-88322 BAHMANI S,ROMBERG J.Phase retrieval meets statistical learning theory:A flexible convex relaxationJ.Artificial Intelligence and Statis-tics,2017:252-26023 ZHANG H,ZHOU Y,LIANG Y,et al.A nonconvex approach for phase retrieval:Reshaped wirtinger flow and incremental algorithmsJ.Jour-nal of Machine Learning Research,2017,18:1-3524 WANG G,GIANNAKIS G B,ELDAR Y C.Solving systems of random quadratic equations via truncated amplitude flowJ.IEEE Transactions on Information Theory,2017,64(2):773-79425 SUN J,QU Q,WIGHT J.A geometric analysis of phase retrievalJ.Foundations of Computational Mathematics,2018,18(5):1 131-1 198SAF Algorithm of Phase Retrieval Based on Rademacher MeasurementsZHUANG Zhitao,WANG Qianqian(School of Mathematics and Statistics,North China University of Water Resources and Electric Power,Zhengzhou 450046,China)Abstract:The SAF algorithm of phase retrieval based on Rademacher measurements was investigated.Numerical experiments showed that the SAF algorithm has a good empirical success rate and robustness given the measured value of m4n.Key words:phase retrieval;SAF algorithm;rademacher distribution;gradient descent method;loss function;optimization