STOMP算法实现与解析：正交匹配追踪的简化版本

"stomp.txt是一个关于分段正交匹配追踪(Stochastic Gradient Orthogonal Matching Pursuit, STOMP)算法的实现，该算法用于从测量向量中恢复稀疏信号。文件提供了一段MATLAB代码，包含详细的注释，适合作为基础类代码学习。STOMP算法采用贪婪迭代策略，每次选取与当前残差最相关的测量矩阵列，逐步减少残差，直至达到预设的稀疏度或迭代次数上限。" STOMP算法是稀疏信号恢复领域的一个重要方法，其主要步骤和关键知识点如下： 1. **输入参数**： - `y`：观测或测量向量，通常为线性测量的结果。 - `A`：传感矩阵，描述了信号到测量的线性变换。 - `S`：最大迭代次数，限制了算法的运行时间。 - `ts`：阈值参数，用于确定哪些列与残差高度相关。 2. **初始化**： - 将`y`转换为列向量，确保后续计算的正确性。 - 初始化恢复信号`theta`为零向量。 - 初始化残差`r_n`为原始测量向量`y`。 - 创建一个空集合`Pos_theta`，用于存储已选择的传感矩阵列的索引。 3. **主迭代过程**： - 对于每个迭代步骤`ss`，计算传感矩阵`A`的每一列与当前残差的内积。 - 使用阈值`ts`和标准差`sigma`找出与残差高度相关的列索引`Js`。 - 更新候选列集`Is`为`Pos_theta`与`Js`的并集。 - 如果没有新的列被选中，且已达到最大迭代次数，或者在第一次迭代时没有新列，则结束迭代。 - 如果候选列数不超过测量向量的维度，更新`Pos_theta`和相应的子矩阵`At`。 - 计算最小二乘解`theta_ls`，即`At`的伪逆乘以`y`。 - 更新残差`r_n`为`y`减去`At`与`theta_ls`的乘积。 - 当残差的范数小于一个很小的阈值（如1e-6）时，提前结束迭代。 4. **结果输出**： - 最终的恢复信号`theta`只填充了在迭代过程中选择的列对应的元素，即`theta(Pos_theta)`。 STOMP算法相较于传统的匹配追踪(Orthogonal Matching Pursuit, OMP)算法，引入了随机梯度下降的元素，能够在一定程度上提高算法的效率和恢复性能。在实际应用中，STOMP通常用于压缩感知(Compressive Sensing)场景，如图像压缩、信号处理等，通过较少的测量数据恢复原始的稀疏信号。