Sparse Signal Recovery using Log-Sum Regularization and Adaptive Smoothing

技术摘要：基于对数和正则化与自适应平滑的稀疏信号恢复

问题陈述
本文探讨了从含噪线性观测中恢复稀疏信号的问题，这是压缩感知中的核心任务。给定真实信号 $x_0 \in \mathbb{R}^N$ 和观测值 $y = Ax_0 + w$，其中 $A$ 为测量矩阵，$w$ 为噪声，目标是重构 $x_0$。虽然 $\ell_1$ 正则化（LASSO）是理想但计算上不可处理的 $\ell_0$ 正则化的标准可行替代方案，但它存在收缩偏差，导致非零幅度被低估并产生假阳性，特别是在测量次数有限的情况下。非凸惩罚项（如对数和惩罚）能提供更接近 $\ell_0$ 正则化的近似，并可能减少这种偏差。然而，这些惩罚项的非凸性往往会在重构算法中引入不稳定性。

方法论
作者提出了一种利用对数和惩罚项的稀疏恢复框架，其定义为 $R_i(x_i; \varepsilon) = \log(|x_i|/\varepsilon + 1)$，其中 $\varepsilon > 0$ 控制平滑度。为解决非凸性引起的不稳定性，本文采用了一种自适应平滑策略。该策略根据近端参数 $\lambda_{prox}$ 动态确定平滑参数 $\varepsilon$，使得 $\varepsilon = \sqrt{\lambda_{prox}} + \Delta\varepsilon$。这一特定选择确保了标量近端算子保持连续，从而避免了通常在 $\varepsilon \leq \sqrt{\lambda_{prox}}$ 时出现的间断。

文中 formulation 并分析了两种算法方法：

1. 近似消息传递（AMP）： 作者推导了一种利用对数和惩罚项连续近端算子的 AMP 算法。此外，他们推导了相应的**状态演化（SE）**递归，以刻画算法在大型系统极限（$N, M \to \infty$ 且 $\alpha = M/N$ 固定）下的动力学行为。SE 递归预测了均方误差（MSE）并识别相变。
2. 交替方向乘子法（ADMM）： 针对有限维重构实现了 ADMM 算法。在含噪设定下，包含一个松弛步骤以提高稳定性。在无噪设定下，通过调度惩罚参数 $\rho_{ADMM}$ 而非使用固定的松弛步骤来维持稳定性。

主要贡献

1. 算法构建： 本文利用源自自适应平滑的连续近端算子，专门针对对数和正则化构建了 AMP 算法。
2. 理论分析： 推导了该 AMP 算法的状态演化（SE）递归，为无噪极限下的最终 MSE 和精确恢复相变提供了理论预测。
3. 实证验证： 作者实现了对数和正则化的 ADMM，并证明其经验性能与 SE 预测一致。具体而言，最小 MSE 及其对正则化参数 $\lambda_{pen}$ 的定性依赖关系与理论定点分析相符。
4. 比较性能： 该研究提供了对数与 $\ell_1$ 正则化的比较分析， delineating 了每种惩罚项更优越的区间。

结果

• 相变（无噪情况）： 在无噪设定下，ADMM 的经验成功边界与 SE 递归预测的相变高度吻合。结果表明，与 $\ell_1$ 最小化相比，对数和惩罚项能以更少的测量次数（更低的临界测量率 $\alpha_c$）实现精确恢复，特别是在低信号密度下。
• 含噪情况性能：
  • AMP： AMP 算法的性能在广泛的正则化参数范围内紧密遵循 SE 预测。
  • ADMM： 虽然 ADMM 并未严格遵循 AMP 轨迹（由于固定与自适应平滑参数的差异），但其最小 MSE 及其对 $\lambda_{pen}$ 的定性依赖关系与 SE 预测相符。
  • 区间依赖性： 比较揭示了基于信号密度（$\rho$）和测量率（$\alpha$）的权衡。对数和正则化主要在低密度（$\rho$）或高测量率（$\alpha$）区间产生更低的最佳最终 MSE。相反，$\ell_1$ 正则化在高密度和低测量率区间仍然更优。作者认为，这可能是因为 $\ell_1$ 的收缩偏差在高密度场景下通过抑制噪声引起的幅度增长，意外地稳定了重构过程。

意义
本文声称，所提出的自适应平滑策略有效缓解了非凸对数和正则化固有的不稳定性，使得 AMP 和 ADMM 的成功应用成为可能。推导出的状态演化作为相变边界和最终重构误差的可靠预测器。这项工作表明，虽然对数和正则化在减少收缩偏差和扩展精确恢复区域方面具有理论优势，但其相对于 $\ell_1$ 正则化的实际优越性取决于具体情境，在稀疏且测量充分的情景中最为有益。该研究为理解压缩感知中非凸惩罚项、算法稳定性与重构性能之间的相互作用建立了基准。