结构稀疏

2024-10-10

结构稀疏（共8篇）

结构稀疏篇1

引言

压缩感知 (Compressive Sensing, CS) [1,2,3]是一种新的信息获取理论。压缩感知理论建立在Candès, Romberg和Tao以及Donoho的工作上, 他们提出并证明一个在某一种基下可以稀疏表示的信号可以通过一部分投影信息重构出来。与传统的奈奎斯特采样定理不同, 该理论指出, 只要信号是稀疏的或者在某个基下可压缩, 就可以利用随机测量矩阵把高维空间上的信号稳定的嵌入到低维空间上。信号在低维空间上的投影包含了重构信号所需要的足够信息, 可以用低维空间上的少量采样值精确重构出原始信号。

当前, 对压缩感知理论的研究大多是以精确重构信号为目的。然而, 在许多信号处理应用中, 信号获取的最终目的并不是重构原始信号, 而仅仅是完成一个检测决定[4,5,6,7,8,9], 像在许多通信系统或者雷达系统中的信号检测任务[10]。在许多情况下, 由于压缩感知的采样值已经保持了原始信号的结构和相关信息, 即使不精确重构信号也可以通过处理压缩感知的采样值完成信号的检测[6,8]。

在基于压缩感知的稀疏信号检测具体算法方面, 一种基于匹配追踪 (Matching Pursuit, MP) 的非相关检测和估计算法[5]已经被提出。该算法通过比较利用部分重构算法得到的最大稀疏系数和利用蒙特卡洛模拟[5]获得的最优门限之间的大小来完成检测任务。本文提出一种基于稀疏信号结构信息的检测方法, 该方法可以分为两部分, 包括一种基于压缩采样匹配追踪 (Compressive Sampling Matching Pursuit, Co Sa MP) [11]的部分重构算法和一种新的检测判定方法。

本文内容安排如下。第二部分介绍压缩感知基础理论。第三部分我们提出并分析基于稀疏信号结构信息的压缩检测方法。第四部分我们通过仿真实验结果来验证提出方法的有效性。最后, 第五部分总结工作并为以后的工作提出方向。

压缩感知理论

压缩感知理论主要包括信号的稀疏表示、编码测量和重构算法三个方面。对于一个信号x∈RN, 假设其稀疏度为k (k

式中:Φ满足约束等距性条件 (Restricted Isometry Property, RIP) [6,11]。现在考虑由采样值y重构原始信号x, 首先应基于采样值y获得x在其变换域Ψ上的稀疏表示θ, 然后在此基础上结合相应的变换基获得原始信号。这可以通过0l范数优化问题找到具有稀疏结构的解:

式中, , 由于式 (2) 的优化问题是一个难求解的NP-hard (Nondeterministic Polynomial-time hard) 问题, 所以可以用1l约束[4,5]取代l0约束:

基于稀疏信号结构信息的压缩检测算法

假设信号s是一个确定的已知的稀疏信号, 我们考虑以下两种假设:

式中:s∈RN, 且稀疏度为k (k

检测的任务就是通过处理采样值y来判断感兴趣的已知信号s的有无。假设信号s在变换域内满足稀疏度为k, 即:

式中:Ψs和θs分别表示变换基和相应的稀疏系数。根据部分重构的思想我们可以通过采样值获得信号在变换基Ψs上的稀疏系数估计值。本文中我们采用基于压缩采样匹配追踪[11] (Compressive Sampling Matching Pursuit, Co Sa MP) 的部分重构算法来获得估计值。与基于匹配追踪的重构算法相比, 基于压缩采样匹配追踪的重构算法性能更好。由于我们不需要精确重构出原始信号, 我们调整压缩采样匹配追踪算法为部分重构算法, 具体算法如下:

令 , 迭代次数设为T, T值应小于精确重构所需要的迭代次数。设信号s在变换域Ψ内的稀疏度为k, 则算法具体步骤如下:

(3) 合并:Z=Ω∪sup (qt-1) 。

(6) 更新采样: 。

(7) 迭代次数t加1, 若t

(8) 输出部分重构信号。

获得估计值后, 我们就可以利用提出的新的判定方法来完成检测任务。具体的判定方法会在下面详细介绍。

θs可以用下面的集合方式表示:

对于目标信号s, 对应稀疏系数值越大, 其可重构出来的概率越大, 反之, 越小的稀疏系数越容易淹没于噪声中, 从而无法重构出来。因此, 我们引入可重构率的概念, 具体定义如下式:

当位置相似度小于某一值时, 我们可以认为位置信息相似度太低, 目标信号不存在。本文中, 我们定义位置相似度门限为目标信号的最大稀疏系数对应的可重构率与最小稀疏系数对应的可重构率之和, 即:

表示位置相似度门限。若位置相似度大于所设门限, 这时, 需要通过幅值信息来判断目标信号的有无。文献[4]通过比较部分重构算法所得的最大稀疏系数与所设门限的大小关系来判断目标信号的有无。在该算法中, 门限是通过模特卡洛模拟的方法得到的, 然而, 实际中门限的设置比较困难, 门限对噪声比较敏感, 门限设置不恰当会严重影响检测性能。在本文中, 我们提出一种新的方法来完成检测判决, 该方法避免了门限的设置, 同时仿真结果表明该方法具有很好的检测性能。具体方法如下:

在位置信息满足一定相似度的基础上, 我们利用部分重构出的估计值中具有最大可重构率的稀疏系数的幅值信息, 假设这一稀疏系数对应的位置信息为, 对应的幅值信息为

当假设H1成立时, 估计值中的与对应的θs中的在数值大小上是近似的, 在一定SNR下的统计特性满足如下分布:

我们可以得到:

当假设H0成立时, 部分重构出的信息满足一定的位置相似度的概率很低, 当位置相似度满足条件时, 我们可以根据幅值信息差异来完成判决。对应于H1情况, 在一定SNR下, H0情况下统计特性满足如下分布:

我们可以推导出:

综合以上分析, 我们可以得到如下的判决方法:

仿真结果和分析

设s是一个长度N=25 6稀疏信号, 其稀疏度k=6。Φ是一个大小为M×N的测量矩阵, 其元素满足高斯分布, M为压缩感知采样点数。实验中假设H1和H0出现的先验概率为Pr (H1) =Pr (H0) =.05, 检测成功率为2000次检测实验的统计结果。同时规定, 检测成功率高于95%时, 检测才有意义[7], 在实验结果中表现为标准线这一条直线。

首先我们验证本文提出的判决方法的有效性。我们对比不同信噪比下本文提出方法与文献[4]采用的方法的检测成功率, 这里部分重构算法我们分别采用文献[4]提出的匹配追踪 (MP) 算法和改进的压缩采样匹配追踪 (Co Sa MP) 算法, 判决方法也分别采用文献[4]的门限判决方法和本文提出的基于信号结构信息的判决方法。令采样点数M=80, 信噪比SNR的变化范围为[-10, 10], 步进为1。实验结果如图1所示。

从图1可以看出, 本文提出的基于结构信息的判决方法更具优势, 同时, 采用Co Sa MP的部分重构算法比采用MP的部分重构算法获得的结构信息更可靠。下面我们研究测量点数对检测性能的影响。在仿真实验中, 我们设迭代次数T=6, 固定信噪比SNR=-2d B, 图2为仿真实验结果。

从图中可以看出, 提出方法比原有方法更有优势, 即使采用原有的部分重构算法, 在判决部分采取本文提出方法, 检测性能也有所提升。另外, 从性能曲线的变化趋势, 我们可以看出检测性能随测量点数的增加变得越来越好, 这是由于测量点数增多, 测量信号中包含的目标信号的结构信息越丰富, 部分重构得到的估计信息更可靠。

然后, 我们验证迭代次数对检测成功率及检测时间的影响。实验结果如图3和图4所示。

仿真实验中, 对于图3所示的实验, 我们考虑了SNR=-2d B和S N R=3 d B的情况, 测量点数为100;对于图4所示的实验, 我们设置SN R=1 0 d B, 测量点数为100, 检测时间定义为1000次检测所用的时间。从图3可以看出, 本文提出方法检测性能很稳定, 迭代次数对检测性能的影响很小, 这是由于采用Co Sa MP的部分重构算法在迭代次数很少的情况下就能获得足够的用于判决的结构信息, 而采用MP的部分重构算法需要迭代次数达到一定程度时, 才能获得可靠的结构信息。另外, 从图4可以看出, 采用Co Sa MP部分重构算法检测方法要比采用MP部分重构算法的检测方法在时间上更有优势, 速度更快。综合图3和图4, 我们可以得出, 本文提出方法在迭代次数很小的情况下也能快速、可靠地检测出目标信号的有无。

为了进一步验证算法的有效性, 下面针对应用于雷达系统中的线性调频信号进行检测。在雷达系统中, 线性调频信号是一种非常重要的信号形式, 信号瞬时频带宽的特性虽然提高了雷达系统的目标检测及识别能力, 却给信号采集及数据处理带来极大压力, 如何使用较少的采集数据完成检测是一个关键技术[7]。在这里, 我们使用文献[12]中的四参量chirplet字典来生成线性调频信号。设生成的线性调频信号的信号长度为1024, 相对chirplet字典的稀疏系数满足正态分布[4], 这里稀疏度设为5, 信噪比为10d B。下面验证本文所提算法与MP检测算法在不同测量点数下的对线性调频信号的检测性能。

从图中可以看出, 本文所提算法能使用较少的测量点数获得较高的检测性能, 这可以减轻接收系统系统在采样和数据处理方面的压力。

结束语

本文基于稀疏信号的结构信息提出一种新的压缩检测方法, 该方法利用改进的压缩采样匹配追踪 (Co Sa MP) 部分重构算法获得目标信号的估计, 通过对比位置与幅值信息的相似度来完成检测。与原有的检测方法相比, 本文提出的方法更高效、更快速、更稳定。实验结果表明, 在低信噪比时, 本文方法在较少的迭代次数下, 可以使用较少的采样数据获得较高的检测成功率。

参考文献

[1]E.Candès, J.Romberg, and T.Tao, Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J], IEEE Trans.Inf.Theory.2006, 52 (2) :489–509.

[2]D.Donoho, Compressed sensing[J], IEEE Transaction on Information Theory, 2006, 52 (4) :1289-1306.

[3]Y.Tsaig, D.L.Donoho, Extensions of compressed sensing[J], Signal Processing.2006, 86 (3) :549–571.

[4]M.F.Duarte, M.A.Davenport, M.B.Wakin, R.G.Baraniuk, Sparse signal detection from incoherent projection[C], IEEE Int.Conf.Acoustics Speech and Signal Processing (ICASSP) , Toulouse, France, May 2006, 305-308.

[5]Jun Wu, Naian Liu, Yanfei Zhang, Changlin Shen.Blind detection of frequency hopping signals based on compressive sensing[C].Consumer Electronic, Communication and Networks (CECNet) , 2012, 1691-1694.

[6]J.Haupt, R.Nowak, A.Yeh, Compressive sampling for signal classification[C], In 2006 Asilomar Conf.on Signals, System&Computer, Oct.2006, 1430-1434.

[7]刘冰, 付平, 孟升卫.基于正交匹配追踪的压缩感知信号检测算法[J].仪器仪表学报, 2009, 31, (9) :1959-1964

[8]J.Haupt, R.Nowak.Compressed sampling for signal detection[C].IEEE Int.Conf.on Acoustics, Speech, and Signal Processing (ICASSP) , Honolulu, Hawaii April 2007, 1509-1512

[9]刘冰, 付平, 孟升卫.基于采样值数字特征的压缩感知信号检测算法[J].仪器仪表学报, 2011, 32, (3) :577-582

[10]Joachim H.G.Ender, On compressive sensing applied to radar[J], Signal Processing.2010, 90 (5) :1402–1414.

[11]D.Needell and J.A.Tropp.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples[J], Applied and Computational Harmonic Analysis, 2009, 26 (3) :301–321.

[12]O.Yeste-Ojeda, J.Grajal, and G.Lopez-Risueno.Atomic decompositionfor Radar applications[J], IEEE Trans.Aerosp.Electron.Syst., 2008, 44 (1) :187–200.

结构稀疏篇2

稀疏造句

1、树木稀疏。

2、从拥有稀疏特点的应用程序的环境中转移到集成的生命周期环境需要投入额外的技能来使用新的环境。

3、虽然它将占用更多的空间，但它可以提供更好的灵活性，因为您可以删除任何不需要的文件或者数据包，而这是您在使用稀疏模型时无法实现的。

4、在一个稀疏分布式网络中，记忆是感知的一种。

5、如果一个条目只填充了稀疏的内容，那么结果看上去就像图8那样。

6、有利于形成这场汹涌洪水的自然因素有三条，这幅大汤普森峡谷下游的自然色图像展示出其中两者：陡峭的地形和稀疏的植被。

7、对于稀疏查找来说，它将根据每条输入记录来生成数据库查询，并且查询将被发送给目标数据库以获取结果。

8、照片上有着稀疏头发的男人怎么看都不对，她说。

9、因此，很多人宁可把它们剃光而不是保留它们用以掩盖秃的地方或任其稀疏地生长。

10、还好幸运的是，大量的碳分布的很稀疏，形成了只占岩石中较少含量的次要成分。

11、第二天，一辆豪华大马车驶进苏格兰农民稀疏的庄稼地，一位衣着考究的贵族从马车中走出来，向农民介绍自己，称自己是他救的男孩的父亲。

12、过了一会儿，头顶上出现了白色月亮的轮廓和一些稀疏的星星，足以让他能分辨出一个人形。

13、在采用稀疏分布式内存的超级计算机里，记忆与数据处理之间的差异消失了。

14、通过使用稀疏列，列数量的限制和相关的空间要求问题都被根除了。

15、因此，问题不在于全球主义是如何的古老，而在于全球主义在任何特定时间下有多么“稀疏”或“密集”。

16、这些来自意大利不同学院的研究员们解释道，他们的模型由稀疏图中节点代表的代理组成。

17、一片深绿色的地毯覆盖了大部分崎岖的`地表，而片片裸地或植被稀疏的地块散布于图片边缘。

18、他们越往前走，那些房屋就变得越大，花园也是从稀疏的草坪扩展到密密麻麻围起来的篱笆和树木。

19、但是，马毅认为这些困难是可以通过稀疏表示来加以解决的。

20、但是当某一地区的人口由稀疏和稠密转化的时候，头盖骨的尺寸会减小。

21、随着时间的推移，毛囊就会发生改变并收缩，导致头发稀疏。

22、即使是那些头发稀疏的男人也会去想办法增多毛发，美容院里面挤满了男人，他们都想得到一头被女性所喜爱的时尚、浓密、波浪式的头发。

23、因为产品的属性各不相同，这种表有许多行，但是填充的列非常稀疏，这导致效率非常低。

24、稀疏查找类型。

25、不可以在稀疏查找中使用批量访问方法。

结构稀疏篇3

压缩传感[1,2,3]技术是一项新兴的技术,主要特点是以远低于奈奎斯特采样数据量精确恢复信号。将其应用于超声波无损检测领域,将大大减少检测产生的数据量,简化硬件系统结构,提高检测信息的分辨率和实时处理能力。然而,目前采用压缩传感技术面临的一个技术瓶颈是稀疏分解原子库规模巨大,在信号分解与重构过程中导致计算复杂度大,降低了该项技术的实用性。针对上述问题,本文提出了一种基于信号结构的稀疏分解原子库的优化策略,并将其应用于管道检测领域,大大减少了原子库的规模。

目前国内外对稀疏分解Gabor原子库的简化研究很少。上海交通大学的梁巍等人根据超声信号是一个高斯调制的带通信号,其有用信息集中在以探头中心频率为中心的某一带宽内,利用带宽因子、探头中心频率和初相位这些先验信息对Gabor原子库的尺度因子和频率因子进行简化,减少了原子库的原子数量[4]。但是脉冲超声回波信号的中心频率并不等于探头频率,且由于实际环境及噪声的影响,其频带宽度以外也包含一定信息量。其次,该方法需要对带宽因子进行估计,存在一定的误差。兰州大学的王峥嵘等人根据Gabor原子的相位因子特性,对原子波形互为相反的原子进行了删减[5]。另外对较长信号分段向量截取,利用对应的长度较短的原子库分别对各段信号进行稀疏分解,再相加得到原信号。

本文以管道检测的缺陷脉冲超声回波信号为研究对象,首先根据Gabor原子的原子特性,对频率因子和相位因子[5]离散化范围进行简化。然后根据脉冲超声回波信号的波形特征对其进行有效长度截取,提取待分解信号的包络并拟合成高斯函数,将对应函数参数转换成Gabor原子形式的尺度因子参数并统计其分布范围,提出了一种基于信号结构的尺度因子离散化方法,克服了依赖于信号长度的尺度因子离散化方法的缺陷。通过对实测信号的仿真表明,优化原子库的稀疏分解效果与Gabor原子库接近,原子数量却减少为原来的1 /8左右。

1 Gabor 原子库的离散化

Gabor原子由一个经过调制的高斯窗函数构成,其表达式为[6]:

其中,g( t) = exp( - πt2) 是高斯窗函数,γ = ( s,u,v,ω) 是时频参数,其中s为尺度因子,u为位移因子,v为频率因子,ω为相位因子。

由于尺度因子、频率因子和相位因子定义了原子的形状,位移因子定义了原子的中心位置[7]。严格意义上余弦函数也应该进行移位处理,因此本文所用Gabor原子表达式为:

离散化方法为[6]:

由上述离散化方法中j、p、k、i的取值范围,可以得到原子库的原子数量为:

由公式( 3) 可知,原子库的原子数量非常巨大。比如,当信号长度为256时,LD= 119756。因此有必要对原子库进行简化。

2 基于原子特征的 Gabor 原子库简化

由公式( 3) 可以看出,原子库的原子数量非常巨大,但是有些原子波形完全相同或者相位相差180度。基于匹配追踪算法[8]稀疏分解时,原子选择原则是信号或余量与原子的内积绝对值最大,因此满足上述条件的这些原子的分解效果相同。本节对满足这些条件的原子进行简化。具体如下:

设两个Gabor原子分别为g( 1) 和g( 2) ,它们的尺度因子、位移因子和相位因子分别相同,频率因子分别为v1和v2且满足v1+ v2= 2π。两个原子的差异仅仅是余弦函数部分,只对余弦函数进行分析,具体如下:

由公式( 4) 可知,只要将原子g( 2) 的相位因子改为2π - ω,则两个原子的波形完全相同。由于Gabor原子的相位因子ω∈[0,2π],完全能实现上述改变。因为频率因子v∈[0,2π],所以将频率因子v的取值范围简化为0到π。

设两个Gabor原子分别为g( 3) 和g( 4) ,它们的尺度因子、位移因子、频率因子的分别相同,相位因子分别为ω1、ω2且满足ω1- ω2= π。两个原子的差异仅仅是余弦函数部分,只对余弦函数进行分析,则:

由公式( 5) 可知,原子g( 3) 和g( 4) 的波形互为相反。相位因子ω = 0,π/6,2π/6,…,2π,在上述对频率因子简化的基础上,再将相位因子ω的取值范围简化为0到5π/6。频率因子和相位因子简化后的原子库为改进Gabor原子库,对应的频率因子和相位因子离散化范围为: 0≤k≤2j,0≤i≤5,原子库的原子数量为:

对比公式( 3) 可以发现,原子库的原子数量减少很多。比如,当信号长度为256时原子数量为30744,是对应Gabor原子库的原子数量119756的1 /4左右。

3 基于脉冲超声回波信号结构的尺度因子简化

由Gabor原子的离散化方法可以发现,尺度因子、位移因子、频率因子的离散化范围均与信号的长度有关,信号长度越长,尺度因子离散化范围越大,位移因子和频率因子的离散化步长越细,原子库的原子数量越大。因此,在对信号稀疏分解之前,必须对其进行有效长度截取,以减少原子库的规模。本文对管道检测的脉冲超声回波信号进行了有效长度截取,截取前的信号如图1所示。

由图1可见,除了有多次脉冲超声回波信号外,大部分信号的接近于0,如果直接对上述信号稀疏分解将导致对应原子库的数量巨大,很多原子是冗余的,因此在对信号稀疏分解之前有必要对信号进行有效截取。脉冲超声回波信号是一个调制的高斯信号,其包络实质是一个高斯函数。Gabor原子也是调制的高斯函数,原子尺度因子反应了高斯包络特性。因此运用原子对脉冲超声回波信号稀疏分解时,由于迭代前几次待分解的信号仍然是高斯调制信号,选择原子的尺度因子取值范围应该满足待分解信号的包络特性,基于此可以简化Gabor原子的尺度因子离散化范围,该方法得到的原子库为结构原子库。具体实现方法如下所示:

1根据脉冲超声回波信号的波形结构,确定样本信号的有效长度。

2用改进Gabor原子对一定数量样本信号进行稀疏分解,迭代次数均取前5次,对每次的待分解信号都进行如下操作:

一是提取待分解信号包络曲线。

二是拟合包络曲线为高斯函数,函数模型为

三是将参数c1转换为Gabor原子形式的尺度因子s1。

3统计上述所有样本信号的取值范围。

4根据s1的取值范围简化改进Gabor原子库的尺度因子离散化范围。

4 实验验证与分析

为了验证本文提出的简化方法的正确性,进行如下两个仿真实验。实验使用的脉冲超声回波信号是管道检测时产生的回波信号,探头的中心发射频率为10MHz,晶圆直径为6mm,耦合剂为水,采样频率为100MHz,仿真实验均在MATLAB上进行。

4. 1 Gabor原子库和改进Gabor原子库的稀疏分解相同性验证

运用Gabor原子库和改进Gabor原子库分别对图2所示的脉冲超声回波信号进行稀疏分解,分解方法为匹配追踪算法。迭代前10次选择的原子波形分别如图3和图4所示。

由图3和图4可以发现,两种原子库下稀疏分解每次选择的原子波形相同或相反。基于匹配追踪算法稀疏分解时,原子选择原则是信号或余量与原子的内积

绝对值最大,因此两种原子库的稀疏分解效果相同。

4. 2 Gabor原子库和结构原子库的稀疏分解性能对比

实验由两部分组成,首先是脉冲超声回波信号稀疏分解结构原子库的形成,然后是基于Gabor原子库和结构原子库的稀疏分解性能对比。

4. 2. 1样本信号有效长度截取

由图1可见,一段完整脉冲超声回波信号包括多次回波信号,每次的信号长度均在200点左右,Gabor原子只能处理长度为2的整数次方的信号,因此本文截取长度为256点的信号作为样本信号。

4. 2. 2样本信号的s1取值范围统计

本文取30组脉冲超声回波信号作为样本信号,,运用改进Gabor原子对其稀疏分解,并基于脉冲超声回波信号结构的尺度因子简化方法进行处理,统计出30组样本信号的s1的取值范围,如图5所示。

30组样本信号的最小值为32,最大值为380。

4. 2. 3原子尺度因子s1离散化范围

已经得到s1∈[32,380],因此稀疏分解选择的改进Gabor原子的尺度因子的离散化范围可简化为32到256之间。实验统计了基于改进Gabor原子对上述30组样本信号前5次稀疏分解选择原子的尺度因子s1的取值范围,如图6所示。

除了两组信号的最小值为16之外,大部分信号的取值范围均在32到256之间,验证了上述推理的正确性。由此得到的结构原子库的原子数量为15372,与信号长度为256时对应Gabor原子库的原子数量119756相比,减少为原来的1 /8左右,原子数量大大减少。

4. 2. 4基于Gabor原子库和结构原子库的稀疏分解性能对比

本文以10组脉冲超声回波信号为测试信号,分别在Gabor原子库和上述得到的结构原子库下对其稀疏分解。实验统计了重构相对误差达到0. 02以内需要的迭代次数以及对应重构相对误差,以此来验证结构原子库的稀疏分解性能。重构相对误差的定义如下所示:

其中,x和分别表示原始信号与重构信号。

实验结果如表1所示。

由表1可以看出,运用Gabor原子库和结构原子库稀疏分解时,重构相对误差达到0. 02以内需要的迭代次数基本一致,相差范围在±3次以内。说明运用结构原子对管道检测脉冲超声回波信号稀疏分解的效果与Gabor原子接近。

5 结束语

结构稀疏篇4

视觉追踪在计算机视觉领域一直是一个重要的课题, 尤其对于监测应用、车辆导航和人机界面研究。比如有人在文献[1-4]中已经提出了很多追踪方法, 但仍然是一个具有挑战性的问题, 由于像局部遮挡, 光照变化, 姿势变化, 背景混乱和视角变化等因素的影响。在本文中, 基于结构局部稀疏表达模型和自适应模板更新策略提出了一种有效的跟踪算法。

1 系统流程图

在此介绍基于自适应结构局部稀疏外观模型法的视觉跟踪, 以下是基于Matlab的系统流程。

2 局部结构稀疏外观模型

给出一组目标模板视频图像序列T=[T1, T2, …, Tn], 在目标区域对一组重叠的局部图像块抽样。利用这些局部块作为词典来给在可能的候选区域局部块编码, 即D=[d1, d2, …, d (n×N) ]∈Rd× (n×N) , 其中d是图像块向量的尺度, n是目标模板的数量, N是在目标区域局部块的数量。矩阵D中的每一列都是从矩阵T中矢量化的局部图像块中通过詛1归一化方法获取的。每个局部块代表固定目标对象的一部分, 因此所有的局部块就能表达目标的完整结构, 由于局部块是从许多模板收集的, 所以这个词典收集了不同模板的共同点并能表达他们的各种形式。对于一个候选目标区域, 可以表示成Y=[y1, y2, …, yN]∈Rd×N。如图2所示。

假设具有稀疏性的情况下, 在目标区域的局部块都能够表示为只有几个基本数组元素的线性组合, 通过求解此公式:

这里yi指的是第i个量化的局部图像块, bi∈R (n) N是局部块相应的稀疏编码, bi≥0意思是bi所有的元素非负。记B=[b1, b2, …, bN], 表示一个候选区域的稀疏代码矩阵。每个局部块的稀疏系数都被分成若干段, 根据每个向量元素对应的模板, 即biT=[bi (1) T, bi (2) T, …, bi (n) T], 其中bi (k) ∈RN表示系数向量bi的K阶分块。对这些分段系数加权, 获得第i个局部块向量Vi,

这里向量Vi对应第i个局部块, C是一个标准术语。然后在候选区确定位置的每个局部块都可以用在不同模板位置的局部块表示。采取的平方矩阵V的对角线元素作为混合特征值, 即:

其中f是混合特征值的向量, 对齐的跟踪结果也便于使用增量子空间训练方法进行码本更新。在集中遍历这些局部块之后, 异常值的影响降低了并且结构信息扔被保存在表达数据中以此更好地定位目标。

3 模板更新

在目标跟踪方法中, 生成累积概率序列:

根据均匀分布定理产生一个在单位区间[0, 1]的随机数r。通过选取哪一本部分的随机数, 可以选择被更换的模板。这能使旧模板缓慢地更新和新模板的快速更新, 从而减小漂移的问题。

利用稀疏表达和子空间学习方法给更新的模板建模。这种增量式法不但可以适应外观改变, 而且也可以保护收集到的目标物体的相同视角的共同信息。目标估计可以通过主成分分析的基向量的线性组合建模和在文献[4]中使用的琐碎模板法。

其中:p表示观测向量矩阵, 矩阵U由特征向量组成, q是特征向量系数矩阵, e表示在p被损坏或遮挡的矩阵中的像素。由于遮挡和噪声引起的误差是任意的并且稀疏的, 用詛1正规化最小二乘法解决此问题。

其中:H=[U I], c=[q e]T, λ是正则化参数。琐碎模板系数被应用到解决噪声或遮挡问题和避免太多的遮挡块被更新到模板集。然后重建的图像被用于更新将被替换的模板。这个过程可以看作是引入稀疏子空间表达方法。

4 目标跟踪

本文使用的目标跟踪算法是在贝叶斯定理框架下实现的。给出目标观察数据集z1:t=[z1, …, zt]到第t帧, 目标状态变量xt可以由最大的后验概率估计计算

在xti表示第i个序列状态。后面的概率p (xti|z1:t) 可以通过贝叶斯定理递归,

其中p (xt|xt-1) 表示动态模型和p (zt|xt) 指的是观测模型。动态模板p (xt|xt-1) 描述连续帧之间的目标状态的时间相关性。把六参数仿射转换模型运用到给连续两帧之间的目标模板进行建模。状态转换作为p (zt|xt-1) =N (xt;xt-1, Σ) , Σ是对角协方差矩阵, 它的元素是仿射参数各个方差。

观察模型p (zt|xt) 表示zt观察在状态xt的可能性。它对于稳健的跟踪起着重要的作用。在此方法中, 观测模型由

在等式的右边表示候选区域和基于混合特征f目标之间的相似性。随着模板的逐渐更新, 观察模型能够适应目标的外观改变。

5 实验设计

该算法在MATLAB软件中实现。詛1最小化问题可以用文献[5]中的SPAMS package方法来解决, 在所有的实验中正规化常数的λ被设置为0.01, 对于每一个视频序列, 目标对象的位置在第一帧需要手动标记。文献[6]增量视觉跟踪 (IVT) 方法, 文献[7]基于片段 (fragtrack) 跟踪方法, 文献[8]詛1指数法, 文献[9]多实例学习 (MIL) 跟踪器法。实验结果表明, 本文的跟踪方法比其他的方法更好。

6 总结

本文所提出的方法利用跟踪目标的空间和局部信息通过使用队列池方法遍历空间布局的局部块。这有助于更准确地定位目标, 在被遮挡时更可靠。但有时会出现误差, 导致跟踪出错, 所以本系统的跟踪算法也有待改进。

摘要：本文基于MATLAB软件, 通过利用局部结构稀疏外观模型的方法和一种新颖的队列池方法 , 利用跟踪目标的空间和局部信息实现目标跟踪。通过遍历所有图像局部块获得的相似性, 不但能够准确定位目标而且处理了遮挡问题。此外, 也使用了结合增量子空间学习和稀疏表达方法的模板更新策略, 此策略可使模板实时更新, 稳定性好。

关键词：MATLAB,局部模型,队列池方法,稀疏表示,目标跟踪

参考文献

[1]姜明新, 王洪玉, 刘晓凯.基于多相机的多目标跟踪算法[J].自动化学报, 2012, 38 (4) :497-506.

[2]姜明新, 王洪玉, 等.基于ML和L2范数的视频目标跟踪算法[J].电子学报, 2013, 41 (11) :2307-2313.

[3]姜明新, 王洪玉.基于多层定位的多目标跟踪算法[J].大连理工大学学报, 2012, 52 (5) :767-771.

[4]姜明新, 王洪玉.基于特征分组的在线目标跟踪算法[J].大连理工大学学报, 2013, 53 (5) :755-759.

[5]B.Liu, L.Yang, J.Huang, P.Meer, L.Gong, and C.A.Kulikowski.Robust and fast collaborative tracking with two stage sparse optimization[C]//ECCV.2010.

[6]J.Mairal, F.Bach, J.Ponce, and G.Sapiro.Online learning for matrix factorization and sparse coding[J].Journal of Machine Learning Research, 2010, 11:19-60.

[7]D.Ross, J.Lim, R.-S.Lin, and M.-H.Yang.Incremental learning for robust visual tracking[J].IJCV, 2008, 77 (1) :125-141.

结构稀疏篇5

矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素的分布没有规律,通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于25%时,则称该矩阵为稀疏矩阵(sparse matrix),该比值称为这个矩阵的稠密度。事实上,实际问题中大规模矩阵基本上都是稀疏矩阵,很多稀疏度在90%甚至99%以上。因此需要有高效的稀疏矩阵的压缩存储格式。

稀疏矩阵的压缩存储思想是仅存储非零元素的行号、列号以及值(三元组)。常见的顺序存储方式有三元组表、伪地址表示法等;链式存储结构有十字链表结构、带行指针向量的链表结构等。链式存储结构更适合作为非零元素的位置和个数经常发生变化的稀疏矩阵的存储方式。将阐述稀疏矩阵带行指针向量的单链表结构及基于此存储方式的稀疏矩阵转置算法及调用转置算法辅助稀疏矩阵相乘算法具体实现。

2 链表存储结构[1]

2.1 三元组结点的类型

在稀疏矩阵这种链式结构中,需要把具有相同行号的三元组结点按列号从小到大顺序链接成一个单链表,每个结点由3个域组成:非零元所在列的列号(col),非零元的值(value)及指向本行下一个非零元的指针(next,)每个三元组结点结构。其类型可定义为如下模板[2]

2.2 稀疏矩阵类型

稀疏矩阵中的每一行对应一个单链表,每一个单链表都有一个表头指针,为了把它们保存起来,便于访问每一个单链表,需要使用一个行指针向量,该向量中的第i个分量用来存储稀疏矩阵中第i行所对应的单链表的表头指针,该指针指向第i行第一个非零元结点,若该行没有非零元,则该指针为空。例如,稀疏矩阵A6×7如图1及其带行指针数组的单链表存储结构如图2所示。

带行指针的链表存储结构表示的稀疏矩阵类声明模板如下:

3 稀疏矩阵基本运算

3.1 构造算法

在对稀疏矩阵类对象实例化时以参数初始化矩阵的行数、列数及非零元个数,并对行指针数组动态分配数组空间。

3.2 转置算法

将一个矩阵转置就是把原矩阵的行、列对换。在带行指针向量的链式存储结构上实现稀疏矩阵的转置时,算法思想是:在带行指针数组的单链表中从原矩阵的第一行单链表开始,逐行遍历每一个单链表,将第i个单链表(即第i行)中列号为j的结点逐一复制到一个新结点同时完成行、列互换,并按照转置后列号递增的顺序插入到目标矩阵第j行。在这个过程中用到了一个insert函数,实现在目标矩阵中第k行尾部插入一个新结点s。实现的代码分别如下:

3.3 相乘算法

设有两个矩阵分别是m×n和n×l的A和B,它们相乘后的结果矩阵C为m×l。对于C中的每一个元素C[i][j],0≤i≤m-1,0≤j≤l-1:[3]

在带行指针数组的单链表存储结构上实现稀疏矩阵相乘算法思想是:结果矩阵中元素C[i][j]是A的第i行的所有列的对应元素与B矩阵中第j列的所有行的对应元素相乘后再相加的结果。但是在带行指针数组的单链表存储结构中第j列的数据不容易读取。在此算法的实现过程中的处理方法是先将B矩阵转置,得到B的转置矩阵的带行指针数组的链表存储结构,则实现过程就变成读取并处理A矩阵中的第i行的非零元分别与B的转置矩阵中的第j行的对应列号相等的非零元素相乘再相加就得到了结果矩阵中的C[i][j]。实现的代码如下:

4 基本运算的算法性能分析

在稀疏矩阵带行指针数组的单链表存储结构上,建立带行指针链式存储结构的时间复杂度是O(Rows+Terms)。转置算法的主要过程是对原矩阵中的链表进行逐行扫描,时间性能取决于矩阵的行数Rows和非零元个数Terms,因此,该转置算法的时间复杂度为O(Rows+Terms)。相乘算法主要过程也是对原矩阵A和B单链表逐行进行扫描,而且每处理A矩阵中一行,需要扫描矩阵B所有行。在此考虑一种平均的情况:矩阵A中Terms个非元素平均分布到每一行是A.Terms/A.Rows个元素,B的非零元素的个数B.Terms,因此,该矩阵相乘算法时间复杂度为O(A.Terms/A.Rows*B.terms)。当稀疏矩阵的非零元素的个数Terms远远小于矩阵的行列数时,这些基本运算的时间复杂度比采用二维数组存储时的时间复杂度要好得多。

5 结语

在实际应用中处理大型稀疏矩阵时,选择采用何种存储方式要根据对矩阵进行的运算来决定。对稀疏矩阵带行指针向量的链表存储结构做了具体介绍并完成了基于这种存储结构上的基本运算。通过对各算法的性能分析,当稀疏矩阵中非零元素的位置和个数变动比较大时,带行指针向量的链表存储结构是一种不错的选择。

参考文献

[1]徐孝凯.数据结构实用教程(C/C++描述)[M].北京:清华大学出版社,2004:98-99.

[2]郑莉,董渊,何江舟.C++语言程序设计[M].北京:清华大学出版社,2010:309-314.

稀疏重构算法篇6

关键词：稀疏逼近,压缩感知,最优化,重构

图像恢复是通过计算机处理,对质量下降的图像加以重建或恢复的处理过程。因摄像机与物体相对运动、系统误差、畸变、噪声等因素的影响,使图像往往不是真实景物的完善映像[1,2,3]。在遥感图像处理中,为消除遥感图像的失真、畸变,恢复目标的反射波谱特性和正确的几何位置,通常需要对图像进行恢复处理,包括辐射校正、大气校正、条带噪声消除、几何校正等内容。在图像恢复中,对于一个目标函数求极小值,其中要求解的目标函数就是如下的一个不受约束的最优化问题[4,5,6,7]

$\min_{x} ϕ (x)$ :f(x)+τc(x) (1)

其中,f为Rn→R光滑函数,c为Rn→R正则函数其中定义域x∈Rn。

对于式(1)具体到l2-l1中,有

$\min_{x \in R^{n}} \frac{1}{2} | y - A x |_{2}^{2} + τ | x |_{1} (2)$

其中,y∈Rn,A∈Rk×n,k<n,τ∈R+标准欧几里得范数 $| \cdot |_{2}, | \cdot |_{p}$ 代表lp范数,其中p≥1。式(2)可以用于求出欠定线性方程y=Ax的稀疏近似解[8,9]。

之前涉及上述快速算法包括文献[2]中的方法。在信号处理中关于l1惩罚项的记载参见文献[10]。对于上述最优化问题比较流行的新的应用,就是压缩感知(CS)[9]。最新结果显示,一个稀疏信号相对较少的数据投影,可以包含绝大多数信息。当设置了没有噪声的情况下,通过发现一个可以匹配原始信号的稀疏信号从而精确逼近。

1 方法概述

求解式(1),可以通过生成一些列的{xt,t=0,1,…}进行迭代求解,首先通过泰勒公式进行展开,并运用MM算法进行简化

$x^{t + 1} \in \arg \min_{z} (z - x^{t})^{Τ} \nabla f (x^{Τ}) + \frac{α_{t}}{2} | z - x^{t} |_{2}^{2} + τ c (z) (3)$

其中,αt∈R+。将式(3)进行化简得到

$x^{t + 1} \in \arg \min_{z} | y - u^{t} |_{2}^{2} + \frac{τ}{α_{t}} c (z) (4)$

其中, $u^{t} \in x^{t} - \frac{1}{α_{t}} \nabla f (x^{t})$ 。将式(3)中前两项,即 $(z - x^{t})^{Τ} \nabla f (x^{t}) + \frac{α_{t}}{2} | z - x^{t} |_{2}^{2}$ 可以看作一个二次可分离的逼近f(x),如果对于正则项c(z)是可分离的情况,则式(3)是可分离的形式。对于正则项c(z)是可分离的情况,可写为如下形式

$c (x) = \sum_{i = 1}^{n} c_{i} (x_{i}) (5)$

式(2)中的l1正则项显然如式(5)所示,即 $c_{i} (z) = | z |$ ,当正则项是l $_{p}^{p}$ 范数时, $c (z) = | z |_{p}^{p} = \sum_{i} | z_{i} |^{p}$ ,也满足式(5),即正则项是可分离的。

对于正则项是块可分离的情况,如式(6)所示

$c (x) = \sum_{i = 1}^{n} c_{i} (x_{[i]}) (6)$

其中,x[1],x[2],…,x[m]是x中m个不相交的子集。

综上所述,可以得到式(3)每一次迭代的解。当正则项c(x)是可分离的或者块分离的,可以得到有限的极小值。随后可以证明极小值的解收敛。

2 算法

2.1 算法框架

通过选取不同的正则项c(x),不同的方法选择αt,序号8中xt+1满足的条件不同,可以得到不同的实例化。

2.2 正则项c(x)是可分离的,对于子问题的求解

对于式(2)可以用MM算法求解,其中, $f (x) = \frac{1}{2} | y - A x |_{2}^{2}$ 。将其展开为 $f (x) = \frac{1}{2} y^{2} - y^{Τ} A x + \frac{1}{2} x^{Τ} A^{Τ} A x$ 。令, $\frac{1}{2} y^{2} = c, - y^{Τ} A = b^{Τ}, \frac{1}{2} A^{Τ} A = Ρ + Ν$ ,其中P是正的确定矩阵,N是负的确定矩阵。可得如下迭代公式

$x^{t + 1} \in \arg \min_{z} z^{Τ} Ρ z + (b + 2 Ν x^{t})^{Τ} z + (c - z^{Τ} Ν z) + τ c (z) (7)$

2.3 对于αt的选取

可以用αtI来代替Hessian矩阵∇2f(x),令,st=xt-xt-1,Rt=∇f(xt)-∇f(xt-1),要求αtst≈Rt从而得到αt

$α_{t} = \arg \min_{α} | α s^{t} - R^{t} |_{2}^{2} = \frac{(s^{t})^{Τ} R^{t}}{(s^{t})^{Τ} s^{t}} (8)$

对于式 $(2) f (x) = \frac{1}{2} | y - A x |_{2}^{2}$ ,则有 $α_{t} = | A s^{t} |_{2}^{2} / | s^{t} |_{2}^{2}$ 。保证αt在算法结构中的αt∈[αmin,αmax]。

2.4 解的条件

对于每一次迭代,xt+1满足如下

$ϕ (x^{t + 1}) \leq \max_{i = \max (t - Μ, 0), \dots, t} ϕ (x^{i}) - \frac{σ}{2} α_{t} | x^{t + 1} - x^{t} |^{2} (9)$

其中,σ∈(0,1)是一个常量,通常取一个接近于零的数。

2.5 终止条件

终止条件用于迭代程序的最后终止的条件。

2.6 对于的自适应选取

就像GPRS和IST算法,好的初始值对于问题的解是有益处的。关于自适应的选择就是首先给定一个初始的τ0,用于初始化算法,当第二次运行算法程序时,可以自适应地选择一个τ,这样可以减少算法的迭代次数。如果用一个稍大的τ来解决式(1),然后逐渐缩小到期望值,比直接给定一个较小的τ,通常会更有效。

对于τ,如果 $τ \geq | A^{Τ} y |_{\infty}$ 则关于式(2)的解是零向量。如果τ比 $| A^{Τ} y |_{\infty}$ 稍小,则认为过大,当 $τ ≪ | A^{Τ} y |_{\infty}$ 时,则认为τ足够小。

3 实验结果

前提条件选取A是[20×40]的随机矩阵,分别选取x为不同的稀疏度,ζ=1.1。

4 结束语

介绍了用于解决大欠定最优化问题的稀疏重构算法SpaRSA,并改进了SpaRSA的解法以及对τ的选取,仿真结果表明,该算法能够更快的求出近似解,在正则项是凸的情况下,可以证明目标函数的极小解是收敛的。

参考文献

[1]STEPHEN J W,ROBERT D.Sparse reconstruction by sepa-rable approximation[J].IEEE Trance on Math,2009(1):981-986.

[2] CLAERBOUT J,MUIR F.Robust modelling of erratic data[J].Geophysics,1973(8):826-844.

[3] AXELSSON O.Iterative solution methods[M].Newyork:Cambridge University Press,1996.

[4]BARZILAI J,BORWEIN J.Two point step size gradient meth-ods[J].IMA Journal of Numerical Analysis,1988(8):141-148.

[5] OLSHAUSEN B A,FIELD D J.Emergence of simple-cell receptive field properties by learning a sparse code for natural images[J].Nature,1996,38(1):607-609.

[6]LEWICKI M S,SEJNOWSKI T J.Learning overcomplete rep-resentations[J].Neural Computer,2000,12(2):337-365.

[7] COMBETTES P,WAJS V.Signal recovery by proximal for-ward-backward splitting[J].SIAM Journal of Multiscale Model Simulation,2005(4):1168-1200.

[8] CLARKE F.Optimization and nonsmooth analysis[M].New York:Wiley Press,1983.

[9]CAND`ES E,ROMBERG J,TAO T.Stable signal recovery from incomplete and inaccurate information[J].Communica-tions on Pure and Applied Mathematics,2005,59(6):1207-1233.

压缩感知稀疏信号重构算法研究篇7

关键词：压缩感知,平滑函数,l0范数,信号重构

不同于传统的奈奎斯特 (Nyquist) 采样定理, 压缩感知理论 (Compressed Sensing, CS) [1,2]充分利用信号稀疏性或者可压缩性, 将采样与压缩同时进行, 通过一个观测矩阵将高维信号投影到低维空间, 再通过求解一个优化问题从少量的观测值中实现原信号的精确重构。它极大的降低了采样的复杂度, 节约了采用所需时间, 减小数据获取、传输及处理的压力, 因此CS一出现便引起广大研究人员的关注, 目前其应用研究已经涉及到众多领域, 如图像信号处理[3,4]、语音信号处理[5,6]等等。

压缩感知主要包括三个方面即:信号的稀疏表示, 线性测量, 重构算法。其中稀疏信号重构算法是该理论的至关重要的环节, 其作用是利用尽可能少的测量值来精确地重构出原始信号。目前国内已出现的具有代表性的压缩感知信号重构算法主要有:基于l0范数最小化的贪婪迭代匹配追踪系列算法, 如正交匹配追踪 (Orthogonal Matching Pursuit, OMP) [7]、梯度类算法[8]等;基于l1范数最小化的凸优化算法, 如基追踪算法 (Basis Pursuit, BP) [9]、迭代阈值类算法[10]等;以贝叶斯统计为代表的非凸优化算法, 如FOCUSS[11]算法等。上述算法各有优缺点。

Hosein Mohimani等人2009年提出的平滑l0范数 (Smoothed l0 Norm, SL0) 算法[12], 该算法使用带参数的平滑函数去逼近向量的最小l0范数, 将求解最小l0范数问题转化为平滑函数的极值问题。在此算法的基础上, 文献[13]构造了TSL0 (Thresholded SL0) 算法。针对平滑函数的选取问题, 本文提出一种新的平滑函数序列近似l0范数, 实现稀疏信号的精确重构。仿真结果表明, 该算法在信号测量个数以及稀疏度相同的情况下, 重构概率优于OMP算法和SL0算法。

1 信号重构模型

设将N维实信号α∈RN×1为K稀疏向量, 即该信号包含为K个非零值, 其中K≤N。对该信号进行压缩观测, 将高维信号投影到低维空间,

其中Φ为观测矩阵, Φ∈RM×N, K

上式方程中未知数的个数N大于个数M, 是欠定方程因此有无穷解。充分利用信号α的稀疏特性, 通过附加一定的限制条件可以求解上述方程组。其求解模型为:

2 改进SL0重构算法

SL0重建算法主要采用最速下降法和梯度投影原理, 其关键问题是选取合适的平滑连续函数来逼近l0范数, 通过一个平滑的连续函数来近似逼近向量的最小l0范数, 使得l0范数最小的量就是所求的最优解。文献[12]中采用来近似l0范数。通过改变参数σ, 可以获得最小l0范数解。为了进一步提高其逼近性能, 本文采用如下形式函数作为平滑函数, 来近似l0范数, 显然有

记Fσ (α) =N-Ni=∑1fσ (αi) , α0表示向量α非零元素的个数。其中参数σ的大小决定了逼近的程度, 当σ=0时, 由于, 因此式 (3) 的解就是式 (1) 的解。实际上无法令σ=0, 因此只能通过选择一个递减序列σ1, σ2, σ3, 对每一个σi值对应的目标函数求最优值, 直到σ足够小为止。

采用上述平滑函数结合梯度投影方法进行优化求解, 算法具体步骤如下:

第1步:设定初始值, 重建向量x=ΦTy, 初始余量0r=0, 平滑函数的初始参数σ=1。

第2步:求解-Fσ的梯度d;

第3步:利用修正牛顿算法求得x=x+μd。

第4步:利用梯度投影得到x=x-ΦT (ΦΦT) -1 (Φx-y) , 同时计算余量r=y-Φx。

第5步:得到最优值。

3 仿真分析

为了验证算法的重构性能, 本文通过MATLAB处理平台对算法进行仿真测试。选取信号y=Φα, Φ∈RM×N为服从高斯分布的随机矩阵, α由非零元素±1组成的离散信号, 信号长度N=256。μ取0.5, 重复200次实验, 改变信号的稀疏度和测量次数, 重构概率的变化情况曲线如图1、图2所示。

从图1可以看出测量次数 (M=128) 一定时, 随着信号稀疏度的增加, 三种算法的重构概率逐渐减小, 当稀疏度为40时, 本文算法依然有着较高的重构概率, OMP, SL0算法重构概率相对较低。从图2可以看出, 稀疏度一定时 (稀疏度K=30) , 随着测量次数的增加, 信号重建的概率逐渐增加, 本文算法在相同测量次数情况下有着较高的重构概率。

4 结论

基于压缩感知的稀疏信道估计篇8

1 压缩感知模型

在现实应用里, 我们可能碰到如下的方程y=Φx, 其中x∈Rn为未知向量, y∈Rm是已知向量, 为Φ∈Rm×n已知的测量矩阵, m

minx∈Rn‖x‖l0 subject to y=Φx,

其中‖x‖l0=∑undefined|{i∶xi≠0}|。

但是该算法复杂度为非多项式难度 (NP-hard) , 因而采用折中算法。经典的折中方法包括两类:贪婪算法和最小l1范数法。前者包括正交匹配追踪[8] (Orthogonal Matching Pursuit, OMP) , 该算法具有易于实现和较低的算法复杂度。但当稀疏度S较大时, 该算法不稳定, 因而需要采用后者:最小l1范数法。本文着重研究最小l1范数, 并在此基础上应用迭代最小l1范数来提高性能。

2 OFDM系统模型

OFDM传输过程可用如下方程

y=x*h+z=Xch+z

其中y和x分别为接受和发出的时域数据。Xc是循环矩阵, z～CN (0, N0I) 为复高斯噪声向量。

接收的数据通过离散傅立叶变换 (DFT) 解调。由于X是循环矩阵, Y=Fy= (Y0, Y1, …, YN-1) 和X= (X0, X1, …, XN-1) 为频域数据。发出的频域数据中包含导频, 导频符号用Xp表示, 可得

RY=Rdiag (X) Fh+RFz=diag (Xp) Fh+RFz

其中R为导频选择矩阵, Xp为频域导频符号组成的向量。满足Rdiag (X) =diag (Xp) 。将Φ=Rdiag (X) F代入方程 (公式编号) , 可得

Yp=Φh+z′,

其中z′=RFz。Yp和Φ都为已知, 要求解的h稀疏。所以可以用压缩感知的模型来求解h, 即估计该稀疏信道。

3 基于压缩感知估计信道

3.1 最小l1范数法 (BP)

直接求解最小l0范数法, 也就是寻找最稀疏的向量满足已知方程, 计算复杂度过高。通常用最小l1范数法求解, 又叫基追踪法 (Basis Pursuit, BP) [6],

undefinedsubject to y=Φx,

其中‖x‖l1=∑undefined|xi|。

3.2 迭代最小l1范数法 (RBP)

BP法虽然将l0范数问题转化为l1范数问题, 降低了运算复杂度, 但可以利用迭代算法进一步提高。算法如下[5]:

第一步设置迭代次数l为零, 并加权系数wundefined=1, i=1, …, n;

第二步求解加权最小l1范数问题:x (l) =arg min‖Wlx‖l1subject to y=Φx;

第三步更新加权系数:对于每个undefined;

第四步跳出迭代如果达到预定的迭代次数lmax。否则, 增加l并回到第二步。

式中ϵ是为了避免分母出现零。用这种迭代算法可以更好的估计非零系数的位置和大小。因为, 迭代最小l0范数法中将x向量中绝对值较大的元素xi的权重wi减小并放大绝对值较小元素的系数, 因而更加逼近最小l0范数法[5]。

4 仿真与性能比较

为了验证基于压缩感知的稀疏信道估计的性能, 我们进行了仿真测试。OFDM系统采用QPSK调制, 每帧的长度为N=256, 导频长度为P=64。信道为多径瑞利信道, 其长度为L=256, 稀疏度为K=25, 即包含K个非零系数, 而大小和位置都是随机的。导频长度是信道长度的1/4, IFFT法采用均匀分布, 和基于压缩感知的方法采用随机分布。

实现了3种估计信道的方法, 并给出对应的误码率曲线。IFFT法是利用均匀分布的导频符号计算出信道的64个频域响应系数, 然后作逆傅立叶变换 (IFFT) , 再做N点傅立叶变换得到频域响应系数。由图1可以看出, 传统方法已经无法有效估计信道, 同时基于压缩感知的BP法 (即最小l1范数法) 和RBP法 (迭代最小l1范数法) 明显优于传统的IFFT法。但是, 这种性能提升是以牺牲运算时间为代价的, 迭代次数越多, 则耗时越长。

5 结论

基于压缩感知的稀疏信道估计方法包括BP法和RBP法。在降低的导频符号数的情况下, 它们仍能有效地估计信道, 而常规方法此时已无法估计信道。同时, 相比BP方法, RBP法明显降低了误码率。

参考文献

[1]Shanner F.Cotter, Bhaskar D.Rao.Sparse Channel Es-timation via Matching Pursuit with Application to Equali-zation[J].IEEE Trans.on Communication, 2002, 50:3.

[2] Christian R. Berger, WANG Z H, ZHOU S L. Application of Compressive Sensing to Sparse Channel Estimation[M]. IEEE Magzine, 2010.

[3] E. Candes and T. Tao.Decoding by linear programing[J]. IEEE Trans. Inform. Theory 2004:3-5.

[4]E.Candes, Michael B.Wakin.An introduction to com-pressive sampling[M].IEEE Signal Processing Magzine, 2008:21-30.

[5]E.J.Candes, Michael B.Wakin, Stephen P.Boyd.En-hancing sparsity by reweighted l1 minimization.Manu-script.

[6] D. L. Donoho. For most large underdeterminded systems of linear equations the minimal l1 norm solution is also the sparsest Manuscript, 2004.

[7] Romberg J. Imaging via compressive sampling[J]. Signal Processing Magazine, 2008, 25 (2) :14-28.

【结构稀疏】推荐阅读：

稀疏估计06-15

加权稀疏表示06-27

稀疏表示分类09-11

稀疏贝叶斯论文08-11

稀疏的近义词05-26