压缩感知OMP程序

% 1-D信号压缩传感的实现(正交匹配追踪法Orthogonal Matching Pursuit)

% 测量数M>=K*log(N/K),K是稀疏度,N信号长度,可以近乎完全重构

% 编程人--香港大学电子工程系 沙威 Email: wsha@eee.hku.hk

% 编程时间：2008年11月18日

% 文档下载: http://www.eee.hku.hk/~wsha/Freecode/freecode.htm

% 参考文献：Joel A. Tropp and Anna C. Gilbert

% Signal Recovery From Random Measurements Via Orthogonal Matching

% Pursuit，IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 53, NO. 12,

% DECEMBER 2007.

clcclear

%% 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) % 完整信号

%% 2. 时域信号压缩传感

Phi=randn(M,N) % 测量矩阵(高斯分布白噪声)

s=Phi*x.' % 获得线性测量

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

m=2*K % 算法迭代次数(m>=K)

Psi=fft(eye(N,N))/sqrt(N) % 傅里叶正变换矩阵

T=Phi*Psi' % 恢复矩阵(测量矩阵*正交反变换矩阵)

hat_y=zeros(1,N)% 待重构的谱域(变换域)向量

Aug_t=[]% 增量矩阵(初始值为空矩阵)

r_n=s % 残差值

for times=1:m % 迭代次数(有噪声的情况下,该迭代次数为K)

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_y=(Aug_t'*Aug_t)^(-1)*Aug_t'*s % 最小二乘,使残差最小

r_n=s-Aug_t*aug_y % 残差

pos_array(times)=pos% 纪录最大投影系数的位置

end

hat_y(pos_array)=aug_y % 重构的谱域向量

hat_x=real(Psi'*hat_y.')% 做逆傅里叶变换重构得到时域信号

%% 4. 恢复信号和原始信号对比

figure(1)

hold on

plot(hat_x,'k.-') % 重建信号

plot(x,'r') % 原始信号

legend('Recovery','Original')

norm(hat_x.'-x)/norm(x) % 重构误差

【嵌牛导读】：传统基于奈奎斯特定律的信号采样方法暴露出来的缺点越来越多，几年来一种新的理论----压缩感知打破了奈奎斯特采样定理（采样速率大于信号最高频率的两倍），成为了新的研究热点。

【嵌牛鼻子】：压缩感知信号采集欠奈奎斯特采样正交匹配追踪

【嵌牛提问】：压缩感知的原理？

【嵌牛正文】：

2004年，D.Donoho等人提出了压缩感知理论，Tao T等人在此基础上进行了改进[ ]，为超宽带信号采集问题的解决开辟了一条新的道路。该理论是假设待采样信号在某个空间内具有稀疏的特性（只有少量的非零元素），利用测量矩阵将高维的稀疏信号投影为低维的测量值，从而完成对信号的压缩。然后通过优化求解的方法，可以精确重构出原始信号。该理论将压缩和数模变换合围一体，利用低采样率完成对宽带信号的压缩采样，降低了对AD器件性能的要求，具有十分良好的发展前景，其系统框图如下图所示。

压缩感知主要分为三个部分：信号稀疏表示、压缩测量、信号重构。

信号稀疏表示：

首先介绍一下压缩感知中十分重要的几个概念。

稀疏性：如果一个向量的大多数元素都为0，只有少量元素具有有效值，那么这个向量就具有稀疏性[ ]。

稀疏度：如果一个向量中非零元素个数小于N，即‖x‖_0

压缩测量：

压缩测量是压缩感知中非常重要的一步，其关键在于压缩矩阵的选择。压缩矩阵的作用就是将高维的信号映射为低维的输出信号，完成信号的压缩测量。测量过程可以用下式表示。

令测量矩阵A_(l*n)=φ_(l*n)*Ɵ_(n*n)，上式可简化为下式：

如果要求信号能够重构，那么这种映射应该是一一对应的，即特定的µ只能映射为唯一的y。这样的唯一性是保证信号能够精确重构的前提。为了满足这样的重构条件，测量矩阵A必须满足一定的条件。T.TAO等人提出为此提出了RIP条件（受限等距特性）。如果A能满足下式的不等式:

上式表示在测量矩阵满足RIP条件时，重构出的信号的误差在相当小的一个范围内。经过上面的讨论，我们就为精确重构出信号提供了理论上的保障。

信号重构：

重构算法是压缩感知的核心内容和最后一步，其恢复精确度和算法复杂程度决定了采样系统的可行性和实用性。由采样输出y_(l*1)求解输入信号µ_(n*1)是一个未知数个数多余方程个数的欠定方程。通常情况下其解有无数个，需要进行优化求解来确定最优解。

常用的优化求解算法为：贪婪算法，凸优化算法和组合算法。

AIC(模拟信息转换器)， 其结构如下图所示。

单像素相机

每次只取一个像素点，随机取若干次。运用算法对所取的像素值进行处理，恢复出原始信号

医学成像

用0范数或1范数解决cs重构归属一个数学问题，犹如给定你一个公式，利用这个公式或者说原理去做出很多的算法，cs重构本归属与对0范数的求解问题上的。

但0范数属于数学上一个NP_hard问题，是无法解决的，所以不能直接用求0范数的理论去做算法，从而提出一系列基于求0范数最小的贪婪类算法。如MP,OMP等算法。，这类算法中，最为基础的算是MP算法了。贪婪算法的速度较快，但是重构效果相对较差，需要的测量数也较多，不能高效地压缩信号，并且对测量矩阵的要求更高。但总的来说，应用范围广。

数学家同时发现，求解L1范数也可以逼近与0范数的效果，即把NP_hard问题转化为线性规划问题。所以现在有很多用求L1范数原理而创造了各类算法，最典型的是BP（基追踪）算法和梯度投影稀疏重构算法。这种算法重构效果很好，但是运算量大，复杂，应用于实际上可能不大。至少得改进其算法。

还有一大类算法，我不关注，不说了。

具体那些算法怎么实现，自己去网上下程序仿真一下吧。。。。

---