精华内容
下载资源
问答
  • 学习分布式压缩感知必读的文献,描述了分布式压缩感知的稀疏模型和重构算法
  • 分布式压缩感知简介

    千次阅读 2019-03-12 22:20:22
    分布式压缩感知是针对多个传感器对多个信号进行压缩感知的情景,令每个传感器独立对信号进行测量,然后基于测量结果,综合利用信号内部以及信号之间的关联结构实现稀疏信号的恢复。 分布式压缩感知有一个大前提:...

    什么是分布式?

    分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。其目的是利用更多的机器,处理更多的数据。

    什么是分布式压缩感知?

    分布式压缩感知是针对多个传感器对多个信号进行压缩感知的情景,令每个传感器独立对信号进行测量,然后基于测量结果,综合利用信号内部以及信号之间的关联结构实现稀疏信号的恢复。

     

    分布式压缩感知有一个大前提:原始信号之间具有联合稀疏性

    针对此大前提,文章Distributed compressed sensing提出了三个联合稀疏模型(JSM),以下分别介绍。

     

    JSM1-Model-Sparse common component + innovations 

    JSM1模型,文献中是这么描述的,所有信号都拥有一个共同成分(common sparse component)和一个特有成分(innovation component)并以表达式的形式给出,其中Zc经过变换基底变得稀疏,稀疏度为Kc,同理,Zj经过变换基底变得稀疏,稀疏度为Kj,这里注意共同成分和特有成分均在同一个基底下稀疏。

    JSM-1建模的实际情况是一组传感器,全天测量多个室外位置的温度。 温度读数xj具有时间(信号内)和空间(信号间)相关性。 全局因素,例如太阳和盛行风,可能会产生影响zC,这对所有传感器都是通用的,并且结构足以允许稀疏表示。 更多的局部因素,如阴影,水或动物,可以促进局部创新zj,也是结构化(因此稀疏)。 对于记录光强度,气压或其他现象的传感器网络,可以设想类似的情况。 所有这些场景都对应于测量在时间和空间上平滑变化的物理过程的属性,因此是高度相关的。

     

     

    JSM2Model-Common sparse supports 

    相较于JSM1模型,JSM2模型中的信号并没有公共分量

    由JSM-2良好建模的实际情况是多个传感器获取相同傅里叶稀疏信号的复制品,但具有由信号传播引起的相移和衰减。 在许多情况下,恢复每个感测信号是至关重要的,例如在许多声学定位和阵列处理算法中。 JSM-2的另一个有用的应用是MIMO通信。

     

     

    JSM3Model-Nonsparsecommon component + sparse innovations 

    JSM3是JSM1的的扩展,其中JSM1要求共同成分是稀疏的,而JSM3则放松了此约束。

    由JSM-3良好建模的实际情况是,不同传感器记录了几个源,并且背景信号在任何基础上都不稀疏。例如摄像机获取生产线中组件的快照; 然后,计算机系统检查设备中的故障以用于质量控制目的。 虽然每个图像可能非常复杂,但是图像的集合将是高度相关的,因为每个相机正在观察具有微小(稀疏)变化的相同设备。

    总结:

    1.JSM-1模型:共有成分和特有成分均是稀疏的

    2.JSM-2模型:共有成分为0,特有成分是稀疏的,且稀疏度相同,均为K,非零元素的位置也相同,仅仅取值不同。

    3.JSM-3模型:共有成分非稀疏,但特有成分是稀疏的。

    展开全文
  • 基于回溯的分布式压缩感知匹配追踪方法
  • 针对MIMO系统信道的联合稀疏特性,提出一种基于分布式压缩感知(DCS)的MIMO-OFDM系统信道估计方法。分布式压缩感知(DCS)被视为分布式信源编码和压缩感知(CS)的结合,论文详细论证了分布式压缩感知理论在MIMO-OFDM...
  • 利用视频非局部相似性的分布式压缩感知重构
  • 基于分布式压缩感知的H.264帧间编码
  • 根据分布式压缩感知理论,提出一种宽带协作频谱感知的方式。该方式相比于以往的协作压缩频谱感知方式,认知用户传向融合中心的数据精简为压缩信号,各个压缩信号在融合中心进行融合重构,这样就减少传向融合中心的数据量...
  • 基于分布式压缩感知的宽带欠定信号DOA估计
  • 一种新的基于分布式压缩感知的时变稀疏信道估计
  • 针对上述问题,提出一种结合分布式压缩感知理论的信道估计导频优化方案。首先,根据时延域中无线信道的稀疏特性挖掘基函数系数之间的联合稀疏性并对估计方程进行去耦处理。接着,引入分布式压缩感知理论,获得一种...
  • 对此,提出一种应用于 多基雷达系统的基于分布式压缩感知的联合检测与跟踪算法.首先,应用分布式紧凑感知 矩阵追踪算法直接重构出表征目标状态空间信息的稀疏网格反射向量;然后,应用检测 前跟踪算法得到精确的目标运动...
  • 基于分布式压缩感知的无线传感器网络异常数据处理.pdf
  • 基于分布式压缩感知理论,利用高光谱图像谱间的低秩特性,提出一种高光谱图像分布式压缩感知重构方法。该方法在编码端对各谱段图像分别进行压缩感知测量,运算简单,便于硬件实现。解码端重构时,首先对各谱段图像...
  • 综合考虑到视频序列本身的不同特性以及时空相关性,将传统视频编码中的多假设预测运动估计思想引入到分布式压缩感知视频编码系统中,提出一种新的基于时空相关性的分布式压缩感知多假设预测重构算法。在编码端增加CS...
  • DCS_SOMP分布式压缩感知

    热门讨论 2013-12-12 17:22:35
    DCS_SOMP分布式压缩感知 根据 CS 理论可知,在信号长度一定的情况下, 稀疏度越好,所需的测量值个数越少。对于一个信号群,选择不同的共同分量会有不同的联合稀疏效果。如果能够知道每个节点采集到的信号,那么可以...
  • 在差值信号稀疏模型的基础上, 提出了一种适用于该模型的分布式压缩感知算法, 该算法能够在节点间不通信的情况下实现对差值信号的编码。仿真结果表明, 与单独重构相比, 提出的算法可以用更少的观测值联合重构出信号群...
  • 分布式压缩感知的基础向内容梳理写在前面的一点废话OMP与SOMP内容梳理目前遇到的一些问题OMP算法流程DCS-SOMP算法流程 写在前面的一点废话     在经历了传统数据稀疏这个硬骨头之后,我发现我自己太想当然了,...

    写在前面的一点废话

        
    2020年4月27日的一点感想:
        在经历了传统数据稀疏这个硬骨头之后,我发现我自己太想当然了,有些事情想的太过于简单了,我要做的事情是我自己选的,真的要摆正心态,不能着急!本人才疏学浅,能力有限,有误之处还望不吝指教。
        
    2020年5月1日的一点感想:
        感觉自己就像是一个有坏道的硬盘,跑不起来最高的速度,有些东西存进去了就拿不出来,一点一点的修复,一点一点的补上坏的地方。
        

    OMP与SOMP内容梳理

    目前遇到的一些问题

        目前我做了对原始信号的稀疏度分析、对小波变换后的信号做了观测和重构,信号本身的特性发掘不出来,多路重构仅在重构所需数据量上与单路有所下降,并无大的创新。完成了OMP单路算法的重构;DCS-SOMP多路联合重构的完整过程。整个实验中缺少其他算法的对照组;缺少创新性;对于符合原始信号特性的联合稀疏不明确。
        以下,准备从寻找信号特性的联合稀疏和联合重构算法两个方面入手,首先先梳理一下现在的一些算法流程,巩固一下,也便于后续文字叙述直接使用。

    明确几个概念

    何为内积?

        此处的内积是指向量之间的数量积,几何意义是一个向量投影在另一个向量上的大小,在代数计算上就是向量A=(x1,y1),向量B=(x2,y2),A与B的内积写做A·B=x1*x2+y1*y2,若引申到N维则是x1x2…xn+y1*y2…yn,多个向量相互做内积也是如此。
        几何空间上A·B=|A||B|cosθ.
        内积可以表示两个向量之间的相关趋势,两个向量垂直则内积为0,两个向量平行内积为1,所以在迭代过程中通过传感矩阵与各列残差的内积来选出一个最大值,作为最相关的依据,此处后面详细说明。

    何为投影?

         从二维角度上来说,我们常见的投影就是在这里插入图片描述
    当然一般的投影是位于坐标轴上的,在此处我们要说明的是一个向量 bb 在向量 aa 上的投影向量 pp
    在这里插入图片描述
    显然 ppaa 上,所以 p=xap=xappxx 倍的 aa bb点与pp点之间会存在一个误差e=bpe=b-p,且向量ee是垂直于aa向量的,由ppaa的列空间中的一个子空间,所以垂直于列空间的是左零空间,所以aTe=0a^Te=0成立,展开就是 aT(bxa)=0aTbaTxa=0x=aTbaTa a^T(b-xa)=0\quad \Rightarrow \quad a^Tb-a^Txa=0 \quad \Rightarrow \quad x= \frac{a^Tb}{ a^Ta }
    代入到 p=xap=xa 中,p=aaTbaTap=aaTaTabp=a\frac{a^Tb}{ a^Ta }\quad \Rightarrow \quad p=\frac{aa^T}{ a^Ta }b
    则可得到p=Pbp=Pb,也就是说bb乘了一个矩阵就变成了他的投影,所以我们称PP为投影矩阵。
    P=aaTaTaP=\frac{aa^T}{ a^Ta }

         当整个维度上升到2维以上时,就是说一个向量bb,投影于A矩阵各列张成的列空间中,对于此处参见线性代数数学基础中对于四个基本空间部分的论述。此时的投影矩阵P=A(ATA)1ATP=A(A^TA)^{-1}A^T一般来说A不一定是方阵,所以其也不可逆,故ATAA^TA为方阵才存在可不可逆的说法,这个式子中间也不可展开。

    何为最小二乘法?

        通俗但不严谨的讲,最小二乘法是一种拟合散点使生成的曲线与各个数据点之间误差的平法和最小的方法。是一种将非线性数据按线性拟合的方法 (此句可能有歧义)。
        举个例子说,现在在平面直角坐标系上有4个点,A(1,5)、B(2,7)、C(4,8)、D(5,10),想找一种方法来表示这4个点的变化趋势,此时我们设定yi=axi+b,将4个点分别代入
                                5=a+b;7=2a+b;8=4a+b;10=5a+b;
    此时我们想求得一组a和b使得上述4个式子均成立,但显然是不可能的,所以我们换种思路,使得没个点到拟合曲线的误差最小,设误差为   ε=Σ(y(xi)-yi(x))2=(a+b-5)2+(a2+b-7)2+(a4+b-8)2+(a*5+b-10)2
    此时获得了所有点与目标曲线之间的一个差值的平方,代表了每一个散点与目标曲线之间的绝对距离,如果这个距离最小,则说明我们的曲线到每一个点的距离都是最小的,即便不能穿过,但是可以依照整体的趋势划分。整理后得到了ε(a,b) 的表达式,对该式子,我们分别求取a,b的偏导数,导数表示一个函数的变化率,偏导数是当这个函数不止有一个自变量时每个自变量的变化趋势,所以如果想取误差的最小值,我们需要分别求取当ε关于a和关于b的偏导数,当一阶导数出现0时说明函数出现拐点,为极值点(此处仅考虑示例中的情况为极小值点)
    可列出两个式子:
    aε(a,b)bε(a,b) \frac{ \partial }{\partial a} ε(a,b) \qquad \frac{ \partial }{\partial b} ε(a,b)
    此时可以作为正常方程求解a和b,求出a=a1,b=b1即可求的一个式子y=a1x+b1,这个式子与各点的误差平方和最小,所以依据这种标准求取曲线的方法叫做最小二乘法。
        以上叙述的是最小二乘法在微积分代数领域中解超定方程组的一个示例,个人水平着实有限。。。不求严谨,但求叙述通俗。
        实际上我们在压缩感知中是要解欠定性方程组,同样的,可以用最小二乘法去拟合一个曲线,实现与目标点值的逼近,此处也涉及投影矩阵的概念。
        
        首先,我们确定一个要求解的问题是
    {y1=a1,1θ1+a1,2θ2+a1,3θ3y2=a2,1θ1+a2,2θ2+a2,3θ3 \left\{\begin{aligned} y_{1} & = & a_{1,1} \theta_{1}+a_{1,2} \theta_{2}+a_{1,3} \theta_{3} \\y_{2} & = & a_{2,1} \theta_{1}+a_{2,2} \theta_{2}+a_{2,3} \theta_{3} \end{aligned}\right.
    此方程由两个方程联立,具有3个未知数,系数矩阵为
    A=(a1,1a1,2a1,3a2,1a2,2a2,3)A=\begin{pmatrix} a_{1,1},a_{1,2},a_{1,3}\\ a_{2,1},a_{2,2},a_{2,3} \end{pmatrix}
    yy = AA θ\theta,使用最小二乘法求解该方程就是
    θ^=(ATA)1ATy\widehat \theta=(A^TA)^{-1}A^Ty
    最终可以获得一个近似的 θ^\widehat \theta 作为最优解即为所求,这个是在线性代数上做最小二乘。两者的联系见线性代数基础部分详解

    说明一下本文的符号体系

        此处是以压缩感知的常规形式给出,xxN*1 为原始信号,θ\thetaN*1为稀疏信号,yyM*1为观测信号,ϕ\phiM*N为观测矩阵,ψ\psiN*N稀疏矩阵,K为信号稀疏度,N为原始信号长度,M为观测信号长度,A为传感矩阵。
                                        yyM*1=ϕ\phiM*N θ\thetaN*1   A=ϕ\phiM*N ψ\psiN*N

    其中N>>M>K,ψ\psiN*N一般为正交矩阵,也就是ψ\psiHN*N = ψ\psi-1N*N
    后文中出现一些新符号时可能会就地解释。。。完善的时候再修改此处

    OMP算法流程

        OMP的意思是Orthogonal Matching Pursuit,正交匹配追踪。
        关于他的前世今生不多说,是一种经典算法,前身是MP算法,加入了正交的步骤是使得求解内积时为0,不再重复计算残差,加快了算法的收敛速度。
        OMP的算法输入部分:观测信号y,传感矩阵A,信号稀疏度K。
        OMP的算法输出部分:重构的估计稀疏向量 θ^\widehat{\theta} ,残差值 rrN*1。(这个rr中只含有k次迭代的残差)
        首先说明,OMP算法并不是专门应用于压缩感知重构信号的,他是一种用于解欠定性方程组的算法,其他的重构算法也都是在解决欠定性方程组的问题,如何在欠定性方程组中找到一个最优解,也就是l0范数的问题,此处我们先不谈l0范数的问题,单纯从算法角度出发,结合一些前述知识去看他的运行步骤和算法流程。

    1.  输入变量yyAA,K,已知 yyM*1=AAM*N θ\thetaN*1 ,我们要求解的问题就是在已知 yyAA 的基础上求 θ\theta,显然这是一个求解欠定方程的问题。因为θ\theta的维度大于yy的维度。设定一个残差 rr 作为求解的目标,迭代之初,我们与目标函数的残差就是 yy 本身,即 rr0=yy ( rr0的角标表示迭代次数 )要在迭代的过程中使残差最小,也就让我们拟合的 θ^\widehat{\theta} 更加接近于真实的 θ\theta。还需初始化一个序号索引集
                     (---------------------称该步骤为算法初始化过程---------------------)

    2.  取传感矩阵 AA每一列(共N列)分别与残差 (也是个列向量) 做内积,可以获得一个N维的向量,在此向量内寻找一个绝对值的大的项,也就是投影值最大的项,认为该列与目前的残差最为相关(属于个人理解,可能不严谨),记录下其位置序号以及 AA 中该序号列的数值。

    3.  将这一列数记做 aaMax 作为方程 yyM*1=(aaMaxM*1 θ\thetaN*1 中的系数,此时该式为一个欠定性方程组(通俗理解就是解的个数大于所联立方程的个数)此处不好理解可将aaMax这一列向量与θ\theta这一列向量展开,可以得到(y1y2...yM)=(a1,Maxa2,Max...aM,Max)(θ1θ2.θM.θN)={y1=a1,Maxθ1+a1,Maxθ2+...+a1,MaxθNy2=a2,Maxθ1+a2,Maxθ2+...+a2,MaxθN..yM=aM,Maxθ1+aM,Maxθ2+...+aM,MaxθN\begin{pmatrix} y_{1}\\ y_{2} \\ .\\.\\.\\y_{M}\end{pmatrix}=\begin{pmatrix}a_{1,Max}\\ a_{2,Max} \\ .\\.\\.\\a_{M,Max}\end{pmatrix}*\begin{pmatrix}\theta_{1}\\ \theta_{2} \\ .\\\theta_{M}\\.\\ \theta_{N}\end{pmatrix}= \left\{\begin{aligned} y_{1} & = & a_{1,Max} \theta_{1}+a_{1,Max} \theta_{2}+...+a_{1,Max} \theta_{N} \\y_{2} & = & a_{2,Max} \theta_{1}+a_{2,Max} \theta_{2}+...+a_{2,Max} \theta_{N} \\.\\. \\y_{M} & = & a_{M,Max} \theta_{1}+a_{M,Max} \theta_{2}+...+a_{M,Max} \theta_{N} \end{aligned}\right.
    也就变成了(y1y2...yM)=(a1,Maxa2,Max...aM,Max)θ1+(a1,Maxa2,Max...aM,Max)θ2+...(a1,Maxa2,Max...aM,Max)θN\begin{pmatrix} y_{1}\\ y_{2} \\ .\\.\\.\\y_{M}\end{pmatrix}= \begin{pmatrix}a_{1,Max}\\ a_{2,Max} \\ .\\.\\.\\a_{M,Max}\end{pmatrix} \theta_{1}+\begin{pmatrix}a_{1,Max}\\ a_{2,Max} \\ .\\.\\.\\a_{M,Max}\end{pmatrix}\theta_{2}+...\begin{pmatrix}a_{1,Max}\\ a_{2,Max} \\ .\\.\\.\\a_{M,Max}\end{pmatrix}\theta_{N}
    通过前述所说的最小二乘法求解(aaMaxT.aaMax)-1aaMaxTyy= θ^\widehat{\theta}

    4.  该 θ^\widehat{\theta}为这一次迭代过程的结果,我们认为这个θ^\widehat{\theta}是当前的一个最优解,并用他重新求取
    y^=Aθ^\widehat{y}=A_{索引列的集合}\widehat{\theta} AΩ就是A_{\Omega},随着迭代次数增加,AΩA_{\Omega}的列数在不断扩大。将y^\widehat{y} 与原值yy做差,作为更新残差 (rr1)=yy^y-\widehat{y}。此处可以判断残差是否符合要求精度,如果不符合将该残差继续代入步骤2中,迭代次数是输入的稀疏度,最多重构稀疏度K个。
    (PS:但此时随着迭代次数的增加,aaMax的列数在不断增多,每迭代一次,就增加一列,相当于在保留了原有趋势的基础上加入修正余项,θ\theta的行数也随着迭代次数的增加不断增加,最终aaMax会变成一个M行K列的矩阵,依旧是一个扁矩阵,前述说过M>K,θ^\widehat{\theta}会变成一个K行的列向量,这个地方是我本人最开始理解的不好的地方,主要是数学底子太薄弱。。。)
    重复 2、3、4 过程,不断更新残差,最终获得K个残差值。
                     (---------------------称以上步骤为算法贪婪迭代过程过程---------------------)

    5.  最终获得了K个列数索引,而原 θ\theta 是一个N长的向量,只不过是K稀疏的。所以我们按照这K个索引将最终所求得的 θ^\widehat{\theta}k 排好顺序填进所有的非0点中作为最终重构的稀疏向量 θ^\widehat{\theta}输出。
                     (---------------------称该步骤为算法输出最终结果---------------------)

    SOMP算法流程

         SOMP的意思是Simultaneous Orthogonal Matching Pursuit 同步/同时正交匹配追踪算法 该算法属于OMP拓展到多信号的一种方法。当信号数为1时,SOMP与OMP的步骤相同,此方法出现于

    输入部分:J个观测信号的矩阵SMJS_{M*J},公共稀疏度K,传感矩阵AMNA_{M*N}
    输出部分:重构的估计稀疏向量 θ^JN\widehat{\theta}_{J*N} ,残差值 rrN*J

    1.  输入变量SSAA,K,初始化残差为 R0R_{0} = SS ,初始化索引集 Ω=ϕ{\Omega}={\phi},初始化迭代计数变量i=1。
                     (---------------------称该步骤为算法初始化过程---------------------)

    2.  通过解决一个简单的优化问题来寻找支撑集
    arg maxωNJ=1J<ri1eω,Aω> {\argmax\limits_{\omega\in N}} \sum_{J=1}^J |<r_{i-1}e_{\omega},A_\omega>|
         求解关于所有信号的残差与传感矩阵之间内积的和,就是每一个信号分别求内积,将多个信号的内积绝对值加和取最大值,作为本次迭代最相关列索引的坐标。并将该系数加入至索引集 Ω{\Omega} 内。
         此处与OMP的区别就在于OMP是输入信号是1列,将其与传感矩阵的各列做内积,取最大值,SOMP中输入的是个矩阵,将S矩阵的每一列分别与传感矩阵的一列做内积,加和,再分别与传感矩阵的下一列做内积,再加和,依次往复。
         式中的eωe_{\omega}为第ω{\omega}列的正交基。可以直接忽略他的作用,是为了表示在当前索引中张成的向量空间。

    3.  求取投影,原文中给的说明就是求取一个投影系数,实际上就是和OMP中最小二乘法求取投影的步骤相同,对于每一个信号在该列上求取一个近似解。
    每一个信号都会获得一个θ{\theta}故为θ^iJ\widehat{\theta}_{i*J}(i为迭代次数)

    4.  分别更新每一列的残差值 rNJr_{N*J}=SMJAΩS_{M*J}-A_{\Omega}* θ^iJ\widehat{\theta}_{i*J} ,对残差的大小进行判断,是否满足重构精度要求,不满足可重复 2、3、4 过程,不断更新残差。若满足了可以终止迭代。最终至多获得K个残差值。
                     (---------------------称以上步骤为算法贪婪迭代过程过程---------------------)

    5.  最终获得了K个列数索引,而原 θ\theta 是一个N长的向量,只不过是K稀疏的。所以我们按照这K个索引将最终所求得的 θ^\widehat{\theta}k 排好顺序填进所有的非0点中作为最终重构的稀疏向量 θ^\widehat{\theta}输出。
                     (---------------------称该步骤为算法输出最终结果---------------------)

    总结SOMP

         SOMP的重构问题在于重构多个信号的时候要确保所有信号的稀疏位置相同,因为会求取多次最小二乘系数,所以各个信号的幅值不同没有关系,各次运算之间是独立的。如果出现信号与信号之间稀疏位置不同的情况,在计算支撑集时就会产生支撑集选择错误的情况,造成重构不准确。
    例如:6个信号联合重构时在该位置上有一个4个信号有值,2个信号的值为0,则计算内积时只会计算4个信号与传感矩阵的内积,会增加序号索引不正确的可能性。
         但是实际仿真中发现这种情况的重构效果还可以,在2个信号的0位置上会出现一个较小的值,但是与整体幅度趋势区别较大,当信号整体稀疏系数(稀疏信号的幅值)较小且观测数(M)不足、稀疏位置不同的情况下容易出现索引位置不正确的情况。
         SOMP的一个好处是引入了多信号之间在公共稀疏基下的稀疏位置相同这一相关性,仅用了内积绝对值加和这一方法就在一定程度上加强相关度最大列的索引依据,使得联合重构时即使观测点数较少,也可以重构出原始信号,这一点在OMP上有了很大改善,OMP中的M经验值要为3-4倍的K效果较好,而SOMP中对于联合多路信号,信号数越多,我们需要的观测数就可以越少,小于2都可以,本人在实际试验中采用M=1.5倍的K进行6路信号重构时,误差就可以控制在2%以内,相比于OMP好了很多,在DCS的论文中,给出了一个趋势就是当信号数趋于无穷时,且各个信号在公共稀疏集上稀疏位置相同,则观测数可趋近与M=K+1即可。

    DCS-SOMP算法流程

    From【BARON D, WAKIN M B, DUARTE MF, et al. Dis-tributed compressed sensing[J]. Neural Information Processing Systems(NIPS),2005,22(10):2729-2732.】
        DCS-SOMP与SOMP有所不同,文中说DCS-SOMP是对SOMP在多信号拓展时做了适应性调整,这个说法我没有在文中找到实际的依据,但是不同的是DCS-SOMP对正交投影的运用方法与OMP和SOMP有些写法上的区别,其实方法本身应该是相似的,只是表现方法不同,在DCS-SOMP中加入了专门的正交化步骤和去正交化步骤。
    这个步骤目前我梳理清楚了,但是其中涉及施密特正交化与最小二乘法之间的联系,正在补充线性代数的相关知识,后续更新这里,争取讲明白。
        
                        叙述过程中部分对原文符号体系进行了修改,方便与前文对齐。

    输入部分:J个观测信号的矩阵SMJS_{M*J},公共稀疏度K,传感矩阵AMNA_{M*N}
    NOTES: 原文中的输入时观测矩阵,其默认进来的向量就是稀疏的,我们此处可以想象原始信号就是一个变换域的稀疏信号,且文中说明了每一列信号J的随机观测矩阵都是不同的,由于每一个观测矩阵都是随机矩阵。且稀疏矩阵与随机矩阵组成的传感矩阵皆默认满足RIP准则,此处为了说明方便讲所有信号采用同一个随机观测矩阵进行观测。)
    输出部分:重构的估计稀疏向量 θ^JN\widehat{\theta}_{J*N} ,残差值 rrN*J

    1.  输入变量SSAAKK,初始化残差为 R0R_{0} = SS ,初始化索引集 Ω=ϕ{\Omega}={\phi},初始化迭代计数变量i=1。
                     (---------------------称该步骤为算法初始化过程---------------------)

    2.  通过一个优化问题 arg maxωNj=1J<rj,i1,Aω>Aω2 {\argmax\limits_{\omega\in N}}\sum_{j=1}^J \frac{|<r_{j,i-1},A_{\omega}>|}{||A_{\omega}||_{2}}                                   式中的ω\omega表示观测矩阵的列数

         这个优化问题其实是求取每个信号的残差在观测矩阵中每一列的投影,参考前文说的投影部分,其实本意也是去最相关的那一列向量作为后面求解的支撑集,将该列的序号加入 Ω\Omega

    3.  将索引到的那一列数据进行正交变换
    γi=Aj,nit=0i1Aj,ni,γtγt22γt\gamma_{i}=A_{j, n_{i}}-\sum_{t=0}^{i-1} \frac{\left\langle A_{j, n_{i}}, \gamma_{t}\right\rangle}{\left\|\gamma_{t}\right\|_{2}^{2}} \gamma_{t}随着迭代次数的增多,新加入支撑集的索引列数据依次正交化,并将正交后的数据保存为 γi\gamma_{i},此处ii为其中iiγ\gamma的第ii列,ii表示迭代次数,角标tt也同理,表示在施密特正交化过程中 γ\gamma 索引列的序号,文中默认每一个信号的观测矩阵不同,所以给出了每一个信号不同的正交矩阵,此处我们采用的观测矩阵为相同的,故只产生一个正交矩阵,或者说每一个信号到这步的正交矩阵都是相同的。

    4.  开始更新求取的估计值 β^\widehat{\beta} 和残差 rr ,注意此处的rrγ\gamma不是一个东西。。。最开始看的时候一时粗心看成了一个元素,推算了好久也没搞明白什么意思,最后发现他俩是两个完全不同的符号,输出出来后rr被拉长了,就长得较为相似,吃了粗心的亏。
    β^j(i)=rj,i1,γiγi22\begin{aligned} \widehat{\beta}_{j}(i) &=\frac{\left\langle r_{j, i-1}, \gamma_{i}\right\rangle}{\left\|\gamma_{i}\right\|_{2}^{2}} \end{aligned}

    rj,i=rj,i1rj,i1,γiγi22γi\begin{aligned} r_{j, i} &=r_{j, i-1}-\frac{\left\langle r_{j, i-1}, \gamma_{i}\right\rangle}{\left\|\gamma_{ i}\right\|_{2}^{2}} \gamma_{ i} \end{aligned}
         此处估计值 β^\widehat{\beta} 的更新策略是取残差在索引集正交变换后的矩阵上的投影,每一个信号与公共的索引向量单独求取估计值,故一共有jj个估计值,且随着迭代次数的增多,β^j\widehat{\beta}_j 的维度也在扩大, 文中也称该估计值为正交系数向量
         此处估计值 rr 的更新策略其实和OMP类似,OMP是取估计值 θ^\widehat{\theta}AΩA_{\Omega} 中现有的所有索引集做乘法,获得当前迭代过程中的近似解,DCS-SOMP中是取了 β^\widehat{\beta}AΩA_{\Omega} 的索引集做正交变换后的 γ\gamma 做乘法,与原残差做差,更新残差值。其实这一步和上文中说的OMP及SOMP的区别就是DCS-SOMP全部是在正交集上操作,本质原理上是一回事。
    5.  检查残差阈值是否符合精度要求,如果符合则停止迭代,不符合则重复上述2、3、4过程,该算法至多迭代M次,即观测点数为最大迭代次数,(文中说这个M次是局限于第三步中的正交策略,正交变换只在每一次迭代中才会更新一列新的正交索引值,但是这类算法的最大迭代次数不应该都是稀疏度K么?即便是迭代了观测数M次,也应该只有K个有效值。此处存疑)最终获得一个 β^\widehat{\beta}γi\gamma_{i} 两个下一步去正交化的关键参数。
                     (---------------------称以上步骤为算法贪婪迭代过程过程---------------------)

    6.  使用QR分解对AΩA_{\Omega}进行分解 AΩ=QRA_{\Omega}=Q*R 矩阵的QR分解是将一个矩阵分成Q(正交矩阵)和R(上三角矩阵)两个矩阵相乘的形式,该Q矩阵前面的步骤中已经获得,就是 γ\gamma 的集合,因此我们可以求得R矩阵。
         输入的观测信号 yy=γ\gamma 的集合*β^\widehat{\beta}的集合 ,也就是 yy=Q*β^\widehat{\beta},且 yy=AΩA_{\Omega}*θ^Ω\widehat{\theta}_{\Omega}
    代入后可得 Qβ^Q*\widehat{\beta}=QRθ^Q*R*\widehat{\theta}, Q消去,可求得
    θ^Ω=R1β^ \widehat{\theta}_{\Omega}=R^{-1}*\widehat{\beta}
    最后,依旧按照索引序号将所求的 θ^Ω\widehat{\theta}_{\Omega}分配至索引位置,输出最终的 θ^\widehat{\theta}

                     (---------------------称该步骤为算法输出最终结果---------------------)

    总结DCS-SOMP

         DCS中在索引到的序列中加入了正交变换的步骤,使得整个运算进行在A的列空间中,最终获得的也是投影系数,最后利用正交矩阵进行QR分解获得最终输出值。从本质上来看求解过程是一致的,就是多了正交化和去正交化的过程,整个过程用矩阵表示的更加宏观了。

    展开全文
  • 利用前后两关键帧图片生成边信息,两种方法:帧插值和前向估计。
  • 文件名称: BCS_CODE下载 收藏√ [5 4 3 2 1]开发工具: matlab文件大小: 1466 KB上传时间: 2014-11-25下载次数: 9提 供 者: zzz详细说明:贝叶斯压缩感知以及分布式贝叶斯压缩感知的算法实现,很好的范例-Bayesian ...

    文件名称: BCS_CODE891ea1e7dab975064c6bfd22796603ae.gif下载

      收藏√  [443d104427974206832dc4b12407db70.gif

     5  4  3  2  1 fb9128a58cbeaabbeb3718ed75079ccf.gif]

    开发工具: matlab

    文件大小: 1466 KB

    上传时间: 2014-11-25

    下载次数: 9

    提 供 者: zzz

    详细说明:贝叶斯压缩感知以及分布式贝叶斯压缩感知的算法实现,很好的范例-Bayesian Bayesian compressed sensing and distributed compressed sensing algorithm, a good example

    文件列表(点击判断是否您需要的文件,如果是垃圾请在下面评价投诉):

    BCS_CODE

    ........\bcs_ver0.1

    ........\..........\BCS_demo

    ........\..........\........\approx_results.mat

    ........\..........\........\BCS_fast_rvm.m

    ........\..........\........\Fig2.m

    ........\..........\........\Fig4_ab.m

    ........\..........\........\l1qc_logbarrier.m

    ........\..........\........\l1qc_newton.m

    ........\..........\........\multi_approx_measures.m

    ........\..........\........\multi_optimized_measures.m

    ........\..........\........\multi_random_measures.m

    ........\..........\........\optimized_results.mat

    ........\..........\........\random_results.mat

    ........\..........\l1magic

    ........\..........\.......\Data

    ........\..........\.......\....\boats.mat

    ........\..........\.......\....\camera.mat

    ........\..........\.......\....\RandomStates.mat

    ........\..........\.......\l1dantzig_example.m

    ........\..........\.......\l1decode_example.m

    ........\..........\.......\l1eq_example.m

    ........\..........\.......\l1qc_example.m

    ........\..........\.......\Measurements

    ........\..........\.......\............\At_f.m

    ........\..........\.......\............\At_fhp.m

    ........\..........\.......\............\A_f.m

    ........\..........\.......\............\A_fhp.m

    ........\..........\.......\............\LineMask.m

    ........\..........\.......\Notes

    ........\..........\.......\.....\Figs

    ........\..........\.......\.....\....\CVS

    ........\..........\.......\.....\....\...\Entries

    ........\..........\.......\.....\....\...\Repository

    ........\..........\.......\.....\....\...\Root

    ........\..........\.......\.....\....\l1eqexample_minl2.eps

    ........\..........\.......\.....\....\l1eqexample_minl2.pdf

    ........\..........\.......\.....\....\l1eqexample_recovered.eps

    ........\..........\.......\.....\....\l1eqexample_recovered.pdf

    ........\..........\.......\.....\....\l1eqexample_signal.eps

    ........\..........\.......\.....\....\l1eqexample_signal.pdf

    ........\..........\.......\.....\....\phantom_backproj.eps

    ........\..........\.......\.....\....\phantom_backproj.pdf

    ........\..........\.......\.....\....\phantom_orig.eps

    ........\..........\.......\.....\....\phantom_orig.pdf

    ........\..........\.......\.....\....\phantom_sampling.eps

    ........\..........\.......\.....\....\phantom_sampling.pdf

    ........\..........\.......\.....\....\phantom_tv.eps

    ........\..........\.......\.....\....\phantom_tv.pdf

    ........\..........\.......\.....\l1magic.bib

    ........\..........\.......\.....\l1magic_notes.aux

    ........\..........\.......\.....\l1magic_notes.bbl

    ........\..........\.......\.....\l1magic_notes.blg

    ........\..........\.......\.....\l1magic_notes.log

    ........\..........\.......\.....\l1magic_notes.pdf

    ........\..........\.......\.....\l1magic_notes.tex

    ........\..........\.......\Optimization

    ........\..........\.......\............\cgsolve.m

    ........\..........\.......\............\l1dantzig_pd.m

    ........\..........\.......\............\l1decode_pd.m

    ........\..........\.......\............\l1eq_pd.m

    ........\..........\.......\............\l1qc_logbarrier.m

    ........\..........\.......\............\l1qc_newton.m

    ........\..........\.......\............\tvdantzig_logbarrier.m

    ........\..........\.......\............\tvdantzig_newton.m

    ........\..........\.......\............\tveq_logbarrier.m

    ........\..........\.......\............\tveq_newton.m

    ........\..........\.......\............\tvqc_logbarrier.m

    ........\..........\.......\............\tvqc_newton.m

    ........\..........\.......\README

    ........\..........\.......\tvdantzig_example.m

    ........\..........\.......\tveq_example.m

    ........\..........\.......\tveq_phantom_example.m

    ........\..........\.......\tvqc_example.m

    ........\..........\.......\tvqc_quantization_example.m

    ........\..........\MT_CS_demo

    ........\..........\..........\Fig2.m

    ........\..........\..........\Fig3.m

    ........\..........\..........\mt_CS.m

    ........\..........\..........\multi_results_25.mat

    ........\..........\..........\multi_results_50.mat

    ........\..........\..........\multi_results_75.mat

    ........\..........\..........\multi_runs_25.m

    ........\..........\..........\multi_runs_50.m

    ........\..........\..........\multi_runs_75.m

    ........\..........\README.txt

    ........\..........\__MACOSX

    ........\..........\........\l1magic

    ........\..........\........\.......\Data

    ........\..........\........\.......\Measurements

    ........\..........\........\.......\Notes

    ........\..........\........\.......\Optimization

    输入关键字,在本站238万海量源码库中尽情搜索:

    帮助

    [fbmpCP.rar] - 用于图像处理的压缩感知的快速贝叶斯匹配追击算法

    [bcs_vb.zip] - 一个基础贝叶斯变换的压缩感知,包含一个源代码和一个一维信号处理的例子和两个二维图像的例子

    [BCS_.rar] - 贝叶斯压缩感知的仿真程序,此程序使用LAPLACE先验,

    [blockTestOMP.rar] - 压缩感知经典程序算法分块的STOMP算法,该算法已经过验证,可以正常使用。

    [OSGA.zip] - 第二种联合稀疏模型重构算法,用于分布式压缩感知

    [bcs_ver0.1.zip] - 贝叶斯压缩感知,一种新的压缩感知,主要是解决信号的重构问题

    [sl0.rar] - SL0压缩感知算法几篇国外原文,拒绝国内水军,各种误导

    展开全文
  • 分布式压缩视频感知DCVS

    千次阅读 2014-04-01 14:32:52
    1、分布式压缩感知  编码端十分简单,每个信号分别进行CS测量。而解码端复杂,将信号集在一起进行联合重构。如图1所示: 图1 分布式压缩感知的基础是联合稀疏模型,即JSM模型,目前有三种,其中JSM-1:信号集中的...

    1、 分布式压缩感知

        编码端十分简单,每个信号分别进行CS测量。而解码端复杂,将信号集在一起进行联合重构。如图1所示:
    66e3af7607c3ebc8c3a07&690
    图1
    分布式压缩感知的基础是联合稀疏模型,即JSM模型,目前有三种,其中JSM-1:信号集中的信号之间相关性很强,每个信号都由公共信号部分和独立信号部分组成,且均稀疏。
     
        由于这种特性,因此在压缩感知过程中,可以对key frame进行更多次测量,而对non-key frame进行少量测量(编码端的低复杂性并非能找出信号的独立部分),从而可以用较少的测量值获得精确的重构效果。
     
        因此,利用该模型的压缩感知可以既能消除时间冗余(帧间相关性),又能消除空间冗余(帧内相关性)。第一次看到JSM模型时,错以为编码端进行区分公共部分和独立部分并进行测量,当时让我百思不得其解。
     
    2、 分布式视频压缩感知
        由于视频是由连续的帧组成,且时间冗余特别的大,即帧间相关性很强,因此十分适合使用分布式压缩感知。
    文献[1]:DISTRIBUTED COMPRESSIVE VIDEO SENSING, Li-Wei Kang and Chun-Shien Lu,ICASSP。作者提出分布式压缩视频感知,编码端独立每一帧的测量,根据JSM-1模型,key frame 需要更多的测量,non-key frame可以减少测量数目。解码端对key frame直接进行GPSR重构,对于non-key frame重构时,需要利用key frame的边信息(side information)进行辅助重构。不失一般性,设有两个帧,Xt Xt+1,对Xt进行直接重构得到Xt的估计,由于前一时刻与后一时刻均有公共部分,因此将Xt的估计作为Xt+1的估计,辅助重构Xt+1。
     
     
    文献[2]:Dynamic measurement rate allocation for distributed compressive video sensing,Hung-Wei Chen, Li-Wei Kang,SPIE。 作者基于上篇文章,提出将CS帧(non-key帧)进行分块处理,key frame不分块,这样好处是key frame重构质量高,继而提供边信息进行联合重构,提高整体恢复质量。对于分块CS帧,作者设计了自适应确定测量率。
     
        作者提出:由于编码端无法获得raw data,对于CS帧,为了依据前一时刻帧中block的稀疏性估计下一时刻的相应block的稀疏性,则通过解码端key frame反馈信息的方式。
     
        核心思想是:在解码端利用重构出的Xt的块的稀疏性去估计下一个帧Xt+1的相应块的稀疏性,从而确定编码端的测量率。由于,解码端Xt的稀疏表示是固定DWT基,而Xt+1是训练字典,作者使用训练字典来对Xt进行稀疏表示,因此能很好的估计Xt+1,之后通过每块系数的变化率确定每块的测量率。

     同一时期关于分布式压缩视频感知的论文有三篇:

    (1)distributed compressive video sensing,台湾中央研究院,ICASSP 2009  ,April 19-24
    (2)distributed video coding using compressive sampling ,马毅等,PCS 2009 ,May 6-8
    (3)distributed compressed video sensing,Lu Gan 等,ICIP 2009,November 7-10
     
    论文(1):
     
        编码端:分别对key frame和non-key frame进行CS测量,其中non-key frame采用分块技术。根据JSM-1模型,key frame的测量率应该大于non-key frame。稀疏表示使用DWT基,测量矩阵采用SBHE矩阵。
        解码端:key frame采用GPSR进行恢复。同样根据JSM-1模型,利用前一帧的信息来重构当前帧,即key frame提供side information 给non-key frame,采用修正的GPSR进行重构(根据side information计算初始值和终止条件)。what's side information?what's GPSR?
    1
    分布式压缩视频感知(二)--早期DCVS
    论文(2):
     
        编码端:区分key frame和CS frame,对于key frame采用传统的H.264编码,CS frame则分块测量。对n个像素的块组成的列向量进行分块测量,得到n个测量值,之后进行b bts的量化,最后选取m个进行传输。量化的作用是?
        解码端:key frame采用传统的方式进行解码。对于CS帧解码的基是从字典中选取,字典是由当前块所在帧的前P个帧的相应块位置(以x为中心,w*w个像素范围)选取的块组成。然后通过解l1范式问题求得重构值。
        作者提出三种机制,分别是skip机制、single机制、L1机制。skip机制中,如果编码端会计算当前块和之前解码key frame相应块的均方误差,若小于约定值,则skip,解码端根据之前的块copy作为重构。因此,编码端需要接收重构的key frame并计算均方误差,增加了复杂度,另外由于编码端无法获得原始数据,可行?single机制中,发送端发送前面m1个测量值,利用该测量值与字典中各个块的前m1测量值进行MMSE计算,若低于约定值,则选中该块作为恢复。否则,使用L1机制,继续发送剩下m2个测量值。编码端和解码端的信息沟通是通过feedback channel。下图所示。

    2

    论文(3):
     
        编码端:K-frame采用传统方式编解码。对于cs frame采用基于块和基于frame的CS测量(连续传递测量值)。
        解码端:基于块的测量值传到解码端,根据JSM模型进行稀疏限制的块预测,算法能找出时域内相邻块(包括key frame)的最小数目的线性表示。如图所示,基于frame的测量值联合基于块的测量值,得到一个完备的测量矩阵,同时,基于块的预测也能获得一个测量矩阵,两者相减可以获得误差的测量矩阵,由于该误差稀疏,因此可以重构。最后将预测后的帧加上预测误差得到最后的结果。
    分布式压缩视频感知(二)--早期DCVS
    3
    总结:
    1. 基于frame的测量稀疏性较基于块的更好,能够获得全局信息。基于块能获得局部信息,重构质量较高,但存在块效应。
    2. 基于块的CS灵活性较高,能够根据不同块设计不同基、测量矩阵,适合尺寸较大的图像流。
    3. 在论文(1)中,key frame采用基于frame的测量,原因是其重构质量更高?
    4. 论文(1),对于key frame和non-key frame均采用CS测量,编码端简单。论文(2)(3)对于key frame采用传统的方式,恢复质量高,但编码端较复杂。
    5. 论文(2)未具体讲述如何进行最优的块预测??

     

    在(二)中文献(1)的基础上,作者发表了文献(4)、文献(5)

    文献(5):DICTIONARY LEARNING-BASED DISTRIBUTED COMPRESSIVE VIDEO SENSING,台湾中央研究院liweikang,PCS2010
    文献(6):Dynamic measurement rate allocation for distributed compressive video sensing,台湾中央研究院liweikang,VCIP2010
     
    个人认为文献(5)借鉴了文献(2)中字典的设计,并把K-SVD算法引入,得到此篇文章。
    字典学习步骤:
    1.当前帧的前一key frame和后一key frame得到It(side information )。
    2.对上述三帧进行分块,对每个块提取9个training patches(哪9个?)。
    3.利用上述patches,根据K-SVD算法训练得到字典Dt。
     
    side information:根据分布式压缩视频感知(一)中分布式视频编码框架,由已解码的key frame和之前的WZ帧生成side information,它的作用在于作为当前帧的估计,利用该边信息和接收到的WZ帧一起得到当前帧的解码。一般做法是:在相邻的两个key frame之间利用运动估计得到插值帧的运动轨道,利用运动补偿生成边信息。
     
    个人认为文献(6)借鉴了文献(2)中的反馈机制,设计了基于解码端已重构帧的相应块的稀疏性的动态测量率。该节在分布式压缩视频感知(一)提到,此处略。
     
    文献(6)distributed compressive video sensing: a review of the state-of-the-art architectures,M2VIP  2012.11
    文献(7)Adaptive Dictionary Learning for Distributed Compressive Video Sensing  ,期刊JDCTA(EI检索),2012
    作者综合前几篇文献之后提出,编码端将key frame和CS frame均采用基于块的CS测量,CS frame量化后的向量进行编码;解码端,key frame采用基于字典的重构,区别与以往文献。作者对文献(6)cs frame的分块的动态测量策略进行改进,使用局部稀疏和remote joint sparstity,局部稀疏性通过计算SI代替当前帧(feedback)
    个人感觉remote joint sparstity来设计编码端测量率是有问题的,另外SKIP机制说的也不清楚。上述之外作者的改进:利用modified MOD训练字典。
    原文地址:http://blog.sina.com.cn/u/1726197622

     

    展开全文
  • 基于残差重构的分布式视频压缩感知
  • 基于半像素多假设预测的残差重构算法在分布式压缩视频感知中的应用
  • 自适应PCA稀疏基底的分布式视频压缩感知重构
  • 压缩感知(CS)是一种能同时进行数据采集和压缩的新理论,为简化编码算法提供了依据,同时,分布式视频编码(DVC)为低复杂度的视频编码提供了思路。因此,通过整合DVC和CS各自的特性以构建编码简单的视频编码框架, ...
  • 结合压缩感知思想,设计了一种分布式混合压缩感知的无线传感器网络数据收集方法。首先通过基于k-means 的方法均匀聚类形成簇,各簇进行基于混合压缩感知分布式数据收集,完成后通过建立骨干树将数据传输至sink节点...
  • 基于压缩感知分布式视频编码框架matlab代码

    千次阅读 热门讨论 2014-12-28 11:04:23
    刚刚开始学习分布式压缩感知,写下了这个分布式压缩感知的代码,现在上传上来和大家分享交流。如果有什么问题请在这篇博文下面评论即可,看到之后我会回复的。 以下为本程序说明:详细的请看程序代码。 本次主要程序...
  • 为了缓解网络通信带宽压力,提出分布式的1 bit压缩频谱感知算法。各节点对感知数据进行压缩采样并1 bit量化,然后融合节点采用JSM-2模型对数据进行融合,最后通过BIHT算法重构信号频谱,实现频谱感知。仿真结果表明...
  • 基于因子图的分布式变分稀疏贝叶斯压缩感知
  • 针对宽带认知无线电网络中压缩频谱感知算法在低信噪比环境下频谱检测性能下降的问题,提出了一种基于高斯过程的分布式压缩频谱感知算法(PBCS 算法)。首先应用层次化的正态分布概率模型来表示压缩频谱的重构,然后...
  • 宽带分布式协作压缩频谱感知不仅降低过高的采样速率,而且改善在低信噪比环境下的频谱感知性能。为进一步提高频谱感知性能,提出一种基于加权一致优化的宽带分布式协作压缩频谱感知算法。该算法根据当前迭代重构出的...

空空如也

空空如也

1 2 3 4 5
收藏数 93
精华内容 37
关键字:

分布式压缩感知