压缩感知原理

《压缩感知原理》由会员分享，可在线阅读，更多相关《压缩感知原理（13页珍藏版）》请在装配图网上搜索。

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

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

3、从而在很大程度上 降低了采样率。压缩感知跳过了采集N个样本这一步骤，直接获得压缩的信号的表 示。CS理论利用到了许多自然信号在特定的基 上具有紧凑的表示。即这些信号 是“稀疏”的或“可压缩”的。由于这一特性，压缩感知理论的信号编解码框架和 传统的压缩过程大不一样，主要包括信号的稀疏表示、编码测量和重构算法等三个 方面。对于一个实值的有限长一维离散时间信号X ,可以看作为一个RN空间N XI的维的列向量，元素为n , n ,=1, 2,N。RN空间的任何信号都可以用N XI维的 基向量卜N的线性组合表示。为简化问题，假定这些基是规范正交的。把向量 ii=1屮N作为列向量形成N xiN的基矩阵屮:

4、=屮,屮,12,屮，于是任意信号X都Ni =1可以表示为：X二屮0(2.1)其中0是投影系数0 = 0 =； X,屮构成的N XI的列向量。显然，X和0是 同一个信号的等价表示，X是信号在时域的表示，0则是信号在屮域的表示。如果 0的非零个数比 N 小很多，则表明该信号是可压缩的。一般而言，可压缩信号是指 可以用K个大系数很好地逼近的信号，即它在某个正交基下的展开的系数按一定量 级呈现指数衰减，具有非常少的大系数和许多小系数。这种通过变换实现压缩的方 法称为变换编码。在数据采样系统中，采样速率高但信号是可压缩的，采样得到N 点采样信号X ；通过0 =屮TX变换后计算出完整的变换系数集合0 ；确

5、定K个大i系数的位置，然后扔掉N-K个小系数；对K个大系数的值和位置进行编码，从而 达到压缩的目的。由Candes、Romberg、Tao和Donoho等人在2004年提出的压缩感知理论表明，可 以在不丢失逼近原信号所需信息的情况下，用最少的观测次数来采样信号，实现信 号的降维处理，即直接对信号进行较少采样得到信号的压缩表示，且不经过进行N 次采样的中间阶段，从而在节约采样和传输成本的情况下，达到了在采样的同时进 行压缩的目的。Candes证明了只要信号在某一个正交空间具有稀疏性，就能以较低 的频率（M N）采样信号，而且可以以高概率重构该信号。即，设定设长度为N的 信号X在某正交基或框架屮上

6、的变换系数是稀疏的，如果我们可以用一个与变换基 屮不相关的观测基：M x N（M N ）对系数向量进行线性变换，并得到观测集合 Y : M x 1。那么就可以利用优化求解方法从观测集合中精确或高概率地重构原始信 号X。图2.2是基于压缩感知理论的信号重构过程框图。图2.2基于压缩感知理论的信号重构过程基于压缩感知的信号重构主要包含了信号的稀疏表示、编码测量和重构算法三 个步骤。第一步，如果信号X e Rn在某个正交基或紧框架屮上是可压缩的，求出 变换系数0 = tX，0是屮的等价或逼近的稀疏表示；第二步，设计一个平稳的、 与变换基屮不相关的MxN维的观测矩阵，对0进行观测得到观测集合Y = 0

7、0 = 0tX，该过程也可以表示为信号X通过矩阵Acs进行非自适应观测：Y = Acs (其中Acs =屮t)，Acs称为CS信息算子；第三步，利用0-范数意义下的优 化问题求解X的精确或近似逼近X :min| 屮 tx| s.t. AcsX =屮 tX = Y(2.2)求得的向量 X 在基上的表示最稀疏。针对上述的三个步骤，下面将一一解决其中的三个问题。2.1 信号的稀疏表示压缩感知的第一步即，对于信号X e Rn，如何找到某个正交基或紧框架屮， 使其在屮上的表示是稀疏的，即信号的稀疏表示问题。所谓的稀疏，就是指信号X在正交基下的变换系数向量为0 =屮tX，假如对于 0 p 0，这些系数满足

8、：l|0|p、i/p Ip(2.3)则说明系数向量0在某种意义下是稀疏的。如何找到信号最佳的稀疏域？这是 压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏 度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减 速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明，满足具有幂次速度衰减 的信号，可利用压缩感知理论得到恢复，并且重构误差满足：X - X” C - (K /logN)一6 r(2.4)其中r=l/p 1/2, Ovpvl.文献指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、 振荡信号的Gabor系数及具有不连续

9、边缘的图像信号的Curvelet系数等都具有足够的 稀疏性,可以通过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基, 以求得信号的最稀疏表示，这是一个有待进一步研究的问题。Peyre把变换基是正交 基的条件扩展到了由多个正交基构成的正交基字典。即在某个正交基字典里,自适 应地寻找可以逼近某一种信号特征的最优正交基，根据不同的信号寻找最适合信号 特性的一个正交基，对信号进行变换以得到最稀疏的信号表示。对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一种全新 的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的 元素被称为原子。字典的选择应尽可能好地符合被

10、逼近信号的结构，其构成可以没 有任何限制。从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称 作信号的稀疏逼近或高度非线性逼近。从非线性逼近角度来讲，信号的稀疏逼近包 含两个层面：一是根据目标函数从一个给定的基库中挑选好的或最好的基；二是从 这个好的基中挑选最佳的K项组合。因此，目前信号在冗余字典下的稀疏表示的研究 集中在两个方面：(1)如何构造一个适合某一类信号的冗余字典；(2)如何设计快速有 效的稀疏分解算法。在构造冗余字典方面，文献16中提出使用局部Cosine基来刻画声音信号的局部 频域特性；利用bandlet基来刻画图像中的几何边缘；还可以把其它的具有不同形状 的基函数归入

11、字典，如适合刻画纹理的Gabor基、适合刻画轮廓的Curvelet基等等。 在稀疏分解算法的设计方面，基于贪婪迭代思想的MP(Matching Pursuit)算法表现出 极大的优越性，但不是全局最优解。Donoho等人之后提出了基追踪(basis pursuit， BP)算法。BP算法具有全局最优的优点，但计算复杂度极高。之后又出现了一系列 同样基于贪婪迭代思想的改进算法，如正交匹配追踪算法(OMP)，分段匹配追踪 (StOMP)算法等。2.2 测量矩阵的选取如何设计一个平稳的、与变换基屮不相关的MxN维的观测矩阵，保证稀疏向量0从N维降到M维时重要信息不遭破坏，是第二步要解决的问题，也就是

12、信号 低速采样问题。压缩感知理论中，通过变换得到信号的稀疏系数向量0 = TX后，需要设计压 缩采样系统的观测部分，它围绕观测矩阵展开.观测器的设计目的是如何采样得 到M个观测值，并保证从中能重构出长度为N的信号X或者基屮下等价的稀疏系 数向量0。显然，如果观测过程破坏了X中的信息，重构是不可能的。观测过程实 际就是利用M x N观测矩阵的M个行向量（p h对稀疏系数向量进行投影，即计j j =1算0和各个观测向量（ph 之间的内积，得到M个观测值j j =1y =（j = 1,2,M），记观测向量 Y = （y , y，y ），即jj12MY = O0 =屮 tX = AcsX（2.5）这里

13、，采样过程是非自适应的，也就是说，无须根据信号x而变化，观测的 不再是信号的点采样而是信号的更一般的K线性泛函。对于给定的Y从式（2.5）中求出0是一个线性规划问题，但由于M N，即方 程的个数少于未知数的个数，这是一个欠定问题，一般来讲无确定解。然而，如果0 具有K -项稀疏性（K cK，c沁log2(N / K +1)时，重构计算复杂度的量级在O(N3)；第二，由于1-范 数无法区分稀疏系数尺度的位置，所以尽管整体上重构信号在欧氏距离上逼近原信 号，但存在低尺度能量搬移到了高尺度的现象，从而容易出现一些人工效应，如一 维信号会在高频出现振荡。基于上述问题，2005年1月Candes和Rom

14、berg提出了不同的信号恢复方法，该方 法要求对原信号具有少量的先验知识，同时也可以对所求结果施加适当的期望特性， 以约束重构信号的特性。通过在凸集上交替投影的方法，可以快速求解线性规划问 题。Tropp和Gilbert提出利用匹配追踪(MP)和正交匹配追踪(OMP )算法来求解优化 问题重构信号，大大提高了计算的速度，且易于实现。树形匹配追踪(TMP)算法是2005 年La和NDo提出的。该方法针对BP、MP和OMP方法没有考虑信号的多尺度分解时 稀疏信号在各子带位置的关系，将稀疏系数的树型结构加以利用，进一步提升了重 构信号的精度和求解的速度。匹配追踪类算法都是基于贪婪迭代算法，以多于BP

15、算 法需要的采样数目换取计算复杂度的降低。例如OMP算法，需要M cK，c沁21n(N) 个采样点数才能以较高的概率恢复信号，信号重构的计算复杂度为O(NK2)。2006 年Donoho等人提出了分段正交匹配追踪(STOMP, stagewise OMP)算法。它将OMP 进行一定程度的简化，以逼近精度为代价进一步提高了计算速度(计算复杂度为 O(N)，更加适合于求解大规模问题。匹配追踪类方法为其近似求解提供了有力工具，且该类方法用于稀疏信号重建 时具有一定的稳定性。文献8中提出的OMP算法延续了匹配追踪算法中原子的选择 准则，但是实现了递归地对已选原子集合进行正交化以保证迭代的最优性，从而减

16、 少了迭代次数。此后，Needell和Vershynin等人在OMP算法的基础上将正则化过 程用于稀疏度K已知的OMP算法中，提出了ROMP算法。ROMP算法与OMP算法的 不同之处在于，该算法首先根据相关原子挑选多个原子作为候选集，然后从候选集 中按照正则化原则挑选出部分原子，最后将其并入最终的支撑集，从而实现了原子 的快速、有效选择。最近出现的子空间匹配追踪算法(Subspace Pursuit，SP)和压缩采 样匹配追踪算法(Compressive Sampling Matching Pursuit ，CoSaMP)引入了回退筛选 的思想，这些算法的重建质量与线性规划方法相当，同时重建复

17、杂度低，但是这些 算法都是建立在稀疏度K已知的基础上。然而实际应用中信号的稀疏度K往往是未 知的，由此出现了对稀疏度K自适应的稀疏自适应匹配追踪算法(Sparsity Adaptive Matching Pursuit, SAMP)，它通过设置一个可变步长，逐步对信号稀疏度进行估计， 因此可以在K未知的情况下获得较好的重建效果，速度也远快于OMP算法。基于 ROMP算法和SAMP算法的突出优势，本文研究了兼有ROMP算法和SAMP算法优势 的自适应正则化匹配追踪(RAMP)算法。% (正交匹配追踪法Ort hogonal Ma tching Pursui t)clc;clear% 1. 时域测

18、试信号生成K=7;%稀疏度（做FFT可以看出来）N=256;% 信号长度M=64;%测量数（M=K*log（N/K），至少40,但有出错的概率）f1=50;% 信号频率1f2=100;% 信号频率2f3=200;% 信号频率3f4=400;% 信号频率4fs=800;% 采样频率ts=1/fs;% 采样间隔Ts=1:N;% 采样序列x=0.3*cos(2*pi*f1*Ts*ts)+0.6*cos(2*pi*f2*Ts*ts)+0.1*cos(2*pi*f3*Ts*ts)+0.9*cos(2*pi*f4*Ts*ts);% 完整信号% 2. 时域信号压缩传感Phi=randn（M,N）;% 测量矩

19、阵（观测矩阵）s=Phi*x;% 获得线性测量% 3.正父匹配追踪法重构信号（本质上是L_1范数最优化问题）m=2*K;(m=K)Psi=fft(eye(N,N)/sqrt(N);阵(正父基)% Psi二de t2(256);%dc t变换T=Phi*Psi;阵*正父反变换矩阵)hat_y=zeros(1,N);换域)向量Aug_t=;为空矩阵)r_n=s;for times=1:m;的情况下,该迭代次数为K)for col=1:N;列向量product(col)=abs(T(:,col)量和残差的投影系数(内积值)endval,pos=max(product);应的位置% 算法迭代次数% 傅

20、里叶正变换矩% 恢复矩阵（测量矩% 待重构的谱域（变% 增量矩阵（初始值% 残差值%迭代次数（有噪声%恢复矩阵的所有_n);%恢复矩阵的列向% 最大投影系数对% 矩阵扩充Aug_t=Aug_t,T(:,pos);T(:,pos)=zeros(M,1);质上应该去掉，为了简单我把它置零)% 选中的列置零(实aug_y=(Aug_t，* Aug_t)“(-1)* Aug_t，*s;最小% 最小二乘,使残差r_n=s-Aug_t*aug_y;pos_array(times)=pos;数的位置endhat_y(pos_array)=aug_y;hat_x=real(Psi，*hat_y.，);重构得到时域信号% 残差% 纪录最大投影系% 重构的谱域向量% 做逆傅里叶变换% 4. 恢复信号和原始信号对比figure(1);hold on;plot(hat_x,，k.-，)figure(2);plot(x,，r，)%legend(，Recovery，,，Original，) norm(hat_x.，-x)/norm(x)% 重建信号% 原始信号% 重构误差Q=abs(hat_x，-x);figure(3);plot(Q,，r，);11