规则化正交匹配追踪(ROMP)信号重构算法

资 源 简 介

本项目实现了一种高效的压缩感知（Compressed Sensing）信号重构算法——规则化正交匹配追踪算法（Regularized Orthogonal Matching Pursuit, ROMP）。该算法旨在解决从低维观测数据中精确恢复高维稀疏信号的问题，是连接贪婪算法与凸优化算法的重要桥梁。 该算法的核心改进在于引入了“规则化”筛选机制。在每一轮迭代过程中，算法首先筛选出与当前残差相关性最强的一组原子，随后在这些原子中应用规则化准则，即选取其中分量能量最为接近且满足特定比例关系的原子子集。这种方法

详 情 说 明

基于规则化正交匹配追踪（ROMP）的压缩感知信号恢复算法

项目介绍

本项目实现了一种经典的压缩感知（Compressed Sensing, CS）信号重构算法——规则化正交匹配追踪（Regularized Orthogonal Matching Pursuit, ROMP）。ROMP 算法是正交匹配追踪（OMP）算法的重要演进版本，它通过在原子筛选阶段引入“规则化”准则，有效地克服了单纯贪婪搜索在稳定性上的不足。该算法在保持较低计算复杂度的同时，能够提供更强的重构理论保证，是连接简单贪婪算法与复杂凸优化算法（如基追踪 BP）的重要桥梁。

本项目完整演示了从原始稀疏信号生成、测量矩阵构建、信号观测到最终算法重构及性能评估的全过程。

功能特性

1. 自动生成稀疏信号：程序能够根据设定的稀疏度 K，在指定长度 N 的空间内随机生成非零分量。
2. 标准测量环境模拟：采用高斯随机矩阵作为测量矩阵，并执行列归一化处理，确保满足受限等距性（RIP）的基本要求。
3. 严格的规则化筛选机制：在每次迭代中，不仅筛选出相关性最强的原子，还利用规则化准则筛选能量最集中的原子子集。
4. 正交投影更新：利用最小二乘法进行信号估计，确保每次迭代后残差与已选支撑集原子正交。
5. 综合性能评估：自动计算并输出均方误差（MSE）和相对误差（Relative Error）。
6. 直观结果可视化：通过图形对比原始信号与重构信号，并绘制残差收敛曲线以展示算法执行过程。

系统要求

1. 运行环境：MATLAB R2016b 或更高版本。
2. 依赖工具箱：基础 MATLAB 内核即可，无需特殊工具箱。

使用方法

1. 打开 MATLAB 软件。
2. 将包含代码的脚本文件设置为当前工作路径。
3. 直接运行该脚本。
4. 查看命令行窗口输出的重构误差数据。
5. 观察自动生成的对比图表，验证重构效果。

实现逻辑说明

本项目的核心代码逻辑严格遵循以下六个步骤：

1. 参数初始化：设置原始信号长度 N 为 256，观测维度 M 为 128，信号稀疏度 K 为 20。
2. 原始信号生成：随机选取 K 个位置并赋予高斯随机分布的幅值，构建原始稀疏信号。
3. 观测系统构建：

- 生成 M×N 的高斯分布矩阵作为测量矩阵。 - 对测量矩阵进行列归一化，使其每列的二范数为 1。 - 将测量矩阵与原始信号相乘，获得低维观测向量。

1. ROMP 算法重构过程：

- 初始化残差为原始观测向量，支撑集为空。 - 进入迭代循环（最大迭代次数为 K）。 - 匹配投影：计算测量矩阵各列与当前残差的相关系数。 - 初选原子：在相关系数中挑选出数值最大的前 K 个候选索引。 - 规则化筛选：在 K 个候选索引中，寻找一个子集，该子集满足其中最大分量与最小分量的比值不超过 2，且该子集的总能量（平方和）在所有满足条件的子集中达到最大。 - 更新支撑集：将筛选出的原子索引加入支撑集并去重。 - 最小二乘估计：利用左伪逆（反斜杠算子）在支撑集上解最小二乘问题，得到当前重构幅值。 - 残差更新：计算新的残差并记录其范数。 - 终止检查：若残差范数小于 1e-6 或支撑集大小达到观测维度 M，则提前终止。

1. 性能度量：根据重构结果与原始信号的差值，计算 MSE（均方误差）和 Relative Error（相对误差）。
2. 可视化呈现：

- 第一张子图展示原始信号（蓝色）与重构信号（红色虚线）的对比，证明算法捕捉非零位置和幅值的准确性。 - 第二张子图采用半对数坐标（semilogy）展示残差随迭代次数下降的过程，体现算法的收敛速度。

关键算法细节分析

1. 匹配准则：算法通过计算相关系数绝对值来衡量原子与残差的相似度，这体现了匹配追踪的核心思想。
2. 规则化准则（Regularization）：这是 ROMP 的灵魂。算法通过 curr_u(i) <= 2 * curr_u(j) 这一条件，强制选择一组“能量相近”的原子。这种方法比 OMP 每次只选一个原子更高效，比传统方法更稳定。
3. 计算效率：在更新支撑集后，直接通过正交投影（最小二乘）一次性完成支撑集上所有系数的估计，保证了算法的收敛性。
4. 鲁棒性：通过设置 unique 函数确保支撑集索引不重复，并通过残差阈值和维度限制双重控制循环跳出，防止算法陷入死循环或过拟合。