技术摘要：通过截断 $\ell_1-\ell_2$ 最小化结合先验支撑信息实现 $k$-稀疏信号恢复

问题陈述

本文研究了从少量线性测量值 $y = Ax$ 中恢复 $k$-稀疏信号 $x \in \mathbb{R}^n$ 的问题，其中 $A \in \mathbb{R}^{m \times n}$ 且 $m \ll n$。虽然理想的重构涉及最小化 $\ell_0$ 范数（这是一个 NP-hard 问题），但作者将重点放在非凸的 $\ell_1-\ell_2$ 最小化模型上。至关重要的是，本研究引入了先验支撑信息：假设存在一个索引子集 $T^C \subseteq [n]$，已知属于信号的支撑集（即 $T^C \subseteq \text{supp}(x)$）。研究目标是确定如何利用这些先验知识来改进相比于传统 $\ell_1-\ell_2$ 模型的恢复保证。

方法论

作者提出了截断 $\ell_1-\ell_2$ 最小化模型：
$$\arg \min_{x \in \mathbb{R}^n} \|x_T\|_1 - \|x_T\|_2 \quad \text{subject to} \quad Ax = y$$
其中 $T = [n] \setminus T^C$ 是已知非活跃的索引集合，$x_T$ 表示将 $T^C$ 中的元素置为零的向量。这种形式有效地移除了对已知活跃索引的惩罚，使得优化问题不再那么受限。

理论分析区分了局部恢复（即真实信号是一个严格局部极小值点）和全局恢复（即真实信号是唯一的全局极小值点）。作者采用了以下方法：

1. 空空间性质 (NSP)： 基于矩阵 $A$ 的核（kernel）推导充要条件。
2. 限制等距性质 (RIP)： 将 NSP 条件转化为可验证的 RIP 界限。
3. 差分凸 (DCA) 算法： 设计了一个用于求解该非凸问题的数值求解器。目标函数被重新表述为 $g(x) - h(x)$，其中 $g(x) = \|x_T\|_1 + \iota_C(x)$ 且 $h(x) = \|x_T\|_2$。该算法在每次迭代中对 $h(x)$ 进行线性化，并通过具有闭式近端算子（软阈值和正交投影）的原始-对偶分裂法求解凸子问题。

核心贡献

本文做出了四个方面的贡献：

1. 尖锐的理论条件：

   • 确立了固定稀疏信号通过截断局部最小化进行恢复的充要条件（定理 2.4）。
   • 推导了满足先验信息的所有 $k$-稀疏信号恢复的充要条件，涵盖了局部最小化（定理 2.10）和全局最小化（定理 2.18）。
   • 证明了这些条件比传统的 $\ell_1-\ell_2$ 模型（即 $T^C = \emptyset$）以及先前文献中相关的截断 $\ell_1-\ell_2$ 模型更为宽松。

2. 可验证且严格的保证：

   • 推导了一个充分的 RIP 条件：$\delta_{2k} < \frac{t+1}{2k-t-1}$，其中 $t = |T^C|$。随着先验信息量（$t$）的增加，该界限单调改善。
   • 分析了边界情况 $t = k-1$，表明恢复过程简化为一个简单的秩条件。
   • 提供了一个显式的矩阵示例（定理 2.26），证明这种改进是严格的：存在某些矩阵，其截断模型可以恢复所有容许信号，而传统模型则无法恢复。

3. 算法设计：

   • 提出了一个基于 DCA 的算法（算法 1），并辅以高效的原始-对偶子程序（算法 2）来解决非凸问题。
   • 为涉及的所有近端算子提供了闭式表达式，确保了计算效率。

4. 数值验证：

   • 在高斯随机测量（$n=256, m=64$）下进行了实验，将所提模型与传统的 $\ell_1-\ell_2$ 模型进行了对比。

结果

数值实验得出以下发现：

• 性能增益： 截断模型始终优于传统模型。对于 $n=256, m=64$ 且稀疏度 $k=22$ 的情况，当提供 $|T^C| = 8$ 个已知活跃索引时，成功率从 38%（传统模型）提升至 89%。
• 测量效率： 为了达到 90% 的成功率（当 $k=18$ 时），截断模型比传统模型大约需要减少 14 次测量（约减少 20% 的采样预算）。
• 鲁棒性： 即使在先验信息不准确（例如包含 50% 的错误索引）以及存在加性高斯噪声的情况下，这种优势依然存在。在噪声环境下，截断模型实现了更低的媒介相对重构误差（例如，在 40 dB SNR 下，当 $|T^C|=8$ 时，性能提升了 42%）。
• 收敛性： DCA 算法收敛迅速，通常仅需几次外层迭代（3–4 次）即可达到平稳状态。

意义与主张

本文声称，当存在部分支撑信息时，所提出的截断 $\ell_1-\ell_2$ 模型相比于传统方法提供了严格的理论和数值改进。

• 理论意义： 推导出的条件完善了现有文献，表明先验知识以可量化的方式放宽了对测量矩阵（特别是 RIP 常数）的要求。作者明确证明这种改进不仅是数值上的，更是结构性的，这由一个传统模型失败而截断模型成功的反例得到了证实。
• 实际意义： 结果表明，在可以使用不完美先验支撑检测启发式方法的应用场景中，将此类信息纳入 $\ell_1-\ell_2$ 框架可以显著增强恢复的可靠性并降低所需的采样率。

作者指出，推导出的 RIP 界限可能并非最优，未来的工作应致力于研究噪声和近似稀疏信号的稳定恢复，以及选择先验集 $T^C$ 的自适应策略。