Generalized Composed Alternating Relaxed Projection Algorithm for Two-Set Feasibility Problem

这是一份关于论文《Generalized Composed Alternating Relaxed Projection Algorithm for Two-Set Feasibility Problem》（用于两集可行性问题的广义组合交替松弛投影算法）的详细技术总结。

1. 研究背景与问题定义

问题定义：
论文研究的是希尔伯特空间 $H$ 中两个非空闭凸集 $X$ 和 $Y$ 的交集可行性问题，即寻找点 $x \in X \cap Y$。这类问题广泛应用于信号处理、图像重建、压缩感知和地震数据处理等领域。

现有方法的局限性：

• 交替投影法 (MAP)：简单但收敛速度可能较慢。
• Douglas-Rachford (DR) 算法：具有较好的理论性质，但在子空间可行性问题中，其固定点序列常表现出明显的螺旋轨迹 (spiraling trajectory)，导致实际收敛缓慢。
• CARPA 算法：近期提出的组合交替松弛投影算法，通过混合 DR 型算子和投影 - 反射校正，显著加速了收敛，但其参数调节能力仍有局限。

2. 方法论：广义组合交替松弛投影算法 (gCARPA)

作者提出了一种新的算法 gCARPA，旨在统一并扩展现有的投影/反射方法，特别是通过引入额外的松弛参数来克服螺旋行为。

核心算法设计

算法通过引入外部平均步长 $\mu$ 和内部松弛参数 $(\gamma, \theta, \eta)$ 来构建迭代过程：

1. 松弛反射算子：
   定义 $X$ 和 $Y$ 上的松弛反射算子：
   $$R^\theta_X = (1-\theta)I + \theta(2P_X - I)$$
   $$R^\eta_Y = (1-\eta)I + \eta(2P_Y - I)$$
   其中 $\theta, \eta \in (0, 1]$。当 $\theta=\eta=1$ 时，退化为标准反射；当 $\theta=1/2$ 时，退化为投影。这提供了在“纯投影”和“纯反射”之间灵活插值的自由度。

2. 迭代格式：
   算法迭代步骤如下：

   • $x_{k+1} = P_X(z_k)$
   • $u_{k+1} = R^\theta_X(z_k)$
   • $y_{k+1} = P_Y(u_{k+1})$
   • $v_{k+1} = R^\eta_Y(u_{k+1})$
   • $z_{k+1} = (1-\mu)z_k + \mu \left[ (1-\gamma)\frac{1}{2}(z_k + v_{k+1}) + \gamma y_{k+1} \right]$

   该格式可以看作是一个松弛的固定点迭代 $z_{k+1} = F^{\mu,\gamma}_{\theta,\eta}(z_k)$，其中算子 $F$ 是 DR 型平均项与投影项的凸组合。

非平稳变体 (ns-gCARPA)

论文还提出了非平稳版本 (ns-gCARPA)，允许参数 $(\gamma_k, \theta_k, \eta_k)$ 随迭代次数变化。通过设计满足可和性条件的参数更新规则（如递减的阻尼步长），证明了该变体的收敛性。这使得算法能够根据局部几何结构自适应调整参数。

3. 主要理论贡献

3.1 全局收敛性

• 证明了在闭凸集且交集非空的假设下，gCARPA 生成的序列弱收敛到 $X \cap Y$ 中的某一点。
• 在有限维空间中，收敛是强收敛。
• 证明了固定点集 $\text{fix}(F^{\mu,\gamma}_{\theta,\eta})$ 恰好等于可行集 $X \cap Y$（当 $\gamma > 0$ 时），解决了纯 DR 型方法固定点可能不在交集内的问题。

3.2 子空间情形的谱分析与线性收敛率

针对 $X, Y$ 为线性子空间的情形，作者利用主角度 (Principal Angles) 和 Friedrichs 角 进行了详细的谱分析：

• 块对角化：在由主角度诱导的正交基下，迭代算子被分解为 $2 \times 2$ 的块对角矩阵。
• 显式特征值：推导了每个主角度平面上的 $2 \times 2$ 块的特征值显式公式。
• 收敛率刻画：线性收敛率由次主导特征值的模 $\xi(A)$ 决定。
• 极小极大参数选择：在对称情形下（$\mu=1, \dim(X)=\dim(Y)$），证明了最坏情况下的收敛率仅由 Friedrichs 角和最大主角度决定。基于此，提出了一种临界阻尼 (Critical Damping) 的解析参数选择策略，通过求解 $\Delta(t)=0$ 来平衡不同角度下的收敛速度，从而获得理论上的最优线性收敛率。

3.3 非平稳变体的收敛证明

利用 Krasnosel'ski˘ı-Mann 迭代理论，证明了当参数序列满足可和性扰动条件时，非平稳算法依然收敛到可行解。

4. 数值实验结果

论文在多种可行性模型上进行了广泛的数值实验：

1. 子空间可行性问题：

   • 理论验证：实验测得的收敛斜率与理论预测的次主导特征值模高度吻合。
   • 性能对比：
     • 在 Friedrichs 角较大（子空间夹角较大）时，gCARPA（特别是经过网格搜索优化参数后）显著优于 CARPA 和 DR。
     • 在角度较小时，gCARPA 通过调整 $\theta, \eta$ 能有效抑制螺旋轨迹，减少迭代次数。
   • 轨迹可视化：展示了 gCARPA 如何通过调整参数将复特征值区域转化为实特征值区域，从而消除螺旋运动，实现更直接的阻尼收敛。

2. 球与切线相交问题 (非线性)：

   • 这是一个具有零角度切点的经典困难问题。
   • 结果显示，非平稳策略 (ns-gCARPA) 在高精度要求下表现最佳。自适应调整 $(\theta_k, \eta_k)$ 能有效缓解接近切点时的收敛停滞（长尾效应），优于任何固定参数方案。

3. 稀疏线性逆问题 (压缩感知)：

   • 在 $l_1$ 范数球与仿射子空间的交集中测试。
   • gCARPA 和 ns-gCARPA 在多个真实感测试案例中表现出鲁棒性。特别是在某些特定几何结构（如 Problem 3）下，gCARPA 比 CARPA 快了近 3 倍。
   • 实验表明，额外的松弛参数 $(\theta, \eta)$ 能够适应不同的传感几何结构，减少 $l_1$ 投影输出中的支持集振荡。

5. 研究意义与结论

• 统一框架：gCARPA 成功地将交替投影 (MAP)、Douglas-Rachford (DR)、CARPA 以及多种松弛反射方法统一在一个框架内。
• 参数灵活性：引入的 $(\theta, \eta)$ 参数提供了控制“螺旋”与“阻尼”平衡的新自由度，解决了 DR 类算法在子空间问题中螺旋轨迹导致的效率低下问题。
• 理论指导实践：论文不仅提供了收敛性证明，还给出了基于谱分析的显式参数选择公式（极小极大策略），为实际应用提供了理论指导。
• 非平稳适应性：证明了参数动态调整（非平稳方案）在处理复杂几何（如切点、非线性约束）时的优越性，增强了算法的鲁棒性。

总结：该论文提出了一种通用且强大的可行性求解算法，通过理论上的谱分析和数值上的自适应策略，显著提升了投影类算法在子空间及非线性可行性问题上的收敛速度和稳定性。