基于压缩感知的匹配追踪(MP)算法仿真

资 源 简 介

本项目完整实现了基于压缩感知（Compressed Sensing, CS）理论的匹配追踪（Matching Pursuit, MP）重构算法。压缩感知理论打破了传统奈奎斯特采样定理的限制，允许以极低的采样率对稀疏信号进行采样和重建。MP算法作为一种经典的贪婪迭代算法，主要用于解决稀疏近似问题。本项目的核心功能流程包括：首先构建一个长度为N的稀疏信号；其次生成一个M x N的测量矩阵（通常为高斯随机矩阵）对信号进行降维观测；然后利用编写的MP算法核心代码，通过迭代方式在过完备字典中寻找与当前残差最匹配的原子，逐步逼近并重构原始信号。该代码经过严格的仿真验证，能够准确地从由测量矩阵获取的少量观测值中恢复出原始信号，并可视化展示重构效果与误差分析，适用于信号处理、图像压缩及压缩感知算法研究等场景。

详 情 说 明

基于压缩感知的匹配追踪(MP)算法仿真

项目简介

本项目是一个基于压缩感知（Compressed Sensing, CS）理论的MATLAB仿真工程，旨在演示和验证匹配追踪（Matching Pursuit, MP）算法在稀疏信号重构中的应用。

压缩感知理论表明，如果信号在某个变换域是稀疏的，则可以用远低于奈奎斯特采样定理要求的采样率对信号进行采样，并能够高概率地精确重构原始信号。本项目通过构建稀疏信号、生成测量矩阵、进行压缩观测，并最终编写核心MP算法从少量观测值中恢复原始信号，完整复现了CS的处理流程。

功能特性

• 稀疏信号生成：能够构建指定长度和稀疏度的一维信号，非零元素位置随机，幅值服从标准正态分布。
• 测量矩阵构建：使用高斯随机矩阵作为测量矩阵（传感矩阵），并自动对矩阵列向量进行归一化处理，以满足MP算法的原子特性。
• 核心MP算法实现：不依赖第三方工具箱，完全手写实现的匹配追踪算法核心逻辑，包含内积匹配、系数更新及残差迭代。
• 性能评估指标：自动计算重构信号与原始信号的相对重构误差（L2范数）及均方误差（MSE）。
• 可视化分析：提供原始信号与重构信号的对比图，以及算法迭代过程中的残差收敛曲线。

系统要求

• MATLAB R2016a 或更高版本
• 无需额外的工具箱（Toolbox），仅使用MATLAB基础函数

使用方法

1. 下载本项目代码。
2. 在MATLAB环境中打开脚本文件。
3. 直接运行脚本，程序将自动执行以下步骤：

* 初始化参数（信号长度N=256，测量数M=128，稀疏度K=12）。 * 生成稀疏信号与测量矩阵。 * 执行MP算法进行信号重构。 * 在命令窗口输出运行时间、稀疏度参数及重构误差。 * 弹出图形窗口展示重构效果与残差变化。

算法实现细节与逻辑分析

本项目代码主要分为主控流程与MP算法核心函数两部分，具体实现逻辑如下：

1. 信号模型与测量

• 信号构建：初始化一个长度为 $N=256$ 的全零向量，随机选取 $K=12$ 个位置赋予标准正态分布随机值，模拟稀疏信号。
• 测量矩阵：生成 $M times N$ ($128 times 256$) 的高斯随机矩阵 $Phi$。
• 原子归一化：关键步骤，代码通过循环将 $Phi$ 的每一列（视为字典中的原子）进行L2范数归一化。这是匹配追踪算法简化计算系数的前提。
• 压缩观测：通过矩阵乘法 $y = Phi x$ 获得维度为 $M$ 的观测向量。

2. 匹配追踪 (MP) 算法核心逻辑

代码中包含一个名为 mp_algorithm 的内部函数，实现了经典的贪婪迭代策略：

• 初始化：重构信号 $theta$ 初始化为全零向量，初始残差 $r$ 设为观测向量 $y$。
• 迭代过程（最大 $4 times K$ 次）：

1. 相关性计算：计算当前残差 $r$ 与测量矩阵 $Phi$ 中所有列向量（原子）的内积。 2. 原子匹配：寻找内积绝对值最大的原子，记录其索引 pos。 3. 系数提取：直接取该最大内积值作为投影系数 coeff（得益于之前的列归一化处理）。 4. 解更新：在重构向量 $theta$ 的对应 pos 位置累加系数 coeff。注意：MP算法允许在不同迭代步中重复选择同一个原子，系数值会进行叠加。 5. 残差更新：从当前残差中减去选定原子与系数的乘积，即 $r_{new} = r_{old} - coeff times Phi_{pos}$。 6. 收敛检查：计算残差能量，若小于设定阈值 ($1e-6$) 则提前终止迭代。

3. 性能评估与输出

• 相对误差：计算 $frac{||x_{original} - x_{reconstructed}||_2}{||x_{original}||_2}$，用于衡量恢复精度。
• 均方误差 (MSE)：计算原始信号与重构信号差值的平方均值。
• 耗时统计：使用 tic 和 toc 记录核心算法的执行时间。

结果可视化说明

程序运行结束后会生成包含两个子图的图形窗口：

1. 原始信号 vs MP重构信号：

* 使用蓝色实线（Stem图）表示原始稀疏信号。 * 使用红色虚线（Stem图）表示MP算法重构出的信号。 * 该图直观展示了算法是否准确捕获了非零元素的位置和幅值。

1. MP算法迭代残差收敛曲线：

* 横轴为迭代次数，纵轴为残差能量（L2 Norm）。 * 展示了随着迭代进行，残差能量逐步下降并收敛的过程，用于分析算法的收敛速度和稳定性。