高维线性收敛优化与信号处理定点迭代算法的加速方法：准牛顿、Broyden与SQUAREM策略

《IEEE Signal Processing Magazine》：Acceleration Methods for Iterative Optimization and Signal Processing Algorithms [Lecture Notes]

　　

高维问题的优化（最小化或最大化）算法可能极其缓慢，特别是在最优点附近。对于主化-最小化（majorization–minimization, MM）和期望最大化（expectation–maximization, EM）算法尤其如此，已知其收敛为线性收敛。在本“Lecture Note”专栏中，研究人员聚焦于这一大类优化算法，并讨论若干可加速其收敛的加速方案。本“Lecture Note”所提出的加速方法也适用于许多其他具有线性收敛的算法。范围：本文有助于使信号处理学生、研究人员和从业者意识到一组有用的简单工具，这些工具可用于加速定点型（fixed-point type）慢收敛算法，此类算法在信号处理理论与实践中的数量丰富。相关性：许多优化和信号处理算法是定点迭代（fixed-point iteration）方案。此类算法可能具有极其缓慢的收敛速度，这使其在实时应用中的使用几乎不可能。本“Lecture Note”所提出的加速方法可用于显著提高这些算法的速度，在某些情况下可提高100倍甚至更多。先决条件：本“Lecture Note”假定具备统计信号处理、矩阵分析和优化技术的基本知识。

高维优化（最小化或最大化）算法在最优点附近可能极慢，主化-最小化（majorization–minimization, MM）和期望最大化（expectation–maximization, EM）等线性收敛算法尤为突出。信号处理中大量算法属于定点迭代（fixed-point iteration）型，收敛慢到难以实时应用。因此，研究人员针对可写为 x^k+1=f(x^k) 的定点迭代，讨论准牛顿（quasi-Newton, QN）和 Cauchy–Barzilai–Borwein（CBB）等加速方案，并指出这些方案也适用于许多其他线性收敛算法。论文发表在《IEEE Signal Processing Magazine》。其意义是显著提高收敛速度，某些情况下达100倍甚至更多，使实时应用可行。

关键技术方法包括：准牛顿（quasi-Newton, QN）加速，以割线方程近似雅可比矩阵（Jacobian matrix）并构造加速迭代；Broyden 更新，使新近似在 Frobenius 范数下最接近旧近似；Anderson 加速，被证明等价于 Broyden QN 的特殊情形；Broyden–Fletcher–Goldfarb–Shanno（BFGS）更新，在 g(x) 为梯度时保持对称正半定 Hessian 近似；Cauchy–Barzilai–Borwein（CBB）与 SQUAREM（square iterative method），假设 J 比例于单位矩阵，采用两步 Cauchy 迭代与步长选择，局部收敛速率为 |λ|² 或 |λ|³。

研究内容与结果可按原文小标题概括如下。

Introduction：研究人员指出一大类迭代算法可解释为定点迭代方案，加速方法利用该迭代并仅要求 f(·) 可微，但不需已知 f(·)；当维数 n 很大时，直接牛顿法因计算与存储 Jacobian 不可行。

Notation and preliminaries：研究人员定义雅可比矩阵 J=df(x)/dx^T，g(x)=f(x)?x，g_k=x^k+1?x^k，并给出一阶 Taylor 近似 x^k+2≈x^k+1+J(x^k+1?x^k)，从而 g_k+1≈Jg_k。

Quasi-Newton approach：该部分讨论基于准牛顿的加速。Zhou–Alexander–Lange method：利用至少两次迭代，采用 x?^k+3=x^k+1?α_k(??I)^?1g(x^k+1) 的加速步，? 为 J 的近似；可通过二分选择 α_k，若目标函数下降则接受加速结果。Broyden method：提出使新近似在满足割线方程的同时最接近旧近似的更新，并给出扩展 q>2 的 H=(J?I)^?1 更新。Anderson method：原始形式为 x?=[x^k+1,…,x^k+q]α，α 解约束二次问题；研究人员证明其与 Broyden 的特定 QN 加速迭代等价，从而给出非线性情形下的 QN 解释。Broyden–Fletcher–Goldfarb–Shanno method：当 g(x) 为代理函数或原目标梯度时，Δ=J?I 为 Hessian，近最优点对称正半定；BFGS 更新保持对称正半定，DFP 更新为其对偶，秩一更新虽对称但不能保证正半定。

Cauchy–Barzilai–Borwein approach：该部分讨论 CBB 型加速。Varadhan–Roland method：即 SQUAREM，假设 (J?I)^?1≈α_kI，采用两步 CBB 迭代，推导出 x?^k+3≈x^k?2α_kg_k+α_k²d_k；α 可由最小二乘解 α₁、α₂ 或 α_3? 等选择，数值模拟中 α_3? 表现更好。Extension to q>2：将 G=[g_k,g_k+1,…] 与 G?=[d_k,d_k+1,…] 用于扩展 α，并可执行更多迭代。Local Convergence Analysis of Square Iterative Method：分析表明 SQUAREM 局部收敛速率为 |λ|²，扩展形式为 |λ|³，且 α<0 是局部收敛的必要充分条件。

Numerical applications：研究人员将加速方案用于三个应用。Pilot sequence design for orthogonal time–frequency space communication：针对正交时频空间（orthogonal time–frequency space, OTFS）通信，导频设计需使自模糊函数（autoambiguity function）近似 thumbtack；问题为受单模约束的四次最小化。原 OPSA 基于 MM，收敛极慢，M=N=31 时需数天。SQUAREM 与 QN 先正交投影到约束集并回溯 α，快速收敛，生成序列的 ASL 约 ?60 dB，而 MM 旁瓣更大；平均运行时间显著短。Phase retrieval：从线性测量幅度恢复复信号，原 PRIME 基于 MM，固定点更新对应 Wirtinger flow；大维度时用 Tr(AA^H) 替代 λ_max(AA^H) 导致收敛慢。对 K=2,000、N=4,000、无噪声高斯测量，SQUAREM 与 QN 快速降低目标，重建误差小于 MM，平均运行时间显著更快。Adaptive range-Doppler radar imaging：迭代自适应方法（iterative adaptive approach, IAA）用于距离-多普勒成像，其固定点迭代可能收敛慢并陷入极限环。将 SQUAREM 用于 IAA 固定点，在 N=50、L=40、三目标无噪声场景中，相同收敛准则下 SQUAREM 比 IAA 快20倍；IAA 可能陷入极限环而未找到全部目标，SQUAREM 找到三个目标并给出噪声更小的图像。

What we have learned：讨论部分指出，信号处理文献中许多算法因收敛过慢而难以实用，大多数属于定点迭代型，可用本“Lecture Note”的简单方法显著加速。研究人员提出两类加速方法，用于可表示为定点迭代的优化和信号处理算法；通过无线通信、相位恢复和自适应雷达三个应用，证明这些方法可提供显著速度增益，使其在实时应用中非常有用，可在分配时间内达到期望性能。结论翻译为：研究人员认为，这些加速方法应在基础信号处理课程以及信号处理从业者的工具箱中占有一席之地。