压缩感知原理(附程序)
1压缩感知引论
传统方式下的信号处理，是按照奈奎斯特采样定理对信号进行采样，得到大量的采样数据，需要先获取整个信号再进行压缩，其压缩过程如图2.1。
图2.1 传统的信号压缩过程
在此过程中，大部分采样数据将会被抛弃，即高速采样后再压缩的过程浪费了大量的采样资源，这就极大地增加了存储和传输的代价。
由于带宽的限制，许多信号只包含少量的重要频率的信息。
所以大部分信号是稀疏的或是可压缩的，对于这种类型的信号，既然传统方法采样的多数数据会被抛弃，那么，为什么还要获取全部数据而不直接获取需要保留的数据呢？Candes和Donoho等人于2004年提出了压缩感知理论。
该理论可以理解为将模拟数据节约地转换成压缩数字形式，避免了资源的浪费。
即，在采样信号的同时就对数据进行适当的压缩，相当于在采样过程中寻找最少的系数来表示信号，并能用适当的重构算法从压缩数据中恢复出原始信号。
压缩感知的主要目标是从少量的非适应线性测量中精确有效地重构信号。
核心概念在于试图从原理上降低对一个信号进行测量的成本。
压缩感知包含了许多重要的数学理论，具有广泛的应用前景，最近几年引起广泛的关注，得到了蓬勃的发展。
2压缩感知原理
压缩感知，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号进行信号重构的技术。
或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。
压缩感知跳过了采集N个样本这一步骤，直接获得压缩的信号的表示。
CS理论利用到了许多自然信号在特定的基 上具有紧凑的表示。
即这些信号是“稀疏”的或“可压缩”的。
由于这一特性，压缩感知理论的信号编解码框架和传统的压缩过程大不一样，主要包括信号的稀疏表示、编码测量和重构算法等三个方面。
对于一个实值的有限长一维离散时间信号X ，可以看作为一个N R 空间N ×1的维的列向量，元素为[]n ，n ,=1，2，…N 。
N R 空间的任何信号都可以用N ×1维的基向量{}1i N
i =ψ的线性组合表示。
为简化问题，假定这些基是规范正交的。
把向量{}1i N
i =ψ作为列向量形成N N ⨯的基矩阵ψ：=[12,,ψψ ⋯ ,N ψ]，于是任意信号X 都可以表示为： X =ψΘ (2.1)
其中Θ是投影系数Θ=[],i i X θ=⎡ψ⎤⎣⎦构成的N ×1的列向量。
显然，X 和Θ是同一个信号的等价表示，X 是信号在时域的表示，Θ则是信号在ψ域的表示。
如果Θ的非零个数比N 小很多，则表明该信号是可压缩的。
一般而言，可压缩信号是指可以用K 个大系数很好地逼近的信号，即它在某个正交基下的展开的系数按一定量级呈现指数衰减，具有非常少的大系数和许多小系数。
这种通过变换实现压缩的方法称为变换编码。
在数据采样系统中，采样速率高但信号是可压缩的，采样得到N 点采样信号X ；通过T X Θ=ψ变换后计算出完整的变换系数集合{}i θ；确定K 个大系数的位置，然后扔掉N K -个小系数；对K 个大系数的值和位置进行编码，从而达到压缩的目的。
由Candes 、Romberg 、Tao 和Donoho 等人在2004年提出的压缩感知理论表明，可以在不丢失逼近原信号所需信息的情况下，用最少的观测次数来采样信号，实现信号的降维处理，即直接对信号进行较少采样得到信号的压缩表示，且不经过进行N 次采样的中间阶段，从而在节约采样和传输成本的情况下，达到了在采样的同时进行压缩的目的。
Candes 证明了只要信号在某一个正交空间具有稀疏性，就能以较低的频率()M N <<采样信号，而且可以以高概率重构该信号。
即，设定设长度为N 的信号X 在某正交基或框架ψ上的变换系数是稀疏的，如果我们可以用一个与变换基ψ不相关的观测基 ：M N ⨯()M N <<对系数向量进行线性变换，并得到观测集合:1Y M ⨯。
那么就可以利用优化求解方法从观测集合中精确或高概率地重构原始信号X 。
图2.2是基于压缩感知理论的信号重构过程框图。
图2.2 基于压缩感知理论的信号重构过程
基于压缩感知的信号重构主要包含了信号的稀疏表示、编码测量和重构算法三个步骤。
第一步，如果信号X ∈N R 在某个正交基或紧框架ψ上是可压缩的，求出变换系数T X Θ=ψ，Θ是ψ的等价或逼近的稀疏表示；第二步，设计一个平稳的、与变换基ψ不相关的M N ⨯维的观测矩阵Φ，对Θ进行观测得到观测集合T Y X =ΦΘ=Φψ，该过程也可以表示为信号X 通过矩阵CS A 进行非自适应观测：CS Y A = (其中CS T A =Φψ)，CS A 称为CS 信息算子；第三步，利用0-范数意义下的优
化问题求解X 的精确或近似逼近ˆX
： 0
min T X ψ s.t. CS T A X X Y =Φψ= (2.2) 求得的向量X 在基上的表示最稀疏。
针对上述的三个步骤，下面将一一解决其中的三个问题。
2.1 信号的稀疏表示
压缩感知的第一步即，对于信号X ∈N R ，如何找到某个正交基或紧框架ψ，使其在ψ上的表示是稀疏的，即信号的稀疏表示问题。
所谓的稀疏，就是指信号X 在正交基下的变换系数向量为T X Θ=ψ，假如对于02p <<和0R >，这些系数满足：
1/P P i P i R θ⎛⎫Θ≡≤ ⎪⎝⎭∑ (2.3)
则说明系数向量Θ在某种意义下是稀疏的。
如何找到信号最佳的稀疏域？这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。
在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。
Candes 和Tao 研究表明，满足具有幂次速度衰减的信号，可利用压缩感知理论得到恢复，并且重构误差满足：
62ˆ(/log )r r E X X C K N -=-≤⋅ (2.4)
其中r=1/p – 1/2，0<p<1.
文献[8]指出光滑信号的Fourier 系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor 系数及具有不连续边缘的图像信号的Curvelet 系数等都具有足够的稀疏性，可以通过压缩感知理论恢复信号。
如何找到或构造适合一类信号的正交基，以求得信号的最稀疏表示，这是一个有待进一步研究的问题。
Peyre 把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典。
即在某个正交基字典里，自适应地寻找可以逼近某一种信号特征的最优正交基，根据不同的信号寻找最适合信号特性的一个正交基，对信号进行变换以得到最稀疏的信号表示。
对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。
这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。
字典的选择应尽可能好地符合被逼近信号的结构，其构成可以没有任何限制。
从冗余字典中找到具有最佳线性组合的K 项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近。
从非线性逼近角度来讲，信号的稀疏逼近包含两个层面：一是根据目标函数从一个给定的基库中挑选好的或最好的基；二是从这个好的基中挑选最佳的K 项组合。
因此，目前信号在冗余字典下的稀疏表示的研究集中在两个方面：(1)如何构造一个适合某一类信号的冗余字典；(2)如何设计快速有效的稀疏分解算法。
在构造冗余字典方面，文献[16]中提出使用局部Cosine 基来刻画声音信号的局部频域特性；利用bandlet 基来刻画图像中的几何边缘；还可以把其它的具有不同形状的基函数归入字典，如适合刻画纹理的Gabor 基、适合刻画轮廓的Curvelet 基等等。
在稀疏分解算法的设计方面，基于贪婪迭代思想的MP(Matching Pursuit)算法表现出极大的优越性，但不是全局最优解。
Donoho 等人之后提出了基追踪(basis
pursuit ，BP)算法。
BP 算法具有全局最优的优点，但计算复杂度极高。
之后又出现了一系列同样基于贪婪迭代思想的改进算法，如正交匹配追踪算法(OMP)，分段匹配追踪(StOMP)算法等。
2.2 测量矩阵的选取
如何设计一个平稳的、与变换基ψ不相关的M N ⨯维的观测矩阵Φ，保证稀疏向量Θ从N 维降到M 维时重要信息不遭破坏，是第二步要解决的问题，也就是信号
低速采样问题。
压缩感知理论中，通过变换得到信号的稀疏系数向量T X Θ=ψ后，需要设计压缩采样系统的观测部分，它围绕观测矩阵Φ展开．观测器的设计目的是如何采样得到M 个观测值，并保证从中能重构出长度为N 的信号X 或者基ψ下等价的稀疏系数向量Θ。
显然，如果观测过程破坏了X 中的信息，重构是不可能的。
观测过程实际就是利用M N ⨯观测矩阵Φ的M 个行向量{}1M
j j ϕ=对稀疏系数向量进行投影，即计算Θ和各个观测向量{}1M
j j ϕ=之间的内积，得到M 个观测值(),1,2,M j j y j ϕ=<Θ>=…,，记观测向量12(,,y )M Y y y =…，，即
T CS Y X A X =ΦΘ=Φψ= (2.5)
这里，采样过程是非自适应的，也就是说，Φ无须根据信号X 而变化，观测的不再是信号的点采样而是信号的更一般的K 线性泛函。
对于给定的Y 从式(2.5)中求出Θ是一个线性规划问题，但由于M N <<，即方程的个数少于未知数的个数，这是一个欠定问题，一般来讲无确定解。
然而，如果Θ具有K - 项稀疏性(K M <<)，则该问题有望求出确定解。
此时，只要设法确定出Θ中的K 个非零系数i θ的合适位置，由于观测向量Y 是这些非零系数i θ对应 的K 个列向量的线性组合，从而可以形成一个M K ⨯的线性方程组来求解这些非零项的具体值。
对此，有限等距性质给出了存在确定解的充要条件。
这个充要条件和Candes 、Tao 等人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致。
即，要想使信号完全重构，必须保证观测矩阵不会把两个不同的K -项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M 个列向量构成的矩阵是非奇异的。
从中可以看出，问题的关键是如何确定非零系数的位置来构造出一个可解的M K ⨯线性方程组。
然而，判断给定的CS A 是否具有RIP 性质是一个组合复杂度问题。
为了降低问题的复杂度，能否找到一种易于实现RIP 条件的替代方法成为构造观测矩阵的关键。
文献[10]指出如果保证观测矩阵Φ和稀疏基ψ不相干，则CS A 在很大概率上满足RIP 性质。
不相干是指向量{}j ϕ不能用{}i ψ稀疏表示。
不相干性越强，互相表示
时所需的系数越多；反之，相关性则越强．通过选择高斯随机矩阵Φ作为即可高概率保证不相干性和RIP 性质。
例如，可以生成多个零均值、方差为1/N 的随机高斯函数，将它们作为观测矩阵Φ的元素j ϕ，使得CS A 以很高的概率具有RIP 性质。
随机高斯矩阵具有一个有用的性质：对于一个M N ⨯的随机高斯矩阵Φ，可以证明当M ≥cKlog(N ／K)时T CS A Φψ= 在很大概率下具有RIP 性质(其中c 是一个很小的常数)。
因此可以从M 个观测值12(,,y )M Y y y =…，中以很高的概率去恢复长度为N 的K - 项稀疏信号。
总之，随机高斯矩阵与大多数固定正交基构成的矩阵不相关，这一特性决定了选它作为观测矩阵，其它正交基作为稀疏变换基时，CS A 满足RIP 性质。
为进一步简化观测矩阵Φ，在某些条件下，以随机1±为元素构成的Rademacher 矩阵也可以证明具有RIP 性质和普适性。
对观测矩阵的研究是压缩感知理论的一个重要方面。
Donoho 给出了观测矩阵所必需具备的三个条件，并指出大部分一致分布的随机矩阵都具备这三个条件，均可作为观测矩阵，如：部分Fourier 集、部分Hadamard 集、一致分布的随机投影(uniform Random Projection)集等，这与对RIP 性质进行研究得出的结论相一致。
但是，使用上述各种观测矩阵进行观测后，都仅仅能保证以很高的概率去恢复信号，而不能保证百分之百地精确重构信号。
对于任何稳定的重构算法是否存在一个真实的确定性的观测矩阵仍是一个有待研究的问题。
2.3 信号重构
如何设计快速重构算法，从线性观测CS Y A X =中恢复信号，是第三步要将解决的问题，即信号的重构问题。
在压缩感知理论中，由于观测数量M 远小于信号长度N ，因此不得不面对求解欠定方程组CS Y A X =的问题。
表面上看，求解欠定方程组似乎是无望的，但是，文献[8]和[4]均指出由于信号X 是稀疏的或可压缩的，这个前提从根本上改变了问题，使得问题可解，而观测矩阵具有RIP 性质也为从M 个观测值中精确恢复信号提供了理论保证。
为更清晰地描述压缩感知理论的信号重构问题，首先定义向量{}12,,n X x x =…，x 的p -范数为：
1/p
1N p i P i X x =⎛⎫= ⎪⎝⎭∑ (2.6) 当0p =时得到0-范数，它实际上表示X 中非零项的个数。
于是，在信号X 稀疏或可压缩的前提下，求解欠定方程组CS Y A X =的问题转化为最小0-范数问题： 0
min T X ψ s.t.CS T A X X Y =Φψ= (2.7) 但是，它需要列出M 中所有非零项位置的K N C 备种可能的线性组合，才能得到
最优解。
因此，求解式(2.7)的数值计算极不稳定而且是NP 难问题。
注意，这和稀疏分解问题从数学意义上讲是同样的问题。
于是稀疏分解的已有算法可以应用到CS 重构中。
Chen ，Donoho 和Saunders 指出，求解一个更加简单的1l 优化问题会产生同等的解(要求Φ和ψ不相关)：
1
min T X ψ s.t.CS T A X X Y =Φψ= (2.8) 稍微的差别使得问题变成了一个凸优化问题，于是可以方便地化简为线性规划问题，典型算法代表：BP 算法．尽管BP 算法可行，但在实际应用中存在两个问题：第一，即使是常见的图像尺寸，算法的计算复杂度也难以忍受，在采样点个数满足
M cK ≥，()2log /1c N K ≈+时，
重构计算复杂度的量级在3()O N ；第二，由于1-范数无法区分稀疏系数尺度的位置，所以尽管整体上重构信号在欧氏距离上逼近原信号，但存在低尺度能量搬移到了高尺度的现象，从而容易出现一些人工效应，如一维信号会在高频出现振荡。
基于上述问题，2005年1月Candes 和Romberg 提出了不同的信号恢复方法，该方法要求对原信号具有少量的先验知识，同时也可以对所求结果施加适当的期望特性，以约束重构信号的特性。
通过在凸集上交替投影的方法，可以快速求解线性规划问题。
Tropp 和Gilbert 提出利用匹配追踪(MP)和正交匹配追踪(OMP)算法来求解优化问题重构信号，大大提高了计算的速度，且易于实现。
树形匹配追踪(TMP)算法是2005
年La 和NDo 提出的。
该方法针对BP 、MP 和OMP 方法没有考虑信号的多尺度分解时稀疏信号在各子带位置的关系，将稀疏系数的树型结构加以利用，进一步提升了重构信号的精度和求解的速度。
匹配追踪类算法都是基于贪婪迭代算法，以多于BP 算法需要的采样数目换取计算复杂度的降低。
例如OMP 算法，需要M cK ≥，2ln()c N ≈个采样点数才能以较高的概率恢复信号，信号重构的计算复杂度为2()O NK 。
2006年Donoho 等人提出了分段正交匹配追踪(STOMP ，stagewise OMP)算法。
它将OMP 进行一定程度的简化，以逼近精度为代价进一步提高了计算速度(计算复杂度为O(N))，更加适合于求解大规模问题。
匹配追踪类方法为其近似求解提供了有力工具，且该类方法用于稀疏信号重建时具有一定的稳定性。
文献[8]中提出的OMP 算法延续了匹配追踪算法中原子的选择准则，但是实现了递归地对已选原子集合进行正交化以保证迭代的最优性，从而减少了迭代次数。
此后，Needell 和Vershynin 等人在OMP 算法的基础上将正则化过程用于稀疏度K 已知的OMP 算法中，提出了ROMP 算法。
ROMP 算法与OMP 算法的不同之处在于，该算法首先根据相关原子挑选多个原子作为候选集，然后从候选集中按照正则化原则挑选出部分原子，最后将其并入最终的支撑集，从而实现了原子的快速、有效选择。
最近出现的子空间匹配追踪算法(Subspace Pursuit ，SP)和压缩采样匹配追踪算法(Compressive Sampling Matching Pursuit ，CoSaMP)引入了回退筛选的思想，这些算法的重建质量与线性规划方法相当，同时重建复杂度低，但是这些算法都是建立在稀疏度K 已知的基础上。
然而实际应用中信号的稀疏度K 往往是未知的，由此出现了对稀疏度K 自适应的稀疏自适应匹配追踪算法(Sparsity
Adaptive Matching Pursuit, SAMP)，它通过设置一个可变步长，逐步对信号稀疏度进行估计，因此可以在K 未知的情况下获得较好的重建效果，速度也远快于OMP 算法。
基于ROMP 算法和SAMP 算法的突出优势，本文研究了兼有ROMP 算法和SAMP 算法优势的自适应正则化匹配追踪(RAMP)算法。
% (正交匹配追踪法Orthogonal Matching Pursuit)
clc;clear
%% 1. 时域测试信号生成
K=7; % 稀疏度(做FFT可以看出来)
N=256; % 信号长度
M=64; % 测量数(M>=K*log(N/K),至少40,但有出错的概率)
f1=50; % 信号频率1
f2=100; % 信号频率2
f3=200; % 信号频率3
f4=400; % 信号频率4
fs=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*t s)+0.9*cos(2*pi*f4*Ts*ts); % 完整信号
%% 2. 时域信号压缩传感
Phi=randn(M,N); % 测量矩阵（观测矩阵）
s=Phi*x'; % 获得线性测量
%% 3. 正交匹配追踪法重构信号(本质上是L_1范数最优化问题)
m=2*K; % 算法迭代次数(m>=K)
Psi=fft(eye(N,N))/sqrt(N); % 傅里叶正变换矩阵（正交基）
% Psi=dct2(256); %dct变换
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)'*r_n); % 恢复矩阵的列向量和残差的投影系数(内积值)
end
[val,pos]=max(product); % 最大投影系数对应的位置
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; % 纪录最大投影系数的位置
end
hat_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');。
