基于OMP算法的压缩感知信号恢复仿真程序

资 源 简 介

本项目实现了一个标准的正交匹配追踪（Orthogonal Matching Pursuit, OMP）算法，完全遵循Tropp和Gilbert在经典论文《Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit》中的算法描述。程序的具体功能包括：构建K-稀疏的随机信号作为原始数据；构造高斯随机测量矩阵（或伯努利矩阵）模拟对信号的压缩采样过程，获取低维观测向量；实现OMP算法的核心迭代流程，包括初始化残差、计算相关系数寻找最大投影原子、更新支撑集索引、通过最小二乘法进行正交投影以求解系数、以及更新残差向量。该程序代码结构简洁、逻辑清晰且注释详尽，旨在通过直观的信号重建过程，帮助压缩感知（Compressed Sensing, CS）领域的初学者理解稀疏表示及贪婪迭代算法的基本原理，快速掌握从少量随机测量值中高概率恢复原始信号的方法。

详 情 说 明

基于OMP算法的压缩感知信号恢复仿真

项目介绍

本项目实现了一个标准的正交匹配追踪（Orthogonal Matching Pursuit, OMP）算法，完全遵循Tropp和Gilbert在经典论文《Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit》中的算法描述。项目旨在演示压缩感知（Compressed Sensing, CS）的核心思想：如何从少量的随机测量值中，高概率地精确恢复原始的高维稀疏信号。

该程序代码结构简洁、注释详尽，通过直观的信号重建过程和数据可视化，帮助初学者理解稀疏表示及贪婪迭代算法的基本原理。

功能特性

• 稀疏信号生成：自动构建指定稀疏度（K-Sparse）的随机信号，支撑集位置和非零元素值均为随机生成。
• 压缩测量模拟：构造高斯随机测量矩阵，并对列向量进行归一化处理，模拟压缩采样过程获取低维观测向量。
• OMP算法核心实现：

* 实现了基于相关系数的贪婪原子选择。 * 实现了基于最小二乘法（Least Squares）的正交投影系数求解。 * 包含完整的残差更新与迭代收敛记录。

• 结果验证与可视化：

* 计算并输出相对重构误差（L2范数）。 * 提供包含原始/重构信号对比、观测向量分布、残差收敛曲线的综合图表。

系统要求

• MATLAB R2016a 或更高版本（代码使用标准MATLAB语法，无特殊工具箱依赖）。

使用方法

1. 确保MATLAB环境已安装。
2. 打开 main.m 脚本文件。
3. 点击运行。程序将自动执行仿真流程，在命令行窗口输出参数配置及重构误差，并弹出一个图形窗口显示仿真结果。

算法实现细节与逻辑说明

本项目的核心逻辑位于 main.m 中，具体处理流程如下：

1. 参数初始化与信号构建

• 参数配置：设定信号长度 $N=512$，测量数 $M=256$，稀疏度 $K=30$。
• 随机种子：使用 rng(42) 固定随机数生成器种子，确保每次运行的结果可重复。
• 稀疏信号生成：初始化全零向量，利用 randperm 随机选择 $K$ 个位置作为支撑集，并在这些位置填充标准正态分布随机值（randn），生成原始信号 $x$。

2. 测量过程模拟

• 构建测量矩阵：生成 $M times N$ 大小的高斯随机矩阵 $Phi$。
• 列归一化：遍历矩阵 $Phi$ 的每一列，将其除以自身的二范数。这是压缩感知理论中的标准预处理步骤，有助于保持原子能量一致。
• 获取观测值：通过矩阵乘法 $y = Phi x$ 计算得到长度为 $M$ 的低维观测向量。

3. OMP 迭代恢复过程

算法核心采用贪婪迭代策略，循环 $K$ 次（对应稀疏度），主要步骤包括：

• 计算相关系数：计算测量矩阵转置与当前残差向量的内积（Phi' * r），取绝对值得到相关性向量。这代表了残差在字典各个原子上的投影大小。
• 贪婪选择：寻找相关性向量中数值最大的元素及其索引（max 函数），该索引对应的列即为当前步骤最匹配的原子。
• 更新支撑集：将选中的原子索引加入索引集合 aug_k，并将对应的矩阵列加入增广矩阵 Aug_t。代码中包含简单的重复性检查逻辑。
• 正交投影（最小二乘法）：使用 MATLAB 的反斜杠运算符（`）求解超定方程组 $theta = Aug_t backslash y$。这一步实现了正交投影，保证残差与已选原子张成的空间正交，是 "Orthogonal" Matching Pursuit 的关键。
• 更新残差：计算新的残差 $r = y - Aug_t times theta$，并记录当前残差的范数用于后续分析。

4. 信号重构与评估

• 构建稀疏解：根据迭代结束后的系数 $theta$ 和索引集合 aug_k，将数值填入全零向量的对应位置，得到最终的重构信号 $x_{rec}$。
• 误差计算：计算原始信号与重构信号差值的L2范数，并归一化，得到相对重构误差。若误差小于 1e-6，程序将判定为完美重构。

关键代码分析

• Phi(:, i) = Phi(:, i) / norm(Phi(:, i))：

实现了测量矩阵的列归一化。在OMP算法中，如果原子（列向量）没有归一化，内积的大小将受到列向量模长的影响，从而可能导致错误的原子选择。

• product = abs(Phi' * r)：

这是匹配追踪的第一步，通过计算内积衡量当前的残差与哪个原子方向最一致。

• theta = Aug_t y`：

这是OMP区别于MP（Matching Pursuit）的关键。它求解的是全局最优系数（在当前支撑集下），确保了残差的正交性，使得算法能够在 $K$ 步内收敛（在理想条件下）。

结果可视化说明

程序运行结束后生成的图形界面包含三个子图：

1. 稀疏信号重构对比：

* 蓝点实线：原始稀疏信号。 * 红圈虚线：OMP算法重构出的信号。 * 观察点：如果红圈能够准确覆盖蓝点，说明非零位置和幅值均恢复成功。

1. 压缩测量观测向量 y：

* 展示了长度为 $M$ 的观测数据，体现了从 $N$ 维到 $M$ 维的降维过程。

1. OMP迭代过程残差收敛情况：

* 展示了随着迭代次数增加（从 1 到 $K$），残差向量 L2 范数的变化趋势。 * 观察点：正常的收敛曲线应呈现单调递减趋势。