下载文档原格式
正交匹配追踪算法omp原理
正交匹配追踪算法（Orthogonal Matching Pursuit，简称OMP）是一种用于稀疏重构的迭代算法，主要用于解决压缩感知问题。
其原理如下：
1. 稀疏表示假设：假设信号可以通过少量的原子（基底）的线性组合来表示，即稀疏表示。
2. 初始状态：设置初始残差为输入信号，初始解集为空集。
3. 原子选择：在目前残差中选择一个最适合代表残差的原子（基底）。
4. 矩阵变换：将原子调整为正交的形式，即正交化。
5. 正交投影：计算残差与正交基底的投影，得到投影系数。
6. 更新残差：使用投影系数更新残差。
7. 判断结束：如果残差的能量减少到一定程度，则认为重构已经足够准确，结束算法；否则，返回第3步进行下一个迭代。
8. 输出结果：返回最终的解集，其中每个元素对应一个原子。
OMP算法没有要求输入信号满足特定的分布条件，因此适用
于多种应用场景。
算法通过选择最适合的原子来逐步逼近信号，并且通过迭代追踪算法的方式，能够保证逐步收敛到最优解。
该算法的时间复杂度较低，且能在较短的时间内达到令人满意的重构质量。
压缩感知OMP和SP算法在图像重构的应用
作者：张马会
来源：《电脑知识与技术》2015年第23期
摘要：该文介绍了压缩感知理论以及OMP和SP算法的核心思想以及信号的仿真实验，利用离散小波变换的方法对图像信号进行稀疏化的处理，并分别用OMP算法和SP算法对图像信号进行重构。
用MATLAB进行仿真实验，得到不同采样率下的重构图像以及重构图像的峰值信噪比和运行的时间。
实验结果表明：OMP算法的运行时间比较短，而SP算法在采样率低的情况下重构效果比较好。
关键词：压缩感知；图像处理；重构算法
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2015）23-0123-02。
基于压缩感知的信号重构算法研究共3篇基于压缩感知的信号重构算法研究1基于压缩感知的信号重构算法研究随着信息技术的发展以及现代通信系统的广泛应用，人们对于信号重构算法的研究也越来越深入。
其中，基于压缩感知的信号重构算法受到了广泛关注。
本文将从以下四个方面来探讨该算法的研究。
一、压缩感知的基本原理压缩感知的核心思想是将一个高维信号（如图像、音频等）映射到一个较低维的空间中，然后再通过一个线性投影方式将数据压缩。
利用测量矩阵可以将压缩后的数据重构到原来的高维空间中，并且能够利用未知信号的稀疏性完成恢复过程。
这种低维的表示方式可以使数据占用的空间大大减小，因此压缩感知成为了高效的信号采样方式。
二、常见的压缩感知算法常见的压缩感知算法包括OMP算法、CoSaMP算法、MPCP算法等。
其中OMP算法是一种迭代算法，用于寻找稀疏表示向量。
CoSaMP算法考虑到了噪声的影响，能够更准确地进行稀疏重构。
MPCP算法则是多向量压缩感知的拓展，用于处理多个信号的联合稀疏性问题。
三、压缩感知在图像压缩方面的应用基于压缩感知的信号重构算法在图像压缩方面的应用也是较为广泛的。
传统的JPEG和PNG等图像压缩算法虽然能够将图像进行压缩，但是重构后的图像质量较差，并且对于稀疏性较强的图像处理能力有限。
基于压缩感知的算法能够更好地处理稀疏性强的图像，同时也能够提高图像的显示效果。
四、压缩感知在音频处理方面的应用除了在图像处理方面的应用，基于压缩感知的信号重构算法在音频处理方面也具有广泛的应用前景。
例如在音频采样、去噪、提取声音等方面都有着极为广泛的应用。
此外，利用压缩感知的技术，人们还可以用较小的存储空间存储大量音乐等高质量音频数据。
综上所述，基于压缩感知的信号重构算法是一种高效且优越的信号处理方法，具有较广泛的应用前景。
在未来的研究中，我们可以结合更多的数据处理技术来提高算法的效率和精度基于压缩感知的信号重构算法在信号处理中具有广泛应用前景，能够更好地处理稀疏性较强的信号，并提高信号质量。
压缩感知重构算法之OMP算法python实现压缩感知重构算法之OMP算法python实现0pandas0 2016-03-18 15:08:55 9820 收藏 19分类专栏：压缩感知 python 压缩感知重建算法python实现⽂章标签： python压缩感知OMPmatlab重构版权压缩感知重构算法之OMP算法python实现压缩感知重构算法之CoSaMP算法python实现压缩感知重构算法之SP算法python实现压缩感知重构算法之IHT算法python实现压缩感知重构算法之OLS算法python实现压缩感知重构算法之IRLS算法python实现本⽂主要简单介绍了利⽤python代码实现压缩感知的过程。
压缩感知简介【具体可以参考这篇⽂章】假设⼀维信号xx长度为N，稀疏度为K。
ΦΦ为⼤⼩M×NM×N矩阵(M<<N)(M<<N)。
y=Φ×xy=Φ×x为长度M的⼀维测量值。
压缩感知问题就是已知测量值yy和测量矩阵ΦΦ的基础上，求解⽋定⽅程组y=Φ×xy=Φ×x得到原信号xx。
Φ的每⼀⾏可以看作是⼀个传感器（Sensor），它与信号相乘，采样了信号的⼀部分信息。
⽽这⼀部分信息⾜以代表原信号，并能找到⼀个算法来⾼概率恢复原信号。
⼀般的⾃然信号x本⾝并不是稀疏的，需要在某种稀疏基上进⾏稀疏表⽰x=ψsx=ψs,ψψ为稀疏基矩阵，SS为稀疏系数。
所以整个压缩感知过程可以描述为y=Φx=ΦΨs=Θsy=Φx=ΦΨs=Θs重建算法：OMP算法简析OMP算法输⼊:测量值y、传感矩阵Phi=ΦψPhi=Φψ、稀疏度K初始化:初始残差 r0=y,迭代次数t=1,索引值集合index;步骤:1、找到残差r和传感矩阵的列积中最⼤值对应下标，也就是找到⼆者内积绝对值最⼤的⼀个元素对应的下标，保存到index当中2、利⽤index从传感矩阵中找到，新的索引集PhitPhit3、利⽤最⼩⼆乘法处理新的索引集和y得到新的近似值θ=argmin||y−Phitθ||2θ=argmin||y−Phitθ||24、计算新的残差rt=y−Phitθrt=y−Phitθ，t=t+15、残差是否⼩于设定值，⼩于的话退出循环，不⼩于的话再判断t>K是否成⽴，满⾜即停⽌迭代，否则重新回到步骤1，继续执⾏该算法。
压缩感知的重构算法算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。
因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。
压缩感知的重构算法主要分为三大类：1.组合算法2.贪婪算法3.凸松弛算法每种算法之中又包含几种算法，下面就把三类重构算法列举出来。
组合算法：先是对信号进行结构采样，然后再通过对采样的数据进行分组测试，最后完成信号的重构。
(1) 傅里叶采样（Fourier Representaion）(2) 链式追踪算法（Chaining Pursuit）(3) HHS追踪算法（Heavy Hitters On Steroids）贪婪算法：通过贪婪迭代的方式逐步逼近信号。
(1) 匹配追踪算法（Matching Pursuit MP）(2) 正交匹配追踪算法（Orthogonal Matching Pursuit OMP）(3) 分段正交匹配追踪算法（Stagewise Orthogonal Matching Pursuit StOMP）(4) 正则化正交匹配追踪算法（Regularized Orthogonal Matching Pursuit ROMP）(5) 稀疏自适应匹配追踪算法（Sparisty Adaptive Matching Pursuit SAMP）凸松弛算法：(1) 基追踪算法（Basis Pursuit BP）(2) 最小全变差算法（Total Variation TV）(3) 内点法（Interior-point Method）(4) 梯度投影算法（Gradient Projection）(5) 凸集交替投影算法（Projections Onto Convex Sets POCS）算法较多，但是并不是每一种算法都能够得到很好的应用，三类算法各有优缺点，组合算法需要观测的样本数目比较多但运算的效率最高，凸松弛算法计算量大但是需要观测的数量少重构的时候精度高，贪婪迭代算法对计算量和精度的要求居中，也是三种重构算法中应用最大的一种。
压缩感知AMP数据重构算法仿真班级：zz学号：xx姓名：xx2020年12月24日1概述本文针对某个范围内的活跃用户数量检测问题，利用压缩感知AMP数据重构算法进行仿真，仿真的指标包括了各种信道参数、序列长度、序列类型、信噪比、用户数、活跃用户数，结果分析了对活跃用户身份检测的虚警概率和漏检概率。
2压缩感知理论2.1压缩感知简介传统方式下的信号处理，是按照奈奎斯特采样定理对信号进行采样，得到大量的采样数据，需要先获取整个信号再进行压缩，其压缩过程如图：图1传统的信号压缩过程在此过程中，大部分采样数据将会被抛弃，即高速采样后再压缩的过程浪费了大量的采样资源，这就极大地增加了存储和传输的代价。
由于带宽的限制，许多信号只包含少量的重要频率的信息。
所以大部分信号是稀疏的或是可压缩的，对于这种类型的信号，既然传统方法采样的多数数据会被抛弃，那么，为什么还要获取全部数据而不直接获取需要保留的数据呢？Candes和Donoho等人于2004年提出了压缩感知理论。
该理论可以理解为将模拟数据节约地转换成压缩数字形式，避免了资源的浪费。
即，在采样信号的同时就对数据进行适当的压缩，相当于在采样过程中寻找最少的系数来表示信号，并能用适当的重构算法从压缩数据中恢复出原始信号。
压缩感知的主要目标是从少量的非适应线性测量中精确有效地重构信号。
核心概念在于试图从原理上降低对一个信号进行测量的成本。
压缩感知包含了许多重要的数学理论，具有广泛的应用前景，最近几年引起广泛的关注，得到了蓬勃的发展。
2.2压缩感知原理压缩感知，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号进行信号重构的技术。
或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。
压缩感知跳过了采集N个样本这一步骤，直接获得压缩的信号的表示。
CS理论利用到了许多自然信号在特定的基Ψ上具有紧凑的表示。
即这些信号是“稀疏”的或“可压缩”的。
由于这一特性，压缩感知理论的信号编解码框架和传统的压缩过程大不一样，主要包括三个方面：（1）信号的稀疏表示；（2）设计测量矩阵，要在降低维数的同时保证原始信号x的信息损失最小；（3）设计信号恢复算法，利用M个观测值无失真地恢复出长度为N的原始信号。
压缩感知（Compressed Sensing）是一种通过测量和重建稀疏或可压缩信号的技术。
Orthogonal Matching Pursuit (OMP) 是一种贪婪算法，用于求解稀疏表示问题。
以下是一个使用MATLAB 实现OMP 算法的基本示例：matlabfunction x_rec = omp(A, b, K)# 输入: 矩阵A, 观测向量b, 稀疏度K# 输出: 重建向量x_rec# 计算矩阵A 的列的范数norm_A = norm(A, 2);# 初始化索引集和残差support = [];residual = b;# OMP 循环for iter = 1:K# 计算列的系数coef = A' * residual;# 找到具有最大系数的列的索引[~, index] = max(abs(coef));# 将该索引添加到支持集中support = [support, index];# 通过支持集更新残差x_support = A(:, support);x_rec = pinv(x_support) * b;residual = b - A(:, support) * x_rec;endend注意：这个函数需要输入一个矩阵A，一个观测向量b，以及稀疏度K。
A 是测量矩阵，通常是一个随机高斯矩阵或随机二进制矩阵。
b 是观测向量，即A*x，其中x 是需要重建的信号。
K 是信号的稀疏度，即非零元素的数量。
函数的输出是重建的信号x_rec。
注意：这是一个非常基础的实现，实际应用中可能需要添加更多的功能和优化，例如错误处理，超参数选择等。
clc;clear%% 1. 时域测试信号生成%产生长度为N=256的稀疏信号，其稀疏度K=23且这23个非零值随机分布于信号256个位置%观测向量y的长度M=80，即采样率M/N=0.3N=256;K=23;M=80;x = zeros(N,1);q = randperm(N);x(q(1:K)) =randn(K,1); %原始信号%% 2. 测量矩阵及观测值获得Phi=randn(M,N); %测量矩阵% 感知矩阵（高斯分布白噪声）M*NmatrixNorm = Phi.'*Phi;matrixNorm = sqrt(diag(matrixNorm)).';Phi = Phi./repmat(matrixNorm, [M,1]); %注意，观测矩阵是要归一化的，因为原子范数要是1！y=Phi*x ; %获得线性测量%% 3.用MP算法重构信号iterations=K; % 算法迭代次数(m>=K)%signal_reconstruct=zeros(1,1); % 近似解矩阵(初始值为空矩阵)r_n=y; % 残差值M*1x_rec=zeros(N,1);for times=1:iterationsfor col=1:N %感知矩阵的所有列向量innerpro(col)=Phi(:,col)'*r_n; %计算余量和感知矩阵每一列的内积end[val,pos]=max(abs(innerpro) ); %找出内积中绝对值最大的元素和它的对应的感知矩阵的列posx_rec(pos)=x_rec(pos)+innerpro(pos); %计算新的近似x_recr_n=r_n-innerpro(pos)*Phi(:,pos); %更新残差endnorm(x_rec-x)/norm(x) % 重构误差subplot(3,1,1);plot(x);title('origin');subplot(3,1,2);plot(x_rec);title('reconstruct');subplot(3,1,3);plot(r_n);title('残差');附录B OMP算法重构一维信号代码clc;clear%% 1. 时域测试信号生成K=7; % 稀疏度(做FFT可以看出来)N=256; % 信号长度M=64; % 测量数(M>=K*log(N/K),至少40,但有出错的概率)f1=50; % 信号频率1f2=100; % 信号频率2f3=200; % 信号频率3f4=400; % 信号频率4fs=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. 正交匹配追踪法重构信号(本质上是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; % 纪录最大投影系数的位置endhat_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) % 重构误差附录C OMP算法重构二维信号代码function Wavelet_OMPclc;clear% 读文件X=imread('D:\MATLAB\omp\lena256.bmp');X=double(X);[a,b]=size(X);% 小波变换矩阵生成ww=DWT(a);% 小波变换让图像稀疏化(注意该步骤会耗费时间，但是会增大稀疏度)X1=ww*sparse(X)*ww';X1=full(X1);% 随机矩阵生成M=190;R=randn(M,a);% 测量Y=R*X1;% OMP算法X2=zeros(a,b); % 恢复矩阵for i=1:b % 列循环rec=omp(Y(:,i),R,a);X2(:,i)=rec;end% 原始图像figure(1);imshow(uint8(X));title('原始图像');% 变换图像figure(2);imshow(uint8(X1));title('小波变换后的图像');% 压缩传感恢复的图像figure(3);X3=ww'*sparse(X2)*ww; % 小波反变换X3=full(X3);imshow(uint8(X3));title('恢复的图像');% 误差(PSNR)errorx=sum(sum(abs(X3-X).^2)); % MSE误差psnr=10*log10(255*255/(errorx/a/b)) % PSNR% OMP的函数% s-测量；T-观测矩阵；N-向量大小function hat_y=omp(s,T,N)Size=size(T); % 观测矩阵大小M=Size(1); % 测量hat_y=zeros(1,N); % 待重构的谱域(变换域)向量Aug_t=[]; % 增量矩阵(初始值为空矩阵)r_n=s; % 残差值for times=1:M/4; % 迭代次数(稀疏度是测量的1/4) 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; % 纪录最大投影系数的位置if (norm(r_n)<9) % 残差足够小break;endendhat_y(pos_array)=aug_y; % 重构的向量function ww=DWT(N)% 构造正交小波变换矩阵，图像大小N*N，N=2^P，P是整数。
[h,g]= wfilters('sym8','d'); % 分解低通和高通滤波器% N=256; % 矩阵维数(大小为2的整数幂次)L=length(h); % 滤波器长度rank_max=log2(N); % 最大层数rank_min=double(int8(log2(L)))+1; % 最小层数ww=1; % 预处理矩阵% 矩阵构造for jj=rank_min:rank_maxnn=2^jj;% 构造向量p1_0=sparse([h,zeros(1,nn-L)]);p2_0=sparse([g,zeros(1,nn-L)]);% 向量圆周移位for ii=1:nn/2p1(ii,:)=circshift(p1_0',2*(ii-1))';p2(ii,:)=circshift(p2_0',2*(ii-1))';end% 构造正交矩阵w1=[p1;p2];mm=2^rank_max-length(w1);w=sparse([w1,zeros(length(w1),mm);zeros(mm,length(w1)),eye(mm,mm)]);ww=ww*w;clear p1;clear p2;end。
