正交匹配追踪算法小试

变量说明： 变量符号 说明 M 字典矩阵A的行数

N 字典矩阵A的列数

K 算法迭代次数/信号量x的非零元素个数

index 前面用作随机给信号向量x置零的/后面用于保存字典矩阵A中的最强相关原子序号,充当Ω

x 稀疏信号向量x

y 观测数据向量,y=Ax

A 字典矩阵A

my my为ppt中算法中的xk，估计最小化问题y-AΩkx的二范数解

a a为my乘上AΩk，用于更新残差

residual 残差，初始化为y

X 一个全零的(N,1)矩阵，最后用于存放算法恢复的信号向量

product A的转置与残差相乘后再加绝对值

pos 字典与残差向量最强的相关列的序号

算法步骤： 正交匹配追踪算法

1. 算法传入参数M,N,K.
2. 随机生成字典矩阵A,信号向量x矩阵，并生成一个与x维度相同的全零矩阵X，生成一个从0到N的随机顺序的整数数组index，利用循环将信号向量x在index数组的随机性质下置N-K个元素为0.计算观测数据向量y=Ax.
3. 初始化残差，residual=y，将index数组N个数值全部置为-1.
4. 进行K次迭代，先求出A转置与残差的乘积，并返回绝对值给product，再找到product中最大的那一列，将列序号赋到pos中，将index[pos]置1，在此处index发挥的作用是ppt中Ω集合的作用，下面直接搜索index数组大于0的下标的A中的原子进行运算。利用公式：

计算出my的值，这里我查阅资料利用了最小二乘法，直接利用python中的代码np.linalg.pinv(A[:,index>=0])。最后求a=np.dot(my,y)更新残差。利用的公式如下：下标k为第k次迭代

5.将X中index大于0的下标的位置依次等于a的各行数值，即输出系数向量，算法函数返回X。

结果：