压缩感知重构算法之子空间追踪(SP)

2023-10-07 18:10

本文主要是介绍压缩感知重构算法之子空间追踪(SP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:压缩感知重构算法之子空间追踪(SP)

转载自彬彬有礼的专栏

        如果掌握了压缩采样匹配追踪(CoSaMP)后,再去学习子空间追踪(Subspace Pursuit)是一件非常简单的事情,因为它们几乎是完全一样的。

        SP的提出时间比CoSaMP提出时间略晚,首个论文版本是参考文献[1],后来更新了两次,最后在IEEE Transactions on Information Theory发表[2]。从算法角度来讲,SP与CoSaMP差别非常小,这一点作者也意识到了,在文献[1]首页的左下角就有注释:

在文献[2]第2页提到了SP与CoSaMP的具体不同:

从上面可以知道,SP与CoSaMP主要区别在于“Ineach iteration, in the SP algorithm, only K new candidates are added, while theCoSAMP algorithm adds 2K vectors.”,即SP每次选择K个原子,而CoSaMP则选择2K个原子;这样带来的好处是“This makes the SP algorithm computationally moreefficient,”。

        以下是文献[2]中的给出的SP算法流程:

这个算法流程的初始化(Initialization)其实就是类似于CoSaMP的第1次迭代,注意第(1)步中选择了K个原子:“K indices corresponding to the largest magnitude entries”,在CoSaMP里这里要选择2K个最大的原子,后面的其它流程都一样。这里第(5)步增加了一个停止迭代的条件:当残差经过迭代后却变大了的时候就停止迭代。

        不只是SP作者认识到了自己的算法与CoSaMP的高度相似性,CoSaMP的作者也同样关注到了SP算法,在文献[3]中就提到:

文献[3]是CoSaMP原始提出文献的第2个版本,文献[3]的早期版本[4]是没有提及SP算法的。

        鉴于SP与CoSaMP如此相似,这里不就再单独给出SP的步骤了,参考《压缩感知重构算法之压缩采样匹配追踪(CoSaMP)》,只需将第(2)步中的2K改为K即可。

        引用文献[5]的3.5节中的几句话:“贪婪类算法虽然复杂度低运行速度快,但其重构精度却不如BP类算法,为了寻求复杂度和精度更好地折中,SP算法应运而生”,“SP算法与CoSaMP算法一样其基本思想也是借用回溯的思想,在每步迭代过程中重新估计所有候选者的可信赖性”,“SP算法与CoSaMP算法有着类似的性质与优缺点”。

        子空间追踪代码可实现如下(CS_SP.m),通过对比可以知道该程序与CoSaMP的代码基本完全一致。本代码未考虑文献[2]中的给出的SP算法流程的第(5)步。代码可参见参考文献[6]中的Demo_CS_SP.m。

[plain] view plain copy
print ?
  1. function [ theta ] = CS_SP( y,A,K )  
  2. %CS_SP Summary of this function goes here  
  3. %Version: 1.0 written by jbb0523 @2015-05-01  
  4. %   Detailed explanation goes here  
  5. %   y = Phi * x  
  6. %   x = Psi * theta  
  7. %   y = Phi*Psi * theta  
  8. %   令 A = Phi*Psi, 则y=A*theta  
  9. %   K is the sparsity level  
  10. %   现在已知y和A,求theta  
  11. %   Reference:Dai W,Milenkovic O.Subspace pursuit for compressive sensing  
  12. %   signal reconstruction[J].IEEE Transactions on Information Theory,  
  13. %   2009,55(5):2230-2249.  
  14.     [y_rows,y_columns] = size(y);  
  15.     if y_rows<y_columns  
  16.         y = y';%y should be a column vector  
  17.     end  
  18.     [M,N] = size(A);%传感矩阵A为M*N矩阵  
  19.     theta = zeros(N,1);%用来存储恢复的theta(列向量)  
  20.     Pos_theta = [];%用来迭代过程中存储A被选择的列序号  
  21.     r_n = y;%初始化残差(residual)为y  
  22.     for kk=1:K%最多迭代K次  
  23.         %(1) Identification  
  24.         product = A'*r_n;%传感矩阵A各列与残差的内积  
  25.         [val,pos]=sort(abs(product),'descend');  
  26.         Js = pos(1:K);%选出内积值最大的K列  
  27.         %(2) Support Merger  
  28.         Is = union(Pos_theta,Js);%Pos_theta与Js并集  
  29.         %(3) Estimation  
  30.         %At的行数要大于列数,此为最小二乘的基础(列线性无关)  
  31.         if length(Is)<=M  
  32.             At = A(:,Is);%将A的这几列组成矩阵At  
  33.         else%At的列数大于行数,列必为线性相关的,At'*At将不可逆  
  34.             break;%跳出for循环  
  35.         end  
  36.         %y=At*theta,以下求theta的最小二乘解(Least Square)  
  37.         theta_ls = (At'*At)^(-1)*At'*y;%最小二乘解  
  38.         %(4) Pruning  
  39.         [val,pos]=sort(abs(theta_ls),'descend');  
  40.         %(5) Sample Update  
  41.         Pos_theta = Is(pos(1:K));  
  42.         theta_ls = theta_ls(pos(1:K));  
  43.         %At(:,pos(1:K))*theta_ls是y在At(:,pos(1:K))列空间上的正交投影  
  44.         r_n = y - At(:,pos(1:K))*theta_ls;%更新残差   
  45.         if norm(r_n)<1e-6%Repeat the steps until r=0  
  46.             break;%跳出for循环  
  47.         end  
  48.     end  
  49.     theta(Pos_theta)=theta_ls;%恢复出的theta  
  50. end  
function [ theta ] = CS_SP( y,A,K )
%CS_SP Summary of this function goes here
%Version: 1.0 written by jbb0523 @2015-05-01
%   Detailed explanation goes here
%   y = Phi * x
%   x = Psi * theta
%	y = Phi*Psi * theta
%   令 A = Phi*Psi, 则y=A*theta
%   K is the sparsity level
%   现在已知y和A,求theta
%   Reference:Dai W,Milenkovic O.Subspace pursuit for compressive sensing
%   signal reconstruction[J].IEEE Transactions on Information Theory,
%   2009,55(5):2230-2249.[y_rows,y_columns] = size(y);if y_rows<y_columnsy = y';%y should be a column vectorend[M,N] = size(A);%传感矩阵A为M*N矩阵theta = zeros(N,1);%用来存储恢复的theta(列向量)Pos_theta = [];%用来迭代过程中存储A被选择的列序号r_n = y;%初始化残差(residual)为yfor kk=1:K%最多迭代K次%(1) Identificationproduct = A'*r_n;%传感矩阵A各列与残差的内积[val,pos]=sort(abs(product),'descend');Js = pos(1:K);%选出内积值最大的K列%(2) Support MergerIs = union(Pos_theta,Js);%Pos_theta与Js并集%(3) Estimation%At的行数要大于列数,此为最小二乘的基础(列线性无关)if length(Is)<=MAt = A(:,Is);%将A的这几列组成矩阵Atelse%At的列数大于行数,列必为线性相关的,At'*At将不可逆break;%跳出for循环end%y=At*theta,以下求theta的最小二乘解(Least Square)theta_ls = (At'*At)^(-1)*At'*y;%最小二乘解%(4) Pruning[val,pos]=sort(abs(theta_ls),'descend');%(5) Sample UpdatePos_theta = Is(pos(1:K));theta_ls = theta_ls(pos(1:K));%At(:,pos(1:K))*theta_ls是y在At(:,pos(1:K))列空间上的正交投影r_n = y - At(:,pos(1:K))*theta_ls;%更新残差 if norm(r_n)<1e-6%Repeat the steps until r=0break;%跳出for循环endendtheta(Pos_theta)=theta_ls;%恢复出的theta
end
        鉴于SP与CoSaMP的极其相似性,这里就不再给出单次重构和测量数M与重构成功概率关系曲线绘制例程代码了,只需将CoSaMP中调用CS_CoSaMP函数的部分改为调用CS_SP即可,无须任何其它改动。这里给出对比两种重构算法所绘制的测量数M与重构成功概率关系曲线的例程代码,只有这样才可以看出两种算法的重构性能优劣,以下是在分别运行完SP与CoSaMP的测量数M与重构成功概率关系曲线绘制例程代码的基础上,即已经存储了数据CoSaMPMtoPercentage1000.mat和SPMtoPercentage1000.mat:
[plain] view plain copy
print ?
  1. clear all;close all;clc;  
  2. load CoSaMPMtoPercentage1000;  
  3. PercentageCoSaMP = Percentage;  
  4. load SPMtoPercentage1000;  
  5. PercentageSP = Percentage;  
  6. S1 = ['-ks';'-ko';'-kd';'-kv';'-k*'];  
  7. S2 = ['-rs';'-ro';'-rd';'-rv';'-r*'];  
  8. figure;  
  9. for kk = 1:length(K_set)  
  10.     K = K_set(kk);  
  11.     M_set = 2*K:5:N;  
  12.     L_Mset = length(M_set);  
  13.     plot(M_set,PercentageCoSaMP(kk,1:L_Mset),S1(kk,:));%绘出x的恢复信号  
  14.     hold on;      
  15.     plot(M_set,PercentageSP(kk,1:L_Mset),S2(kk,:));%绘出x的恢复信号  
  16. end  
  17. hold off;  
  18. xlim([0 256]);  
  19. legend('CoSaK=4','SPK=4','CoSaK=12','SPK=12','CoSaK=20',...  
  20.     'SPK=20','CoSaK=28','SPK=28','CoSaK=36','SPK=36');  
  21. xlabel('Number of measurements(M)');  
  22. ylabel('Percentage recovered');  
  23. title('Percentage of input signals recovered correctly(N=256)(Gaussian)');  
clear all;close all;clc;
load CoSaMPMtoPercentage1000;
PercentageCoSaMP = Percentage;
load SPMtoPercentage1000;
PercentageSP = Percentage;
S1 = ['-ks';'-ko';'-kd';'-kv';'-k*'];
S2 = ['-rs';'-ro';'-rd';'-rv';'-r*'];
figure;
for kk = 1:length(K_set)K = K_set(kk);M_set = 2*K:5:N;L_Mset = length(M_set);plot(M_set,PercentageCoSaMP(kk,1:L_Mset),S1(kk,:));%绘出x的恢复信号hold on;    plot(M_set,PercentageSP(kk,1:L_Mset),S2(kk,:));%绘出x的恢复信号
end
hold off;
xlim([0 256]);
legend('CoSaK=4','SPK=4','CoSaK=12','SPK=12','CoSaK=20',...'SPK=20','CoSaK=28','SPK=28','CoSaK=36','SPK=36');
xlabel('Number of measurements(M)');
ylabel('Percentage recovered');
title('Percentage of input signals recovered correctly(N=256)(Gaussian)');

        运行结果如下:

        可以发现在M较小时SP略好于CoSaMP,当M变大时二者重构性能几乎一样。

 参考文献:

[1]Dai W,Milenkovic O. Subspace pursuitfor compressive sensing: Closing the gap between performance and complexity.http://arxiv.org/pdf/0803.0811v1.pdf

[2]Dai W,Milenkovic O.Subspacepursuit for compressive sensing signal reconstruction[J].IEEETransactions on Information Theory,2009,55(5):2230-2249.

[3]D. Needell, J.A. Tropp.CoSaMP: Iterative signal recoveryfrom incomplete and inaccurate samples. http://arxiv.org/pdf/0803.2392v2.pdf

[4]D. Needell, J.A. Tropp.CoSaMP: Iterative signal recoveryfrom incomplete and inaccurate samples. http://arxiv.org/pdf/0803.2392v1.pdf

[5]杨真真,杨震,孙林慧.信号压缩重构的正交匹配追踪类算法综述[J]. 信号处理,2013,29(4):486-496.

[6]Li Zeng. CS_Reconstruction. http://www.pudn.com/downloads518/sourcecode/math/detail2151378.html

这篇关于压缩感知重构算法之子空间追踪(SP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/159540

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

查看Oracle数据库中UNDO表空间的使用情况(最新推荐)

《查看Oracle数据库中UNDO表空间的使用情况(最新推荐)》Oracle数据库中查看UNDO表空间使用情况的4种方法:DBA_TABLESPACES和DBA_DATA_FILES提供基本信息,V$... 目录1. 通过 DBjavascriptA_TABLESPACES 和 DBA_DATA_FILES

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

SpringBoot项目注入 traceId 追踪整个请求的日志链路(过程详解)

《SpringBoot项目注入traceId追踪整个请求的日志链路(过程详解)》本文介绍了如何在单体SpringBoot项目中通过手动实现过滤器或拦截器来注入traceId,以追踪整个请求的日志链... SpringBoot项目注入 traceId 来追踪整个请求的日志链路,有了 traceId, 我们在排

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1