压缩感知原理

1、压缩感知原理1压缩感知引论传统方式下的信号处理,是根据奈奎斯特采样定理对信号进行采样,得到大量的采样数据,需要先获取整个信号再进行压缩,其压缩过程如图2.1可压缩信号tWj速米样变换压缩重构信号图2.1传统的信号压缩过程在此过程中,大局部采样数据将会被抛弃,即高速采样后再压缩的过程浪费了大量的采样资源,这就极大地增加了存储和传输的代价.由于带宽的限制,许多信号只包含少量的重要频率的信息.所以大局部信号是稀疏的或是可压缩的,对于这种类型的信号,既然传统方法采样的多数数据会被抛弃,那么,为什么还要获取全部数据而不直接获取需要保存的数据呢？Candes和Donoho等人于2004年提出了压缩感知理论

2、.该理论可以理解为将模拟数据节约地转换成压缩数字形式,防止了资源的浪费.即,在采样信号的同时就对数据进行适当的压缩,相当于在采样过程中寻找最少的系数来表示信号,并能用适当的重构算法从压缩数据中恢复出原始信号.压缩感知的主要目标是从少量的非适应线性测量中精确有效地重构信号.核心概念在于试图从原理上降低对一个信号进行测量的成本.压缩感知包含了许多重要的数学理论,具有广泛的应用前景,最近几年引起广泛的关注,得到了蓬勃的开展.2压缩感知原理压缩感知,也被称为压缩传感或压缩采样,是一种利用稀疏的或可压缩的信号进行信号重构的技术.或者可以说是信号在采样的同时被压缩,从而在很大程度上降低了采样率.压缩感知跳

3、过了采集N个样本这一步骤,直接获得压缩的信号的表示.CS理论利用到了许多自然信号在特定的基上具有紧凑的表示.即这些信号是“稀疏的或“可压缩的.由于这一特性,压缩感知理论的信号编解码框架和传统的压缩过程大不一样,主要包括信号的稀疏表示、编码测量和重构算法等三个方面.对于一个实值的有限长一维离散时间信号X,可以看作为一个RN空间NX1的维的列向量,元素为n,n,=1,2,N.RN空间的任何信号都可以用Nxi维N的基向量i-的线性组合表示.为简化问题,假定这些基是标准正交的.把向量Ni-作为列向量形成NN的基矩阵：=1,2,?,N,于是任意信号X都可以表示为：X(2.1)其中是投影系数=i(X,)构

4、成的NX1的列向量.显然,X和是同一个信号的等价表示,X是信号在时域的表示,那么是信号在域的表示.如果的非零个数比N小很多,那么说明该信号是可压缩的.一般而言,可压缩信号是指可以用K个大系数很好地逼近的信号,即它在某个正交基下的展开的系数按一定量级呈现指数衰减,具有非常少的大系数和许多小系数.这种通过变换实现压缩的方法称为变换编码.在数据采样系统中,采样速率高但信号是可压缩的,采样得到N点采样信号X;通过TX变换后计算出完整的变换系数集合i;确定K个大系数的位置,然后扔掉NK个小系数；对K个大系数的值和位置进行编码,从而到达压缩的目的.由CandesRomberg、Tao和Donoho等人在2

5、004年提出的压缩感知理论说明,可以在不丧失逼近原信号所需信息的情况下,用最少的观测次数来采样信号,实现信号的降维处理,即直接对信号进行较少采样得到信号的压缩表示,且不经过进行N次采样的中间阶段,从而在节约采样和传输本钱的情况下,到达了在采样的同时进行压缩的目的.CandeSE明了只要信号在某一个正交空间具有稀疏性,就能以较低的频率MN采样信号,而且可以以高概率重构该信号.即,设定设长度为N的信号X在某正交基或框架上的变换系数是稀疏的,如果我们可以用一个与变换基不相关的观测基：MNMN对系数向量进行线性变换,并得到观测集合Y:M1.那么就可以利用优化求解方法从观测集合中精确或高概率地重构原始信

6、号X.图2.2是基于压缩感知理论的信号重构过程框图.图2.2基于压缩感知理论的信号重构过程基于压缩感知的信号重构主要包含了信号的稀疏表示、编码测量和重构算法三个步骤.第一步,如果信号XRN在某个正交基或紧框架上是可压缩的,求出变换系数TX,是的等价或逼近的稀疏表示；第二步,设计一个平稳的、与变换基不相关的MN维的观测矩阵,对进行观测得到观测集合YTX,该过程也可以表示为信号X通过矩阵ACS进行非自适应观测：YACS(其中ACST),ACS称为CSJ息算子；第三步,利用0-范数意义下的优化问题求解X的精确或近似逼近父：minTX|s.t.ACSXTXY(2.2)求得的向量X在基上的表小最稀疏.针

7、对上述的三个步骤,下面将一一解决其中的三个问题.2.1 信号的稀疏表示压缩感知的第一步即,对于信号Xern,如何找到某个正交基或紧框架,使其在上的表示是稀疏的,即信号的稀疏表示问题.所谓的稀疏,就是指信号X在正交基下的变换系数向量为tx,假设对于0p2和R0,这些系数满足：i/pIIIpJR(2.3)那么说明系数向量在某种意义下是稀疏的.如何找到信号最正确的稀疏域？这是压缩感知理论应用的根底和前提,只有选择适宜的基表示信号才能保证信号的稀疏度,从而保证信号的恢复精度.在研究信号的稀疏表示时,可以通过变换系数衰减速度来衡量变换基的稀疏表示水平.CandesF口TaoW究说明,满足具有幕次速度衰减

8、的信号,可利用压缩感知理论得到恢复,并且重构误差满足：Cr(K/logN)6r(2.4)其中r=1/p-1/2,0<p<1.文献8指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabo添数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性,可以通过压缩感知理论恢复信号.如何找到或构造适合一类信号的正交基,以求得信号的最稀疏表示,这是一个有待进一步研究的问题.Peyre把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典.即在某个正交基字典里,自适应地寻找可以逼近某一种信号特征的最优正交基,根据不同的信号寻找最适合信号特性的一

9、个正交基,对信号进行变换以得到最稀疏的信号表示.对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解.这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数,称之为冗余字典,字典中的元素被称为原子.字典的选择应尽可能好地符合被逼近信号的结构,其构成可以没有任何限制.从冗余字典中找到具有最正确线性组合的K项原子来表示一个信号,称作信号的稀疏逼近或高度非线性逼近.从非线性逼近角度来讲,信号的稀疏逼近包含两个层面：一是根据目标函数从一个给定的基库中挑选好的或最好的基；二是从这个好的基中挑选最正确的侬组合.因此,目前信号在冗余字典下的稀疏表示的研究集中在两个方面：(1)如何构造一个适合某一类信号

10、的冗余字典；(2)如何设计快速有效的稀疏分解算法.在构造冗余字典方面,文献16中提出使用局部Cosine8来刻画声音信号的局部频域特性；利用bandleit来刻画图像中的几何边缘；还可以把其它的具有不同形状的基函数归入字典,如适合刻画纹理的Gabor基、适合刻画轮廓的Curvelet2t等等.在稀疏分解算法的设计方面,基于贪婪迭代思想的MP(MatchingPursuit)算法表现出极大的优越性,但不是全局最优解.Donoho等人之后提出了基追踪(basispursuit,BP)算法.BP算法具有全局最优的优点,但计算复杂度极高.之后又出现了一系列同样基于贪婪迭代思想的改良算法,如正交匹配追踪

11、算法(OMP),分段匹配追踪(StOMP)算法等.2.2 测量矩阵的选取如何设计一个平稳的、与变换基不相关的MN维的观测矩阵,保证稀疏向量从N维降到M维时重要信息不遭破坏,是第二步要解决的问题,也就是信号低速采样问题.压缩感知理论中,通过变换得到信号的稀疏系数向量TX后,需要设计压缩采样系统的观测局部,它围绕观测矩阵展开.观测器的设计目的是如何采样得到M个观测值,并保证从中能重构出长度为N的信号X或者基下等价的稀疏系数向量.显然,如果观测过程破坏了X中的信息,重构是不可能的.观测过程实际就是利用MN观测矩阵的M个行向量jM对稀疏系数向量进行投影,即计jji算和各个观测向量M之间的内积,得到M个

12、观测值jjiYj,jj1,2,M,记观测向量Y(yi,y2,Ym),即YTXACSX(2.5)这里,采样过程是非自适应的,也就是说,无须根据信号X而变化,观测的不再是信号的点采样而是信号的更一般的K线性泛函.对于给定的Y从式(2.5)中求出是一个线性规划问题,但由于MN,即方程的个数少于未知数的个数,这是一个欠定问题,一般来讲无确定解.然而,如果具有K-项稀疏性(KM),那么该问题有望求出确定解.此时,只要设法确定出中的K个非零系数i的适宜位置,由于观测向量Y是这些非零系数i对应的K个列向量的线性组合,从而可以形成一个MK的线性方程组来求解这些非零项的具体值.对此,有限等距性质给出了存在确定解

13、的充要条件.这个充要条件和CandesTa常人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致.即,要想使信号完全重构,必须保证观测矩阵不会把两个不同的K-项稀疏信号映射到同一个采样集合中,这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的.从中可以看出,问题的关键是如何确定非零系数的位置来构造出一个可解的MK线性方程组.然而,判断给定的ACS是否具有RIP性质是一个组合复杂度问题.为了降低问题的复杂度,能否找到一种易于实现RIP条件的替代方法成为构造观测矩阵的关键.文献10指出如果保证观测矩阵和稀疏基不相干,那么ACS在很大概率上满足RIP性质.不相干是指向量j不能用i稀疏表示

14、.不相干性越强,互相表示时所需的系数越多；反之,相关性那么越强.通过选择高斯随机矩阵作为即可高概率保证不相干性和RIP性质.例如,可以生成多个零均值、方差为1/N的随机高斯函数,将它们作为观测矩阵的元素>使得ACS以很高的概率具有RIP性质.随机高斯矩阵具有一个有用的性质：对于一个MN的随机高斯矩阵,可以证实当M?cKlog(N/K)时TACS在很大概率下具有RIP性质(其中久一个很小的常数).因此可以从M个观测值Y(yi,y2,yM)中以很高的概率去恢复长度为N的K-项稀疏信号.总之,随机高斯矩阵与大多数固定正交基构成的矩阵不相关,这一特性决定了选它作为观测矩阵,其它正交基作为稀疏变换

15、基时,ACS满足RIP性质.为进一步简化观测矩阵,在某些条件下,以随机1为元素构成的Rademache矩阵也可以证实具有RIP性质和普适性.对观测矩阵的研究是压缩感知理论的一个重要方面.Donoho给出了观测矩阵所必需具备的三个条件,并指出大局部一致分布的随机矩阵都具备这三个条件,均可作为观测矩阵,如：局部Fourier集、局部Hadamar狄、一致分布的随机投影(uniformRandomProjection课等,这与对RIP性质进行研究得出的结论相一致.但是,使用上述各种观测矩阵进行观测后,都仅仅能保证以很高的概率去恢复信号,而不能保证百分之百地精确重构信号.对于任何稳定的重构算法是否存在

16、一个真实确实定性的观测矩阵仍是一个有待研究的问题.2.3 信号重构如何设计快速重构算法,从线性观测YACSX中恢复信号,是第三步要将解决的问题,即信号的重构问题.在压缩感知理论中,由于观测数量M远小于信号长度N,因此不得不面对求解欠定方程组YACSX的问题.外表上看,求解欠定方程组似乎是无望的,但是,文献8和4均指出由于信号X是稀疏的或可压缩的,这个前提从根本上改变了问题,使得问题可解,而观测矩阵具有RIP性质也为从M个观测值中精确恢复信号提供了理论保证.为更清楚地描述压缩感知理论的信号重构问题,首先定义向量Xx,x2,xn的p范数为:NL凶.xp2.6当p0时得到0范数,它实际上表示X中非零

17、项的个数.于是,在信号X稀疏或可压缩的前提下,求解欠定方程组YACSX的问题转化为最小0范数问题：min|TX|Os.t.ACSXTXY2.7但是,它需要列出M中所有非零项位置的CK备种可能的线性组合,才能得到最优解.因此,求解式2.7的数值计算极不稳定而且是NF®问题.注意,这和稀疏分解问题从数学意义上讲是同样的问题.于是稀疏分解的已有算法可以应用到CS重构中.Chen,Donoho和SaunderS旨出,求解一个更加简单的I1优化问题会产生同等的解要求和不相关：min|TX1s.t.ACSXTXY2.8稍微的差异使得问题变成了一个凸优化问题,于是可以方便地化简为线性规划问题,典型

18、算法代表：BFW法.尽管BFW法可行,但在实际应用中存在两个问题：第一,即使是常见的图像尺寸,算法的计算复杂度也难以忍受,在采样点个数满足McK,c10g2N/K1时,重构计算复杂度的量级在ON3;第二,由于1范数无法区分稀疏系数尺度的位置,所以尽管整体上重构信号在欧氏距离上逼近原信号,但存在低尺度能量搬移到了高尺度的现象,从而容易出现一些人工效应,如一维信号会在高频出现振荡.基于上述问题,2005年1月CandeSf口Romberg提出了不同的信号恢复方法,该方法要求对原信号具有少量的先验知识,同时也可以对所求结果施加适当的期望特性,以约束重构信号的特性.通过在凸集上交替投影的方法,可以快速

19、求解线性规划问题.Tropp和Gilbert提出利用匹配追踪MP和正交匹配追踪OMP算法来求解优化问题重构信号,大大提升了计算的速度,且易于实现.树形匹配追踪TMP肝法是2005年La和NDo提出的.该方法针对BP、MP和OMP方法没有考虑信号的多尺度分解时稀疏信号在各子带位置的关系,将稀疏系数的树型结构加以利用,进一步提升了重构信号的精度和求解的速度.匹配追踪类算法都是基于贪婪迭代算法,以多于BPU法需要的采样数目换取计算复杂度的降低.例如OMP算法,需要McK,c2ln(N)个采样点数才能以较高的概率恢复信号,信号重构的计算复杂度为O(NK2).2006年Donoho等人提出了分段正交匹配追踪(STOMP,stagewiseOMP)算法.它将OMP进行一定程度的简化,以逼近精度为代价进一步提升了计算速度(计算复杂度为O(N),