SAMP论文学习

SAMP:稀疏度自适应匹配追踪

实际应用中信号通常是可压缩的而不一定为稀疏的,而且稀疏信号的稀疏度我们通常也会不了解的。论文中提到过高或者过低估计了信号的稀疏度,都会对信号的重构造成影响。如果过低估计了稀疏度,会影响重构的质量;而过高估计稀疏度会对算法的准确性和鲁棒性造成影响。

论文在第2部分review了现有的压缩感知重构方法的框架。如下所示:

在一部分中论文提出了两种方式:自上而下、自下而上。对这两个词还不是很理解,对论文的第2部分进行翻译如下:

在第k次迭代中,rk代表残差,Fk代表估计信号的支撑集(finalist),Ck对应的是SP/CoSAMP算法的候选集。其中,OMP、STOMP以及ROMP算法采用是自下而上的方法,循序增加x的支撑集。相比通过逐次迭代增加支撑集的方法,SP和CoSAMP采用的是自上而下的方法进行迭代优化。

如图(a)所示,OMP和StOMP算法只用了一次检测。(b)中ROMP用了两次检测来增加一个或者多个原子进入支撑集。OMP算法在每次迭代中采用计算最大内积的方法来增加支撑集,每次迭代中只有一个原子被选择。StOMP算法通过匹配滤波器以及硬阈值的方法来选择进入支撑集的原子。对于ROMP来说,采用了两次检测,第一次检测与StOMP算法相似,第二次的选择选择依据是原子相关性大小至多不超过某个原子的两倍。在这些自下而上的重构方法中,在每次迭代的最后,支撑集是结合之前迭代中的集合与此次迭代中所选择的原子所构成的。迭代后的残差是由上次的残差减去观测向量在支撑集中的原子构成的子空间上的投影得到的,这一步也称为正交化过程,保证每次迭代后的残差与支撑集的原子正交。

以SP和CoSAMP为代表的自上而下的重构方法也采用了两次不用的选择方法来更新支撑集,但是他们的支撑集大小是固定的(等于输入信号的稀疏度K)。第一次原则的选择方法与ROMP极其相似,而第二次检测更加可靠、准确。在第一次检测之后,通过结合上一次所选择的原子集合和此次选择的原子,形成候选集。求解最小二乘问题得到的前K个最大值所对应候选集中的原子即为所需的支撑集。与上述所说明的自下而上的重构方法最大的不同之处在于加入了回溯,能移除之前迭代过程中错误选择的原子。并且只有SP和CoSaMP方法具有与BP(L1优化)相似的理论支持,此外,它们在观测不准确或者是信号不严格稀疏的情况下也同样适用。

在论文的第3部分提出了SAMP算法,框架和伪代码截图如下:

可看成不同之处在于集合的大小不是固定的,而是可自适应变化的。

摘取博客中所翻译的算法流程:

在伪代码之后论文还进行了迭代终止条件和步长大小选择的讨论。SAMP综合了上述两种方法的优点。

在仿真实验中,对高斯信号和二进制信号重构的效果不同,如下文所示,SAMP依赖于所选用的步长和信号的类型

代码部分不再赘述,可参考文献[2]中的代码,附出SAMP算法的代码如下:

function [xr, iter_num] =SAMP(y, Phi, step_size, sigma)
% SAMP: Sparsity Adaptive Matching Pursuit algoritm for compressed sensing.
% For theoretical analysis, please refer to the paper :
% Thong. T. Do, Lu Gan and Trac D. Tran ,"Sparsity Adaptive Matching
% Purusit for practical compressed sensing" available at http://dsp.ece.rice.edu/cs
% Written by Thong Do(thongdo@jhu.edu)
% Updated on July, 26th 2008
% parameter usage:
%   y: Mx1 observation vector
%   Phi: MxN measurement matrix
%   step_size: any positive integer value not larger than sparsity
%   sigma: noise energy when sensing
%   xr: reconstructed sparse signal
%   iter_num: number of iterations
% Initialization
iter_num = 0;
actset_size = step_size;
active_set = [];
res = y;
stg_idx = 1; % stage index
while (norm(res)>sigma)
    % candidate list
    [val, idx] = sort(abs(Phi'*res), 'descend');       
    candidate_set = union(active_set, idx(1:actset_size));
    % finalist
    [val, idx] = sort(abs(pinv(Phi(:,candidate_set))*y), 'descend');
    new_active_set = candidate_set(idx(1:actset_size));
    new_res = y-Phi(:,new_active_set)*pinv(Phi(:,new_active_set))*y;
    if (norm(new_res) >= norm(res))  
        % shift into a new stage
        stg_idx = stg_idx + 1;
        actset_size = stg_idx*step_size;
      
    else         
        % update residual and active set   
        res = new_res;
        active_set= new_active_set;
       
    end
   
    iter_num = iter_num +1;                        %while的次数
end % loop
% reconstruction
N = size(Phi,2);
xr = zeros(N,1);
xr_active_set = pinv(Phi(:,active_set))*y;
xr(active_set) = xr_active_set;

参考文献:

[1]Thong T.Do,Lu Gan,NamNguyen,Trac D.Tran.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C].AsilomarConference on Signals,Systems,andComputers,Pacific Grove,California,2008,10:581-587.

[2] 彬彬有礼.压缩感知重构算法之稀疏度自适应匹配追踪(SAMP),http://blog.csdn.net/jbb0523/article/details/45690421

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

解决多标签分类问题(包括案例研究)

由于某些原因,回归和分类问题总会引起机器学习领域的大部分关注。多标签分类在数据科学中是一个比较令人头疼的问题。在这篇文章中,我将给你一个直观的解释,说明什么是多...

7826
来自专栏CVPy

OpenCV 玩九宫格数独(二):knn 数字识别

我们现在要做的是要识别从九宫格图片中提取出来的印刷体的数字。本文从零开始做一遍数字识别,展示了数字识别的完整流程。从收集数据开始,到数据预处理,再到训练KNN,...

2.3K2
来自专栏IT派

教程 | 用TensorFlow Estimator实现文本分类

本文选自介绍 TensorFlow 的 Datasets 和 Estimators 模块系列博文的第四部分。读者无需阅读所有之前的内容,如果想重温某些概念,可以...

1673
来自专栏人工智能头条

LSTM实现详解

2303
来自专栏从流域到海域

Python机器学习中的特征选择

原文地址:https://machinelearningmastery.com/feature-selection-machine-learning-pytho...

1.7K7

TensorFlow中生成手写笔迹的Demo

这项操作现在在github上已经可以使用了。

5167
来自专栏大数据挖掘DT机器学习

【kaggle实战】从KNN,LR,SVM,RF到深度学习

@蜡笔小轩V 原文:http://blog.csdn.net/Dinosoft/article/details/50734539 纸上得来终觉浅,还是要多实践...

1.1K6
来自专栏用户2442861的专栏

卷积神经网络CNN经典模型整理Lenet,Alexnet,Googlenet,VGG,Deep Residual Learning

欢迎转载,转载请注明:本文出自Bin的专栏blog.csdn.net/xbinworld。  技术交流QQ群:433250724,欢迎对算法、技术感兴趣的同...

2341
来自专栏专知

【论文推荐】最新五篇视频分类相关论文—细粒度行人识别、群组归一化、MLtuner、时序特征

1803
来自专栏FreeBuf

基于机器学习的web异常检测

Web防火墙是信息安全的第一道防线。随着网络技术的快速更新,新的黑客技术也层出不穷,为传统规则防火墙带来了挑战。传统web入侵检测技术通过维护规则集对入侵访问进...

7465

扫码关注云+社区

领取腾讯云代金券