《基于压缩传感的匹配追踪重建算法研究》读书笔记

基于压缩传感的匹配追踪重建算法研究

1、压缩感知与传统数据获取和处理过程比较：

压缩感知理论表明，在对信号获取的同时，就对数据进行适当的压缩。

传统的数据获取和处理过程主要包括：采样、压缩、传输、解压缩，且采样过程必须满足奈奎斯特采样定律，这种方式采样数据量大，先采样再压缩，浪费大量的传感元，时间和存储空间，相较而下，压缩感知理论针对可稀疏表示的信号，将数据采集和数据压缩合二为一，在信号处理领域应用前景广阔。

2、基础理论介绍：

Candes 和 Donoh 在相关研究基础上于2006年正式提出了压缩传感的概念，设 x(n) 为传统采样所得到的N维数字信号， 如果它是一个K－稀疏（仅有K个非零元 K<<N）或是可压缩（通过变换可成为 K 稀疏〉的信号， 那么它在线性变换下仅用少量的系数即可很好地估计出来。 而通过压缩传感过程可直接得到M维信号 y(m) (M < N ）， 它们之间的关系为：

                                                                              （1）

该式也可以看作原信号x在  下的线性投影。 其中，  称为传感矩阵或测量矩阵， 大小为MxN。压缩传感过程如图 1-1 所示：

其中A I C（Analog-to-information Conversion）为模拟信息转换，通过AIC可以得到 y(m)，之后通过重建算法即可重建数字信号 x(n)。因此，重建算法对于压缩传感采样过程准确性的验证和后期 x(n) 压缩之后的精确重构均有着重要的意义。 由于式（1）中 y 的维数远远低于 x 的维数，因此方程有无穷多个解，即该问题是不适定的，很难直接重建原始信号。

但若 x(n) 是K-稀疏的，则未知数的个数就会大大减少，这样就有很大可能使得方程有唯一解，即能够有 y(m) 重建 x(n)。

这种情况下的方程为：

或者 x(n) 可以通过变换变成K-稀疏信号，例如通过正交变换变成频域的稀疏信号，，s 为  下的稀疏信号。

这种情况下的方程变换为：

理论证明，可以通过求解下面的最优  范数问题，就能够从观测信号 y 中精确重构出未知信号 x：

或者：

Candes 指出当K、 M、 N之间满足  且矩阵  满足约束等距性条件RIP(Restricted Isometry Property)时，

x(n)即可置信重建。

通过以上的分析可以看到， 压缩传感的核心思想与传统信号采样方法对原始信号x先来样后压缩不同， 它由少量线性测量通过求解最优  范数问题得到 x ，突破了 Nyqusit 来样定理的瓶颈， 降低了对传感器件分辨率的要求，使得超高分辨率信号获取成为可能。 在压缩传感中，稀疏信号的重建是一个非常重要的问题。

3、简单谈谈有限等距性条件：

Baraniuk 给出约束等距性的等价条件是测量矩阵  和稀疏表示基  不相关，相关论文已经证明当  为高斯随机矩阵时，能较好地满足这一条件。因此，我们可以选择一个大小为 M*N 的高斯随机矩阵作为测量矩阵，其中每一个值都满足  的独立正态分布。 高斯测量矩阵的优点在于它几乎与任意稀疏信号都不相关， 因而所需的测量次数最小。 但缺点是矩阵元素所需存储空间很大，并且由 于其非结构化的本质导致其计算复杂。

4、压缩感知的应用

运用压缩传感原理， RICE 大学的 Baraniuk 等人成功研制了单像素相机。由于该相机直接获取的是M次随机线性测量值， 而不是获取原始信号的N(M <N)个像素值， 因此为低像素相机拍摄高质量图像提供了可能。

5、引出最小范数法：

信号重建算法是压缩传感理论关键的一部分， 是指由M维测量向量y重建出长度为N(M <N）的信号x的过程。Candes等证明了信号重建问题可以通过求解最小  范数问题加以解决，因为  范数最小使得结果尽可能地稀疏。但Donoho 指出， 求解最小 范数是一个NP-hard问题， 需要穷举x中非零值的所有  种排列可能， 因而无法直接求解。 鉴于此， 相关研究人员提出了一系列求得次最优解的算法，主要包括最小  范数法、贪婪迭代匹配追踪系列算法、迭代阙值法以及专门处理二维图像问题的最小全变分法等。

将  转化为：

, 即将 范数问题转化为范数问题，有文献已经证明二者是等价的。

6、信号重构算法：

重建算法的关键是如何从压缩传感得到的低维数据中精确地恢复出原始的高维数据， 因此对采样过程准确性的验证有着至关重要的意义。

OMP重构算法简介：

OMP算法本质思想是： 以贪婪迭代的方法选择  的列， 使得在每次迭代中所选择的列与当前的元余向量最大程度地相关， 从测量向量中减去相关部分并反复迭代， 直到迭代次数达到稀疏度K， 强制迭代停止。

核心算法步骤：

根据此步骤给出OMP重构算法的MATLAB代码（改自沙威大牛）并给出解释：

 %  1-D信号压缩传感的实现(正交匹配追踪法Orthogonal Matching Pursuit)
 %  测量数M>=K*log(N/K),K是稀疏度,N信号长度,可以近乎完全重构 clc;clear;close all;
 % 1. 时域测试信号生成
 K = 7; %  稀疏度(做FFT可以看出来)
 N = 256; %  信号长度
 M = 64; %  测量数(M>=K*log(N/K),至少40,但有出错的概率)
 f1 = 50; %  信号频率1
 f2 = 100;   %  信号频率2
 f3 = 200;   %  信号频率3
 f4 = 400;   %  信号频率4
 fs = 800;   %  采样频率
 ts = 1/fs;  %  采样间隔
 Ts = 1:N;   %  采样序列
 x = 0.3*cos(2*pi*f1*Ts*ts)+0.6*cos(2*pi*f2*Ts*ts)+0.1*cos(2*pi*f3*Ts*ts)+0.9*cos(2*pi*f4*Ts*ts);  %  完整信号,由4个信号叠加而来
 % 2.  时域信号压缩传感
 Phi = randn(M,N); %  观测矩阵，（M*N）64*256的扁矩阵
 y = Phi*x.'; %  获得观测向量y，（M*1）

 % 3.  正交匹配追踪法重构信号(本质上是L_1范数最优化问题)

 m = 2*K; %  算法迭代次数(m>=K)，设x是K-sparse的
 Psi = fft(eye(N,N))/sqrt(N); %  标准正交基字典（离散傅里叶变换标准正交基矩阵）x'=Psi'*s;(s = Psi*x')
 T = Phi*Psi'; %  恢复矩阵(测量矩阵*正交反变换矩阵)

 hat_s = zeros(1,N); %  待重构的谱域(变换域)向量(行向量1*N)
 Aug_t = []; %  增量矩阵(初始值为空矩阵)
 r_n = y; %  残差值
 product = zeros(1,N);

 for times = 1:m %  迭代次数 for col = 1:N %  恢复矩阵的所有列向量 product(col) = abs(T(:,col)'*r_n); %  恢复矩阵的列向量和残差的投影系数(内积值) end [val,pos] = max(product); %  最大投影系数对应的位置，即找到一个其标记看上去与收集到的数据相关的小波 Aug_t = [Aug_t,T(:,pos)]; %  矩阵扩充 T(:,pos) = zeros(M,1); %  选中的列置零（实质上应该去掉，为了简单我把它置零），在数据中去除这个标记的所有印迹 aug_s = (Aug_t'*Aug_t)^(-1)*Aug_t'*y; %  最小二乘,使残差最小 r_n = y-Aug_t*aug_s; %  残差 pos_array(times) = pos; %  纪录最大投影系数的位置
 end
 hat_s(pos_array)=aug_s; %  重构的谱域向量
 hat_x=real(Psi'*hat_s.'); %  做逆傅里叶变换重构得到时域信号

 %%  4.  恢复信号和原始信号对比
 figure(1);
 hold on;
 plot(hat_x,'k.-') %  重建信号
 plot(x,'r') %  原始信号
 legend('Recovery','Original')
 norm(hat_x.'-x)/norm(x)  

————————————————————————————————————————————————————

符号解释：

这些符号的具体叫法可见（个人觉得还是挺权威）：

压缩感知回顾与展望

K为稀疏度

Phi为观测矩阵，又叫测量矩阵

Psi为正交基字典矩阵（x = Psi ' * s）(s = Psi * x) (x 为时域信号，s 为频域稀疏信号)

hat_s, 信号x在Psi域的稀疏表示，hat_s是K稀疏的，在程序中为行向量

T = Phi * Psi'；为恢复矩阵，又叫CS信息算子（y = Phi * x = Phi * Psi' * s = T * s）

在程序中它们的关系为：hat_y = Phi * Psi' * hat_s' = T * hat_s';

Aug_t: M * times, 由矩阵T中与残差r_n最相关的列向量组成。

对代码的逐行解释，我就不做重复的工作了，见：

压缩感知“Hello World”代码初步学习

这篇文章后面讲解的很详细了。

下面给出上述代码运行结果：

————————————————————————————————————————————————————

不得不说文章的精华我还没有抓到，后面很多恢复算法，我都想去实现一下，作下比较。后面有时间继续更新吧，时间有点紧张。

文章来源: reborn.blog.csdn.net，作者：李锐博恩，版权归原作者所有，如需转载，请联系作者。

原文链接：reborn.blog.csdn.net/article/details/80615635