Weighted Riemannian Optimization for Solving Quadratic Equations from Gaussian Magnitude Measurements

这是一份关于论文《Weighted Riemannian Optimization for Solving Quadratic Equations from Gaussian Magnitude Measurements》（基于高斯幅度测量的二次方程求解的加权黎曼优化）的详细技术总结。

1. 研究问题 (Problem)

本文旨在解决**广义相位恢复（Generalized Phase Retrieval）**问题。

• 核心任务：从 $m$ 个无相位（相位丢失）的测量值 $y_k = |\langle a_k, x \rangle|^2$ 中恢复长度为 $n$ 的复信号 $x \in \mathbb{C}^n$。其中 $a_k$ 是已知的测量向量。
• 数学重构：该问题可以通过“提升（Lifting）”技术转化为恢复一个秩为 1 的半正定矩阵 $X = xx^*$ 的线性逆问题：
  $$y_k = \langle a_k a_k^*, X \rangle, \quad k=1, \dots, m$$
  即寻找线性方程组 $\mathcal{A}(X) = y$ 的秩为 1 解，其中 $\mathcal{A}$ 是线性测量算子。
• 现有挑战：
  • 传统的凸优化方法（如 PhaseLift）虽然理论保证好，但计算复杂度高（从 $n$ 增加到 $n^2$）。
  • 现有的非凸优化算法（如 Wirtinger Flow, TWF 和标准的黎曼梯度下降 RGD）虽然计算效率高，但其收敛速度受限于测量算子在流形切空间上的条件数（Condition Number）。
  • 现有算法使用的度量（Metric）导致条件数严格大于 1（例如 RGD 约为 2，WF 约为 4），这意味着即使样本量 $m$ 很大，收敛因子也无法趋近于 0，导致收敛速度较慢。

2. 方法论 (Methodology)

作者提出了一种基于**加权黎曼梯度下降（Weighted Riemannian Gradient Descent, WRGD）**的新框架，核心在于设计了一种新的黎曼度量。

2.1 统一框架

文章首先指出，基于流形的算法（如 Canonical RGD）和基于分解的算法（如 Wirtinger Flow, WF）本质上都是在秩为 1 矩阵流形 $\mathcal{M}_1$ 上的黎曼梯度下降算法，区别仅在于它们使用了不同的**黎曼度量（Riemannian Metric）和重traction（Retraction）**算子。

2.2 新度量的构造

为了加速收敛，作者设计了一个新的加权度量 $\langle \cdot, \cdot \rangle_o$，旨在使测量算子 $\frac{1}{\sqrt{m}}\mathcal{A}$ 在流形切空间上具有**近等距（Near-isometry）**性质。

• 定义：对于切空间 $T_Z\mathcal{M}_1$ 中的任意向量 $W_1, W_2$，新度量定义为测量算子内积的期望：
  $$\langle W_1, W_2 \rangle_o := \mathbb{E}\left[\frac{1}{m}\langle \mathcal{A}(W_1), \mathcal{A}(W_2) \rangle\right] = \langle W_1, W_2 \rangle + \text{tr}(W_1)\text{tr}(W_2)$$
  其中 $\langle \cdot, \cdot \rangle$ 是标准的 Frobenius 内积。
• 效果：在高斯测量模型下，当 $m$ 足够大时，$\frac{1}{m}\|\mathcal{A}(W)\|_2^2 \approx \|W\|_o^2$。这使得算子 $\frac{1}{\sqrt{m}}\mathcal{A}$ 在切空间上的条件数 $\kappa_o$ 趋近于 1。

2.3 算法流程 (TWRGD)

基于新度量，作者提出了**截断加权黎曼梯度下降（Truncated Weighted RGD, TWRGD）**算法：

1. 初始化：使用截断谱方法（Truncated Spectral Method）生成初始矩阵 $Z_0$，确保初始点足够接近真实解。
2. 截断梯度：在每次迭代中，根据当前估计值 $Z_t$ 和测量值 $y$ 对测量算子进行自适应截断（Truncation），剔除异常值，增强鲁棒性。
3. 梯度更新：计算加权黎曼梯度 $\nabla^{(o)}_{\mathcal{M}_1} F(Z_t)$。该梯度涉及一个特定的投影算子 $T^{(o)}_{TZ}$，其形式为 $uu^*W + Wu u^* - \frac{3}{2}uu^*Wuu^*$。
4. 重traction：使用截断 SVD（保留最大奇异值对应的秩 1 矩阵）将更新后的点投影回流形 $\mathcal{M}_1$。

3. 主要贡献 (Key Contributions)

1. 最优度量设计：

   • 推导出了从采样算子 $\mathcal{A}$ 导出的简单且计算高效的黎曼度量 $g$（即上述的 $\langle \cdot, \cdot \rangle_o$）。
   • 证明了在该度量下，测量算子在切空间上具有近等距性，使得条件数 $\kappa_o \to 1$。这是现有算法（条件数 $>1$）无法达到的。

2. 理论保证：

   • 线性收敛：证明了在随机复高斯测量下，TWRGD 算法以截断谱方法初始化后，能以任意小的收缩因子（Contraction Factor）线性收敛到全局最优解。
   • 样本复杂度：证明了算法在 $m = O(n)$ 的样本量下即可实现精确恢复，这是相位恢复问题的最优样本复杂度。
   • 收敛速度突破：理论表明，随着截断参数增大，收缩因子可趋近于 0，从而显著快于 Canonical RGD 和 TWF。

3. 算法实现：

   • 提出了 TWRGD 算法，虽然涉及矩阵迭代，但通过向量更新实现，计算复杂度与向量空间算法（如 WF）相当，无需大规模 SVD 分解。

4. 实验结果 (Results)

作者在噪声-free 环境下进行了数值实验（$n=1000$），对比了 TWRGD、Canonical RGD (TRGD)、TWF 和 TAF 算法：

• 收敛速度：
  • 迭代次数：TWRGD 达到相同精度（MSE < $10^{-3}$）所需的迭代次数远少于 TRGD 和 TWF。
  • 计算时间：TWRGD 的 CPU 运行时间显著优于 TRGD 和 TWF。例如在 $m=10n$ 时，TWRGD 耗时约 0.38 秒，而 TWF 耗时约 8.18 秒。
• 条件数影响：实验验证了 TWRGD 的条件数接近 1，而 TRGD 和 TWF 的条件数始终大于 1，这直接解释了 TWRGD 更快的收敛速度。
• 成功率：当测量数 $m \ge 5n$ 时，TWRGD 能以接近 1 的概率精确恢复信号，表现优于 TWF，与 TRGD 和 TAF 相当或更优。

5. 意义与结论 (Significance)

• 理论突破：本文解决了非凸相位恢复算法中收敛速度受限于度量选择的问题。通过构造特定的加权度量，实现了算子条件的优化，将收敛因子从常数级降低到可任意接近 0 的水平。
• 效率提升：提出的 TWRGD 算法在保持与现有高效算法（如 WF）相同计算复杂度的同时，显著提升了收敛速度和稳定性。
• 通用性：这种基于“期望度量”的设计思路为其他非凸优化问题（如矩阵补全、盲反卷积等）提供了新的优化视角，即通过设计合适的黎曼度量来改善算子的几何性质，从而加速收敛。

总结：该论文通过引入一种基于测量算子期望的加权黎曼度量，成功克服了传统相位恢复算法收敛慢的瓶颈，提出了理论保证强、实验表现优异的 TWRGD 算法，为相位恢复领域提供了新的理论工具和高效算法。