带随机初始化的重塑Wirtinger流用于相位恢复的收敛性分析
《Journal of Computational and Applied Mathematics》:Convergence Analysis of Reshaped Wirtinger Flow with Random Initialization for Phase Retrieval
【字体:
大
中
小
】
时间:2026年10月22日
来源:Journal of Computational and Applied Mathematics 2.4
编辑推荐:
摘要 本文研究了使用重塑 W 流(RWF)算法进行相位恢复的问题,重点关注在随机初始化下,从幅度测量????=|?????,???|,??=1,…,??中恢复目标向量??∈???,其中????∈???是测量向量。对于高斯随机测量,我们证明当m?≥?O(nlog2nlog3m)
摘要 本文研究了使用重塑 W 流(RWF)算法进行相位恢复的问题,重点关注在随机初始化下,从幅度测量????=|?????,???|,??=1,…,??中恢复目标向量??∈???,其中????∈???是测量向量。对于高斯随机测量,我们证明当m?≥?O(nlog2nlog3m)时,具有随机初始化的 RWF 算法能在???(log???+log?(1/??))次迭代内达到?-精度,从而获得近乎最优的样本和计算复杂度。此外,我们表明具有随机初始化的 RWF 算法在加性噪声下保持稳定。数值实验进一步证明了其对初始化随机性的鲁棒性,以及即使在相对较大的步长下也保持稳定。
引言 相位恢复旨在从仅幅度测量中恢复信号??∈???:????=|?????,???|,??=1,…,??,其中??=(??1,…,????)?表示观测到的测量向量,????∈???,对于??=1,…,??,是已知的测量向量。相位恢复问题长期以来被认为是一个基础挑战,在工程中有着深厚的历史根源,特别是在光学成像和衍射分析中。相位恢复问题最早由 Sayre [1]及其同事在 1952 年提出,在 DNA 双螺旋结构的发现中发挥了关键作用。不久之后,在 1953 年,数学家 H. Hauptman [2]及其同事开发了一种算法来解决晶体学中的相位恢复问题,并成功应用于阐明晶体材料中的分子结构。1978 年,Fienup [3]引入了一种从二维图像的傅里叶模中进行相位恢复的算法,该算法纳入了非负性和已知图像支撑集等约束。到 1984 年,已有充分文献记载[4],相位恢复自然地出现在涉及衍射电磁辐射以测定物体内部结构的实验中。大约在本世纪之交,随着光学成像技术的进步,人们对相位恢复重新产生了兴趣[5]。相位恢复在多个领域有着广泛的应用,如光学成像[6]、图像处理[7]、显微镜学[8]、天文观测[9]、X 射线晶体学[5]、微波通信[10]和量子力学[11]。特别是,通过散射介质的成像是复杂光场传播的一个重要工程应用[12],具有在浑浊生物介质中检测细胞的实际用途[13]。相位恢复在测量和光学信息安全[14]中也发挥着作用,包括集成图像压缩和加密[15]。最近,其与深度学习的结合激发了对单帧干涉图相位恢复的兴趣[16]、[17]、[18]、[19],并扩展了如散斑干涉测量[20]等工业应用。
为了应对相位恢复问题,开发了各种算法。用于相位恢复的有效凸优化方法直到 21 世纪才出现。在此之前,主导方法是简单而高效的交替投影法。最早的交替投影算法称为 Gerchberg-Saxton (GS) 算法,由 Gerchberg 和 Saxton 于 1972 年提出[21]。在此基础上,Fienup 及其同事引入了两个著名的变体:基本输入 - 输出 (BIO) 算法[3]和混合输入 - 输出 (HIO) 算法[22]。随后,提出了几种新的基于投影的算法,其中由 Luke 及其同事开发的混合投影 - 反射 (HPR) 算法[23]和松弛平均交替反射 (RAAR) 算法[24]尤为突出。在凸优化方面,著名的算法包括 PhaseLift [25]、PhaseCut [26]等。
最近,Candès 等人[27]引入了具有谱初始化的 W 流 (WF) 算法,并证明仅使用 O(nlog n) 高斯测量即可实现线性收敛,在???(?????2?log?1??)次浮点运算内达到?-精度。WF 算法的思想是通过普通梯度下降求解以下非凸最小二乘估计问题 (2):min??∈???????(??)=14??????∑??=1[(????????)2???2??]2。W 流 (WF) 算法由截断 W 流 (TWF) 算法进一步改进,如 [Chen 和 Candes] 中所提出。具有随机初始化的 WF 算法在高斯设计下的理论依据在 [29] 中提供。最近,Zhang 等人 [Zhang 和 Liang] 引入了一种非光滑但计算可行的损失函数,开发了具有基于梯度更新的重塑 W 流 (RWF) 算法。RWF 算法已被证明在精心设计的初始化下,对于随机高斯测量,只要测量数量 m 是 O(n) 阶,就能实现向全局最优的几何收敛。RWF 的核心思想是通过类梯度算法????+1=????????????(????)来求解以下问题 min??∈???????(??)=12??????∑??=1(∣????????∣?????)2,其中 ?f(z) 表示 f(z) 的广义梯度。当??????????=0 时,相应的梯度分量使用 Fréchet 超微分 [31] 定义,即设为零。设 σ(a) 表示符号函数,特殊情况???(0)=0。更新方向定义如下:?????(??)=1?????∑??=1(∣????????∣?????)????(????????)?????。
谱初始化的显著成功自然地提出了一个重要的问题:精心设计的初始化对于快速收敛是否真正必要?众所周知,普通梯度下降不能从任意点开始,因为这可能导致收敛到不需要的驻点,如鞍点。尽管如此,一种更简单的初始化策略能否避免这些陷阱,同时达到与谱初始化相当的性能?受此问题启发,实践者通常采用随机初始化,它具有明显的优势——模型无关且通常对模型不匹配更鲁棒。因此,这个问题引起了相当大的研究关注。
尽管具有实际应用吸引力,但随机初始化下 RWF 算法的理论理解仍然有限。本文旨在分析使用随机重采样高斯测量的随机初始化 RWF,为这种广泛观察到的现象提供严格的理论论证。一个主要挑战源于符号函数的存在,这使得 ?f(z) 在原点附近不连续且非利普希茨。
如前所述,O(n) 高斯随机测量下 RWF 算法的线性收敛在 [Zhang 和 Liang] 中确立,但该工作严重依赖谱初始化。在本文中,我们证明 O(nlog2nlog3m) 个高斯随机向量足以保证具有随机初始化的 RWF 算法以高概率收敛到目标信号,并在???(log???+log?1??)次迭代内达到?-精度。随机初始化 RWF 的采样和计算复杂度是近乎最优的,至多相差对数因子。与之前工作中常用的谱初始化相比,随机初始化更实用且有效,更好地符合实际应用的需求。我们的实验进一步证明了随机初始化的便捷性和效率。
在我们的分析中,我们严格证明 RWF 算法的收敛经历了一个由两个不同区域表征的相变。在第一阶段,通过将迭代点 zk 分解为信号分量?zk, x?x 及其正交补??????????,??????,我们表明从随机初始化——与目标信号近乎正交——开始,迭代点与真实解之间的角度单调减小。在采样复杂度 O(nlog2nlog3m) 下,此阶段持续 O(log n) 次迭代。在第二阶段,一旦迭代点满足 dist(z, x)?≤?γ(其中 γ?>?0 为某个足够小的常数),RWF 算法向真实值表现出线性收敛速率,如 [Zhang 和 Liang] 所示。主要挑战源于符号和绝对值函数在原点附近引入的不连续性和缺乏利普希茨连续性。为此,在第一阶段我们应用了一种重采样策略,强制迭代序列 zk 和{ai}之间的条件独立性。这种解耦使我们能够以高概率证明,随机初始化的 RWF 算法在整个第一阶段避免了鞍点。
在发展具有保证全局性能的相位恢复问题非凸算法的追求中,Netrapalli 等人[32]提出了一种交替最小化算法,而 Candès 等人[8]、Chen 和 Candes [Chen 和 Candes]、Zhang 等人[33]以及 Cai 等人[34]聚焦于一阶基于梯度的方法。Sun 等人[35]最近的一项研究检查了非凸目标的几何结构并引入了一种二阶信赖域算法。此外,Wei [36]通过经验证明了 Kaczmarz 随机算法的快速收敛。
本文与 [Zhang 和 Liang] 和 [29] 最为相关。与 [Zhang 和 Liang] 不同,我们将 RWF 算法扩展到随机初始化,增强了其在实际工程环境中的适用性。虽然我们借鉴了 [29] 中引理 8 的分析,但我们的方法有所不同,采用了不同的策略来克服绝对值和符号函数带来的重大挑战。尽管如此,我们提供了一个更直观且易懂的框架来理解和分析问题。
我们使用粗体小写字母,例如 a 来表示向量,使用小写字母,例如 a 来表示标量。符号[a]i 表示向量 a 的第 i 个分量。对于??∈?,σ(a) 表示 a 的符号,特殊情况???(0)=0。单位矩阵记为 In,?????1 表示???中的欧几里得球面。向量 ei 表示标准基向量,其第 i 个分量为 1,所有其他分量为 0。除非另有说明,否则我们采用约定‖·‖表示‖·‖2。考虑可能存在的全局符号差异,两个向量之间的欧几里得距离定义为 d??????????(??,??)=min?{∥?????∥,∥??+??∥}。我们使用符号?(分别地,?)表示:如果 x???y(分别地,x???y),则存在常数 c?>?0 使得 x?≥?cy(分别地,x?≤?cy)。
本文结构如下。第 2 节介绍了提出的算法并给出了主要理论结果。第 3 节提供了定理 2.1 的证明。第 4 节展示了验证我们理论发现的数值实验,并进行了详细讨论。第 5 节总结全文并进行进一步讨论。第 6 节涵盖了必要的预备知识和基础概念。最后,第 7 节和第 8 节提供了主要结果的完整技术证明,第 9 节给出了噪声情况下的理论分析和证明。
章节片段 算法与主要结果 在本工作中,我们考虑批处理设置下的算法。我们将采样向量{????}????=1及其对应的观测值 yi 划分为 K 个不相交块{????,????}??∈???,对于??=1,…,??,每块大小大致相等,并在这些块上循环执行梯度下降。每块的样本量记为???,因此??=??????。完整流程总结于算法 1 中。与 [Zhang 和 Liang] 中使用谱初始化的 RWF 算法不同,我们的方法采用随机
定理 2.1 的证明 由于高斯分布的旋转不变性,在整个分析过程中,我们不失一般性地假设??=??1且??∥0=[??0]1>0。对于每个 zk,我们分解????=??∥?????1+??⊥??,其中??∥??=?????,??1?。此外,我们定义????=??∥??,????=∥??⊥??∥且????=∥????∥。要证明 zk 收敛到 x,只需证明αk 收敛到 1 且βk 收敛到 0。为此,观察到如果存在某个????∈?+使得|????????1|≤?12???且??????≤12???,对于某个足够小的常数γ?>?0,则 d??????????(??????,??)?≤∥???????????∥≤
数值实验 在本节中,我们展示了一些数值实验,以验证具有随机初始化的重采样 RWF 算法的有效性和鲁棒性,并与 WF、IRWF、TWF 和 TAF 进行比较。选择这些方法是因为它们在解决相位恢复问题中使用广泛且性能强大。在这里,值得强调的是,我们的重采样 RWF 和 WF 使用了随机初始化,而 IRWF、TWF 和 TAF 采用了谱初始化。在所有
结论 本文研究了重塑 W 流 (RWF) 算法在随机初始化下的收敛性质。我们的理论分析表明,RWF 能在???(log???+log?(1/??))次迭代内达到?-精度,前提是样本复杂度满足m?≥?O(nlog2nlog3m)。数值实验验证了我们的理论结果,并进一步表明,在大约 O(log n) 次迭代后,算法进入目标向量 x 周围的一个足够小的邻域。
预备知识 引理 6.1 假设????~???(??,????)是一个高斯随机向量。对于任何固定的x,??∈???,假设??∈(0,??2)是 x 和 z 之间的角度,则有??????~???(??,????)????(????????)∣????????|?????=(1?2?????)???+2?sin????????∥??∥?∥??∥。证明 由于齐次性,我们假设??,??∈?????1。不失一般性,我们假设??=??1且??=(cos???,sin???,0,…,0)?。因此,我们得到??????~???(??,????)????(????????)∣????????|?????=??????~???(??,????)????(????,1)?|????,1?cos???+????,2?sin???|?????。设????,1=???cos???且????,2=???sin???,其中??∈(0,+∞),α?∈?(0, 2π)。显然,在上述方程中第 3
引理 3.1 的证明 考虑更新规则????+1=????????????(????),其中?????(????)=1???????∑??=1(|????????????|?|??????????|)????(??????????)?????。根据引理 6.1,有?????(??):=??????~???(??,????)?????(??)=???(1?2?????)????2?sin????????∥??∥,其中??∈[0,??2]是 x 和 z 之间的角度。因此,????+1=????????????(????)+???(?????(????)??????(????))?____?____?:=???(????)。定义 (3) 意味着以下分解:??∥??=?????,???且??⊥??=??????????,??????。结合 (25) 和 (26) 得到??∥??+1=??∥????????∥??+???(1?2???????)+???2?sin??????????∥??∥????∥+?????1?(????)??⊥??+1=??⊥????????⊥??+???2?sin??????????⊥??∥????∥+?????⊥?(????),其中??1?(????)=??∥???1????∑?????=1???????????????,1?_____?_____?:=msub
引理 3.2 的证明 我们首先证明∥????+1∥≤2。为了方便,记???(????,????):=???????????2??+??2??+arcsin?????√??2??+??2??(i)=12?sin?2?????+????(ii)≤??2,其中 (i) 来自定义????=arctan?(????/????),且 (ii) 成立是因为????∈[0,??2]。因此,回顾 (13a),有????+1=(1???+???????)?????+2?????????(????,????)≤(1???+??|??????|)?????+??,其中|?????|≤???log?????130 对于足够小的常数 c?>?0 成立,这是由于引理 3.1。只要????<11?|?????|,就有????+1<11?|?????|≤65。对于βk,采用相同的方法,由 (13b) 可得????+1=(1???+???????)?????+2????????2????2??+??2??≤(1???+??
定理 2.2 的证明 证明 证明与无噪情况类似,因此我们只强调不同之处。
在含噪测量模型(7)下,RWF迭代可以写为$\mathbf{z}_{k+1}=\mathbf{z}_{k}-\tilde{\mu}_{m}\sum_{i\in\mathcal{I}_{t}}\left(|\mathbf{a}_{i}^{\top}\mathbf{z}_{k}|-y'_{i}\right)\sigma\left(\mathbf{a}_{i}^{\top}\mathbf{z}_{k}\right)\mathbf{a}_{i}$。设$\nabla f(z)$表示(5)中的无噪梯度,并定义噪声项$\Delta(z)=\tilde{\mu}_{m}\sum_{i\in\mathcal{I}_{t}}\eta_{i}\sigma\left(\mathbf{a}_{i}^{\top}z\right)\mathbf{a}_{i}$。则(45)可以重写为$\mathbf{z}_{k+1}=\mathbf{z}_{k}-\mu\nabla f\left(\mathbf{z}_{k}\right)+\mu\Delta\left(\mathbf{z}_{k}\right)$。不失一般性,与无噪情形相同,我们假设$\mathbf{x}=\mathbf{e}_{1}$。将$\Delta(z_{k})$分解为平行分量和垂直分量:$\Delta_{\parallel}(z_{k})=$ Linbin Li | Haiyang Peng | Yong Xia | Meng Huang,北京航空航天大学数学与系统科学学院,中国北京。