压缩感知的重构算法

压缩感知的重构算法

算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。

压缩感知的重构算法主要分为三大类：

1.组合算法

2.贪婪算法

3.凸松弛算法

每种算法之中又包含几种算法，下面就把三类重构算法列举出来。

组合算法：先是对信号进行结构采样，然后再通过对采样的数据进行分组测试，最后完成信号的重构。

(1) 傅里叶采样（Fourier Representaion）

(2) 链式追踪算法（Chaining Pursuit）

(3) HHS追踪算法（Heavy Hitters On Steroids）

贪婪算法：通过贪婪迭代的方式逐步逼近信号。

(1) 匹配追踪算法（Matching Pursuit MP）

(2) 正交匹配追踪算法（Orthogonal Matching Pursuit OMP）

(3) 分段正交匹配追踪算法（Stagewise Orthogonal Matching Pursuit StOMP）

(4) 正则化正交匹配追踪算法（Regularized Orthogonal Matching Pursuit ROMP）

(5) 稀疏自适应匹配追踪算法（Sparisty Adaptive Matching Pursuit SAMP）

凸松弛算法：

(1) 基追踪算法（Basis Pursuit BP）

(2) 最小全变差算法（Total Variation TV）

(3) 内点法（Interior-point Method）

(4) 梯度投影算法（Gradient Projection）

(5) 凸集交替投影算法（Projections Onto Convex Sets POCS）算法较多，但是并不是每一种算法都能够得到很好的应用，三类算法各有优缺点，组合算法需要观测的样本数目比较多但运算的效率最高，凸松弛算法计算量大但是需要观测的数量少重构的时候精度高，贪婪迭代算法对计算量和精度的要求居中，也是三种重构算法中应用最大的一种。下面分别就贪婪算法中的MP，OMP算法以及凸松弛算法中的BP算法进行详细的介绍。

三种重建算法

本节主要是介绍一些基本的重建算法，比如贪婪迭代算法中的匹配追踪算法，正交匹配追踪算法，以及凸松弛算法中的基追踪算法，对其原理进行了介绍，并用matlab代码重构出来一维和二维的图形，进而比较这几种算法的性能。

1.匹配追踪算法（Matching Pursuit MP ）

匹配追踪算法是Mallat 和ZHANG 在小波分析的基础上提出的，是贪婪迭代算法中的比较基本的算法，有其显著的特点，是学习研究贪婪算法的基础。

1.1 MP 算法的原理

x y Φ=，其中测量矩阵Φ又称为过完备字典，每一列被称为一个原子，则测量矩阵中有n 个原子，而y 的长度为m ，原子的个数远远大于信号的长度，即m<

量长度为1，要对过完备字典的原子进行归一化处理。

MP 算法的基本思想：

从观测矩阵（过完备字典）中选择一个与信号y 相关性最大（最匹配）的原子，也就是观测矩阵中的一列，构建信号的稀疏逼近，求出信号的残差，重复上面的操作，继续选择与信号残差最匹配的一个原子，如此反复迭代直到达到迭代次数，最后信号y 就可以表示为这些原子的线性组合。

MP 进行稀疏分解的步骤[1][2]：

从观测矩阵中选择一个与信号y 最匹配的原子，也就是内积最大的一个原子，即：

||=sup )

,...1(n i ∈|| （1） 其中，Γ0表示字典矩阵的列索引。先将信号y 投影到向量 Φ∈Γ?0

上，信号y 也可以表示为：

R y y 100,+Γ>Γ=

(2)式等号右边的第一项为观测矩阵中最匹配原子

?Γ0的垂直投影分量，等式右边的第二项R 1是y 通过?Γ0分解后的残差，且与y 正交。

（2）式可以写为：

|||||,|||||1022

2R y y +Γ=>

R R R n n n n n 1,++Γ>Γ=

|||||,|||

||1222R R R n n n n ++Γ=>

R y n i n i i i y 10,+=+Γ>Γ<

=∑?? （6）

因为最后的残差R n 1+正交于上次迭代产生的残差R n ，则最后的表达式为：

|||||,|||||12

2

2R y y n i n o i ++Γ=><∑=? （7） 由（7）式可知，当残差R n 1+为零时，可以得到信号的精确分解。

定理1[3] 存在0>λ，使得一切对于0≥n 时，有||||||||21y n n R λ-+≤成立。

这样（7）式中，||||1R n +按照指数衰减的形式趋于零，也就是

|,|||||2

02

><∑Γ==?i y y n i 成立。 参考文献：

[1] 曹离然.面向压缩感知的稀疏信号重建算法研究.[D].哈尔滨工业大学，2011.

[2] Y .C.PATI.Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition.IEEE.1993:40-44

[3] 韩红平.压缩感知中信号重构算法的研究.[D].南京邮电大学，2012.

1.2 MP 算法的理论框图

根据上面的MP 算法的原理，得出MP 算法的理论图[1]，这样更容易理解。

图1：MP算法框图

参考文献：[1] 韩红平.压缩感知中信号重构算法的研究[D].南京邮电大学，2012

1.3 MP 算法的算法流程

根据1.2中介绍的MP 算法的理论框图，现在写出MP 算法的算法流程[1][2]，这样让我们对MP 算法有一个更加清晰的理解。 输入：测量矩阵)(N M ?Φ，测量向量)1(?N y ，稀疏度k 输出：重构信号∧x

（1）：初始化余量y r =0，迭代次数n=0 1；

（2）：计算余量与测量矩阵的每一列的内积r g n T n 1-Φ=；共有N 个

内积数值。

(3)：找出N 个g n 中的绝对值最大的元素)(k g n ，k 为对应的最大内积的列号。

（4）：计算信号的近似解][][][1k k k g x x n n n +=-；

（5）：更新余量?k n n n k g r r ?-=-][1；

（6）：若满足迭代条件，则n=n+1，x n x =∧，若不满足迭代条件则返回步骤（2）；迭代次数为稀疏度的2倍。

参考文献：

[1] Linfeng Du,Rui Wang. Analysis on Greedy Reconstruction Algorithms Based on Compressed Sensing.[J].IEEE 2012:783-789

[2] 文首先.压缩感知匹配追踪算法的研究.[D].2013

1.4 MP 算法的信号重构

本节分别通过对一维离散信号，二维Lena 为例，进行MP 算法的信号重构。

（1）一维离散信号的MP算法仿真

本次仿真使用matlab随机生成的一维离散信号，稀疏度k=23,信号长度N=256，观测向量的长度M=80，那么采样率M/N=0.3，其中的观测矩阵 是高斯随机矩阵。采用MP算法对一维信号进行重构，重构图如1：

图1：MP算法重构一维信号

通过上面的重构可以得出，MP算法对一维信号有很好的重构效果。（2）二维lena图像的MP算法重构

我们上面的研究知道MP算法对一维信号有很好的重构作用，但是算法不只是要在一维信号中有好的重构功能，还要能很好的重构二维信号才可以，这样应用的范围才会更大。我们知道压缩感知重构的是可压缩的稀疏信号，二维信号是不稀疏的，这就要在进行算

法重构的时候进行一些处理，我们可以先采用离散余弦变换（dct）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct），这样就转化为了我们所需要的。本次在matlab中的仿真，我们采用的是256256

的Lena的二维图像，M=180，N=256，稀疏度k=40，M/N=0.7，观测矩阵是高斯随机矩阵，采用MP算法对二维图像进行重构，重构效果如图2（b）：

（a）原始图片（b）MP算法重构

（M/N=0.7）

通过上面的(a)图和（b）图可知，采样率为0.7的时候，MP算法也能对二维图像进行精确重构。

2.正交匹配追踪算法（OMP）

2.1OMP算法的原理

OMP算法是在MP算法的基础上进行改进的，沿用了MP算法

的重构的思想，但是又对MP 算法进行了改进，使得算法的效率更高，应用更加的广泛。

MP 算法的信号分解中步骤中介绍：R y y 100,+Γ>Γ=

明信号在已经选择的原子上的投影（等是右边第一项）是非正交的，还存在着残差，也就是说每次迭代的过程是次最优的，不是最优解，要想最终的迭代收敛，需要的迭代次数较多。OMP 算法就是根据MP 算法的不足之处加以改进，把所选择的原子首先通过Schimidt 正交化处理，使得在达到迭代条件的时候需要的迭代次数较MP 算法少，但是正交化的过程中会增加计算量。

在每一步中如何对选择的全部原子进行正交化处理呢？这是OMP 算法和MP 算法的不同之处。下面介绍OMP 算法正交化原理[1]： 信号y 经k 步分解：

R a k k n k n n y +Γ=∑=?1且0,>=Γ

R k ，n=1,…，k （1） （1）式和MP 算法的不同在于，MP 算法是残差和前面的一个分量正交，而OMP 算法是残差和前面的每个分量都正交。

k+1步分解为：

R a k k n k n n y 1111+++=+Γ=∑? 且 0,1>=Γ<+?n

R k n=1,…，k+1 （2） k+1阶减去k 阶：

R R a a a k

k k k k n k n k n k n -+Γ+Γ-++++=+∑1111

11)(?? （3） 要想对选择的全部原子进行正交化处理，要求（3）式等于零。测量

矩阵的原子不正交，为了说明（3）式等于零，下面引入一个辅助模型，模型表示的是?

Γ+1k 对前k 个项?Γn

（n=1，…，k ）的依赖，数学语言描述如下： r b k k n k

n n n +Γ=Γ∑=+??11且 =0,n=1,…,k (4)

?Γ+1k 在),...,(

1??k

上张成的正交投影，等式右边的第二项是残差，（4）式代入（3）式中：

0)()(11

11111=-++Γ+-++++++=∑R R r a b a a a k k k k k k n k k k n k n k n n ? (5) 如果（6）和（7）式成立，则（5）式必然成立，

0111=+-+++b a a a

k n k k k n k n （6） 0111=-++++R R r a k k k k k (7) 令a a k k k =++11，有：

b a a a

k n k k n k n -=+1

n =1,…,k (8) 01=-++R R r a k n k k n =1,…,k (9) （8）和（9）两式成立，以上就是OMP 算法进行正交化的过程。 参考文献：

[1] Y .C.PATI.Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition.IEEE.1993:40-44

2.2 OMP 算法的流程图

和上面的MP 算法一样，我们同样画出OMP 算法的流程图，可

以让我们更加清晰的理解算法。

图：OMP算法的流程图

2.3 OMP算法的算法步骤

和MP算法一样，我们也在给出OMP算法的流程图之后，再给出OMP算法的算法步骤[1][2]。

输入：感知矩阵Φ（N

M?）,测量向量y（1?

N）,稀疏度K

输出：重构信号^ x

（1）初始化余量y r =0，迭代次数n=0,重建信号00=x ，索引集

[]0=Γ； （2） 计算余量和测量矩阵每一列的内积：r g n T n 1-Φ=；

（3） 找出g n

中绝对值最大的元素；

（4） 更新原子组合}{1?k n n ?Γ=ΓΦΦ-和新索引集}{1k n n ?=ΓΓ-； （5）利用最小二乘法计算信号的近似解：

y n T n T

n n x ΦΦΦΓΓΓ=-)(1；

（6） 计算更新余量：x r n n y Φ-=；

（7） 更新迭代次数n=n+1，若满足迭代条件,则x n x

=^

；若不满足

迭代的的条件则返回（2），继续进行迭代； 参考文献[1] 文首先.压缩感知匹配追踪算法的研究. [D].2013

[2] Y .C.PATI.Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition.IEEE.1993:40-44

上面提到最小二乘法，首先我们先较少一下什么杀死最小二乘法，然后再说明一下为什么OMP 算法可以用最小二乘法就信号的解。 名词解释：最小二乘法

最小二乘法（最小平方法）是一种数学优化技术，它通过使数据误差的平方和最小来寻找数据的最佳函数匹配。

最小二乘准则：使全部样本观测值的残差平方和达到最小。即

)

(^min min 22Y Y e i i i -∑=∑来确定未知的参数,未知的参数)

,...,,(10'ααααk =，未知参数的估计为

),...,(^^1^0'

^ααααk =，下面我们来推导二阶估计量的公式：

设所有残差的平方和为：^''''''22^^1^0^^2^),...,,()

(ααααααX Y Y e i i i Q X

X Y e Y Y e k +-==∑=∑=- 其中，Y i 是第i 次的样本观测值，^Y i 为相应的第i 次的样本估计值，

^^21...αX Y Y Y e e e e n -=-=??????

????????=，对上式进行求导，以便得到最小二乘估计值：

移项可得，Y X X X '^'=α,在这里我们假定)('1X X -存在，用)

('1X X -左乘上式的；两边，得到α的最小二乘估计量，Y X X X '1^)('-=α,这个公式也就是OMP 算法步骤中的步骤（5），以上就证明了最小二乘法估计OMP 算法的方法。

2.4 OMP 算法的信号重构

本节对OMP 算法进行重构，采用一维离散信号和二维lena 信号022)^^2(^

''^'''''^^=+-=+-??=??ααααααX Y X Y Y Q

X X X X Y

对其进行信号重构，来观察OMP算法的重构功能。

（1）一维离散信号的OMP算法仿真

本次仿真使用matlab随机生成的一维离散信号，稀疏度k=15,信号长度N=512，观测向量的长度M=128，那么采样率M/N=0.25，其中的观测矩阵Φ是高斯随机矩阵。采用OMP算法对一维信号进行重构，重构图如1：

图1：OMP算法重构一维信号

通过上面的重构可以得出，OMP算法对一维信号有很好的重构作用。（2）二维lena图像的OMP算法重构

OMP算法对二维信号进行重构，在这里我们采取和MP算法二维信号重构的方法，也是先采取离散余弦变换（dct）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct），这样就转化为了我们所需要的。本次在matlab中的仿真，我们采用的是256256

?的

Lena的二维图像，M=180，N=256，稀疏度k=40，M/N=0.7，观测矩阵是高斯随机矩阵，采用OMP算法对二维图像进行重构，重构效果如图2（b）：

(a) 原始图像（b）OMP算法重构图片

（M/N=0.7）

通过上面（a）图和（b）图的重构可知，采样率为0.7的时候，OMP算法也能对二维信号很好的重构。

3 基追踪算法（BP）

压缩感知中很重要的一步就是重构算法，重构算法关系着重建信号的质量。基追踪算法是凸松弛法是很有代表性的一种算法。

3.1 凸松弛法介绍

凸松弛法是信号在重构的过程中把重构问题由l0范数问题转化为了l1范数的凸优化问题。下面首先介绍几个涉及到的概念。

凸优化：定义域是闭合的凸集；函数是定义域上的凸函数的最优化问题，只有两个条件同时满足才是凸优化。

凸集：数学定义，D 为集合

R N D ∈,D x x ∈?2

1,,]1,0[∈α,D x x ∈-+?21)1(αα 凸集的几何意义：集合中的任意两点连线段都在集。

凸函数：凸集上的g （x ）函数和任意的实数]1,0[∈α，

D x x ∈21,,使)()1()())1((2121x x x x g g g αααα-+≤-+成立，g （x ）就是凸函数。 下面介绍一下0范数为什么可以用l 1范数进行求解，可以用l 2范数进行求解吗？首先给出这三个范数的统一的数学表达式：

||||min X T p Φ s.t. X Y T ψΦ= P=0，1，2

将三种范数投影到二维空间中，直线X Y T ψΦ=在二维空间中是一

条直线，图1是三种范数在二维空间构成的图形和直线之间的直观图。

（a ） （b ） （c ）

图1：三种范数与直线的关系图

其中（a ）是l 0范数与X Y T

ψΦ=直线关系图，（b ）是l 1范数与

X Y T ψΦ=直线关系图，（c ）是l 2范数与X Y T

ψΦ=直线关系图。

由（a ）图可知，l 0范数在二维空间中是沿着坐标轴的两条垂直的线，

直线向坐标原点逼近的时候首先是和坐标轴相交，这也就是我们所要求的稀疏的解；由（b ）图可知，l 1范数在二维空间中的图形是一个

如（b ）图的菱形，排除直线和菱形的一条边平行的情况，直线向菱形逼近的过程中，首先相交于菱形的四个点，也就是坐标轴上的点，这也就是我们所要求的稀疏的解；由（c ）图可知，l 2范数在二维空

间中的图形是圆形，直线向圆形逼近的时候，直线和圆相交的点几乎都不在坐标轴上，只有直线和坐标轴平行的小概率的时候。通过上面的介绍可以知道，可以用l 1范数来代替l 0范数进行求解。 3.2 BP 算法的原理

上节提到的l 0范数，由于我们所要求解的问题是方程的个数远远

大于未知数的个数，用l 0范数求解是很难求解出来的，这样就找到一

种用l 1范数来代替l 0范数求解的方法，BP （Basis Pursuit ）算法就是

利用l 1范数求解的一种很好的方法。BP 算法不是直接寻求信号的稀

疏表示，只是表示的用于最小化的l 1的系数[1]，通过等价信号的最小

化的l 1范数表示[2]。下面介绍BP 算法的原理。

BP 算法中l 0范数的模型为:

||||0^min x x = s.t. x y Φ= (1)

l 0范数是稀疏变换中不为零的个数，（1）式的求解比较困难，通过上

面的说明，l 0范数可以用l 1范数进行代替，则（1）式可以表示为：

||||1^min x x = s.t. x y Φ= (2)

(2)式表示的是理想的一种情况，在实际的应用中，会混入噪声，也就是：

noise x y +Φ= （3） 那么（2）式可表示为：

||||1^

min x x = s.t. ε≤Φ-||||2

x y （4） （4）式中ε为噪声的能量。由于实际模型中会混入噪声，这就需要一种抑制噪声的模型，也就是改进后的BP 算法，改进后的BP 算法对噪声有一定的抑制作用，那么改进后的模型为[3]：

||||||||12)2/1(min x x y x κ+Φ- (5) 其中，（5）式的第一项是信号经观测矩阵之后的观测值，式子的第二项是噪声产生的观测值，κ表示观测值中中非零元素的位置。BP 算法中就把凸松弛算法转化为了线性规划问题求解，则（5）式可以转化为[1][3]：

||||min 2,21p C X T p x + s.t. b p Ax =+δ 0≥x , 1=δ (6)

(6)式中，],...,,,,...,[2121??????n n A ---← y b ←

]1,...,1,1[←c ],...,,[21αααn x ← X c T min 等价于最小化的l 1范数的系数，p 表示噪声产生的观测值。

参考文献：

[1] Patrick S.Huggins , Steven W. Zucker . Greedy Basis Pursuit.IEEE.2007,55(7):3760-3772

[2] S.S.Chen,”Basis Pursuit”Ph.D.dissertation , Dept.Statistics，Stanford University,Stanford,CA,1995.

[3] 文首先.压缩感知匹配追踪算法的研究.D.2013

3.3 BP算法的信号重构

本节对BP算法进行重构，采用一维离散信号和二维lena信号对其进行信号重构，来观察BP算法的重构功能。

（1）一维离散信号的BP算法仿真

本次仿真使用matlab随机生成的一维离散信号，稀疏度k=30,信号长度N=1000，观测向量的长度M=200，那么采样率M/N=0.2，其中的观测矩阵 是高斯随机矩阵。采用BP算法对一维信号进行重构，重构图如图1：

图1：BP算法一维信号重构图

压缩感知简介

2011.No31 0 3.2 熟悉结构施工图 结构施工图是关于承重构件的布置,使用的材料、形状、大小及内部构造的工程图样,是承重构件以及其他受力构件施工的依据。 看结构施工图最难的就是钢筋，要把结施图看懂就要知道钢筋的分布情况，现在都是在使用平法来标示钢筋，所以也要把平法弄懂才行。在识读与熟悉结施图的过程中应该充分结合钢筋平法表示的系列图集，搞清楚： a 各结构构件的钢筋的品种，规格，以及受力钢筋在各构件的布置情况。 b 箍筋与纵向受力钢筋的位置关系。 c 各个构件纵向钢筋以及箍筋弯钩的角度及其长度。 d 熟悉各构件节点的钢筋的锚固长度。 e 熟悉各个构件钢筋的连接方式。 f 熟悉在钢筋的搭接区域内，钢筋的搭接长度。 g 核算钢筋的间距是否满足施工要求，尤其是各个构件节点处的钢筋间距。 h 弯起钢筋的弯折角度以及离连接点的距离。 除此以外，对于钢筋混凝土构件，还应该熟悉各个构件的砼保护层厚度，各个构件的尺寸大小、布置位置等。特别注意的是对于结施图的阅读应充分结合建施图进行。 4 结束语 在熟悉施工图纸的过程中，施工技术人员对于施工图纸中的疑问，和比较好的建议应该做好记录，为后续工作（图纸自审和会审）做好准备。 参考文献 [1]《建筑识图》周坚主编 中国电力出版社 2007年；[2]《建筑工程项目管理》银花主编 机械工业出版社 2010年； 摘 要 压缩感知（Compressive Sensing, CS）理论是一个充分利用信号稀疏性或可压缩性的全新信号采集、编解码理论。本文系一文献综述，主要介绍了压缩感知的三部分即信号的稀疏表示、测量矩阵的设计、信号恢复算法的设计。 关键词 压缩感知 稀疏表示 测量矩阵 信号恢复算法 1 引言 1928年由美国电信工程师H.奈奎斯特（Nyquist）首先提出，1948年信息论的创始人C.E.香农（Shannon）又对其加以明确说明并正式作为定理引用的奈奎斯特采样定理，是采样带限信号过程所遵循的规律。它指出：在进行模拟/数字信号的转换过程中，当采样频率fs.max大于信号中最高频率fmax的2倍时(fs.max>=2fmax)，采样之后的数字信号完整地保留了原始信号中的信息。一般实际应用中保证采样频率为信号最高频率的5～10倍。该理论支配着几乎所有的信号/图像等的获取、处理、存储、传输等。随着科技的发展，成为目前信息领域进一步发展的主要瓶颈之一，主要表现在两个方面： (1)数据获取和处理方面。在许多实际应用中(例如超宽带信号处理、核磁共振、空间探测等），Nyquist采样硬件成本昂贵、获取效率低下，信息冗余及有效信息提取的效率低下，在某些情况甚至无法实现。 (2)数据存储和传输方面。通常的做法是先按照Nyquist方式获取数据，然后将获得的数据进行压缩，最后将压缩后的数据进行存储或传输，这样会造成很大程度的资源浪费。另外，为保证信息的安全传输，通常以某种方式对信号进行编码，这给信息的安全传输和接收带来一定程度的麻烦。 近年来，由D .D o n o h o (美国科学院院士)、E . Candes(Ridgelet， Curvelet创始人)及华裔科学家T. Tao(2006年菲尔兹奖获得者，2008年被评为世界上最聪明的科学家)等人提出了一种新的信息获取指导理论，即压缩感知（Compressive Sensing(CS)，或称Compressed Sensing、Compressed Sampling）。该理论指出：对可压缩的信号通过远低于Nyquist标准的方式进行数据采样，仍能够精确地恢复出原压缩感知简介 刘太明1 黄 虎2 （1、成都理工大学,四川成都,610059;2、成都理工大学,四川成都,610059） 始信号。该理论一提出，就在信息论、信号/图像处理、医疗成像、模式识别、地质勘探、光学/雷达成像、无线通信等领域受到高度关注，并被美国科技评论评为2007年度十大科技进展。 2 CS基本原理 信号x∈R n×1压缩传感的测量过程可以表示为y=Ax∈R M×1,M<

压缩感知的重构算法

压缩感知的重构算法 算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。 压缩感知的重构算法主要分为三大类： 1.组合算法 2.贪婪算法 3.凸松弛算法 每种算法之中又包含几种算法，下面就把三类重构算法列举出来。 组合算法：先是对信号进行结构采样，然后再通过对采样的数据进行分组测试，最后完成信号的重构。 (1) 傅里叶采样（Fourier Representaion） (2) 链式追踪算法（Chaining Pursuit） (3) HHS追踪算法（Heavy Hitters On Steroids） 贪婪算法：通过贪婪迭代的方式逐步逼近信号。 (1) 匹配追踪算法（Matching Pursuit MP） (2) 正交匹配追踪算法（Orthogonal Matching Pursuit OMP） (3) 分段正交匹配追踪算法（Stagewise Orthogonal Matching Pursuit StOMP）

(4) 正则化正交匹配追踪算法（Regularized Orthogonal Matching Pursuit ROMP） (5) 稀疏自适应匹配追踪算法（Sparisty Adaptive Matching Pursuit SAMP） 凸松弛算法： (1) 基追踪算法（Basis Pursuit BP） (2) 最小全变差算法（Total Variation TV） (3) 内点法（Interior-point Method） (4) 梯度投影算法（Gradient Projection） (5) 凸集交替投影算法（Projections Onto Convex Sets POCS）算法较多，但是并不是每一种算法都能够得到很好的应用，三类算法各有优缺点，组合算法需要观测的样本数目比较多但运算的效率最高，凸松弛算法计算量大但是需要观测的数量少重构的时候精度高，贪婪迭代算法对计算量和精度的要求居中，也是三种重构算法中应用最大的一种。下面分别就贪婪算法中的MP，OMP算法以及凸松弛算法中的BP算法进行详细的介绍。 三种重建算法 本节主要是介绍一些基本的重建算法，比如贪婪迭代算法中的匹配追踪算法，正交匹配追踪算法，以及凸松弛算法中的基追踪算法，对其原理进行了介绍，并用matlab代码重构出来一维和二维的图形，进而比较这几种算法的性能。

OMP压缩感知重构仿真

clc;clear %% 1. 时域测试信号生成 %产生长度为N=256的稀疏信号，其稀疏度K=23且这23个非零值随机分布于信号256个位置 %观测向量y的长度M=80，即采样率M/N=0.3 N=256; K=23; M=80; x = zeros(N,1); q = randperm(N); x(q(1:K)) =randn(K,1); %原始信号 %% 2. 测量矩阵及观测值获得 Phi=randn(M,N); %测量矩阵% 感知矩阵（高斯分布白噪声）M*N matrixNorm = Phi.'*Phi; matrixNorm = sqrt(diag(matrixNorm)).'; Phi = Phi./repmat(matrixNorm, [M,1]); %注意，观测矩阵是要归一化的，因为原子范数要是1！ y=Phi*x ; %获得线性测量 %% 3.用MP算法重构信号 iterations=K; % 算法迭代次数(m>=K) %signal_reconstruct=zeros(1,1); % 近似解矩阵(初始值为空矩阵) r_n=y; % 残差值M*1 x_rec=zeros(N,1); for times=1:iterations for col=1:N %感知矩阵的所有列向量 innerpro(col)=Phi(:,col)'*r_n; %计算余量和感知矩阵每一列的内积end [val,pos]=max(abs(innerpro) ); %找出内积中绝对值最大的元素和它的对应的感知矩阵的列pos x_rec(pos)=x_rec(pos)+innerpro(pos); %计算新的近似x_rec r_n=r_n-innerpro(pos)*Phi(:,pos); %更新残差 end norm(x_rec-x)/norm(x) % 重构误差 subplot(3,1,1);plot(x);title('origin'); subplot(3,1,2);plot(x_rec);title('reconstruct'); subplot(3,1,3);plot(r_n);title('残差');

压缩感知理论综述(原创)

压缩感知理论综述 摘要：信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，但其产生的大量数据造成了存储空间的浪费。压缩感知（Compressed Sensing）提出一种新的采样理论，它能够以远低于Nyquist采样速率采样信号。本文详述了压缩感知的基本理论，着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展，并介绍了压缩感知的应用及仿真，举例说明基于压缩感知理论的编解码理论在一维信号、二维图像处理上的应用。 一、引言 Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。可见，带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩实际上是一种资源浪费，因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言，我们得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist 采样机制是冗余的或者说是非信息的。 于是很自然地引出一个问题：能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于Nyquist采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论，成功实现了信号的同时采样与压缩。 简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和非相干性，或者稀疏性和等距约束性。事实上，压缩感知理论的某些抽象结论源于Kashin创立的范函分析和逼近论，最近由Candes，Romberg,Tao和Donoho等人构造了具体的算法并且通过研究表明了这一理论的巨大应用前景。目前国内已经有科研单位的学者对其展开研究。如西安电子科技大学课题组基于该理论提出采用超低速率采样检测超宽带回波信号。 显然，在压缩感知理论中，图像/信号的采样和压缩同时以低速率进行，使传感器的采样和计算成本大大降低，而信号的恢复过程是一个优化计算的过程．因此，该理论指出了将模拟信号直接采样压缩为数字形式的有效途径。从理论上讲任何信号都具有可压缩性，只要能找到其相应的稀疏表示空间，就可以有效地进行压缩采样。 当前，压缩感知理论主要涉及三个核心问题： (1) 具有稀疏表示能力的过完备字典设计； (2) 满足非相干性或等距约束性准则的测量矩阵设计； (3) 快速鲁棒的信号重建算法设计。 压缩感知理论必将给信号采样方法带来一次新的革命。这一理论的引人之处还在于它对应用科学的许多领域具有重要的影响，如统计学、信息论、编码等。目前，学者们已经在模拟-信息采样、合成孔径雷达成像、遥感成像、核磁共振成像、深空探测成像、无线传感器网络、信源编码、人脸识别、语音识别、探地雷达成像等诸多领域对压缩感知展开了广泛的应用研究。Rice大学已经成功设计出了一种基于压缩感知的新型单像素相机，在实践中为取代传统相机迈出了实质性的一步。 本文围绕稀疏字典设计、测量矩阵设计、重建算法设计三个核心问题，综述了压缩感知理论以及与之相关的信号稀疏变换、观测矩阵设计、重构算法等一系列最新理论成果和应用研究，描述了国内外的研究进展。本文结构安排如下：第2 部分阐述了压缩感知的理论框架；第3 部分系统介绍了压缩感知的三个核心问题，即信号的稀疏表示、信号的观测矩阵、信号重构算法；第4 部分指出压缩感知有待解决的若干关键问题；第5 部分介绍了压缩感知的应用及仿真；第6部分对全文作了总结。

基于压缩感知的图像重构模型的设计

基于压缩感知的图像重构模型的设计 压缩感知打破了传统的奈奎斯特采样定律，可以用远小于奈奎斯特采样定律所要求的采样率从较少的测量值中高精度的重构出原始信号。文章利用MATLAB GUI对基于压缩感知理论的图像压缩重构模型进行设计，该模型界面友好，操作简单方便。 标签：压缩感知；小波变换；图像重构；模型设计 引言 压缩感知理论为信号采集带来了革命性的突破，在信号具有可压缩性或稀疏性的前提下，压缩感知理论能以远低于奈奎斯特频率的采样率对信号进行采样，通过数值最优化准确重构原始信号[1-4]。压缩感知理论是编解码思想的一个突破，减轻了信号采样、传输和存储遇到的巨大压力，是一种信息获取及处理的全新的理论框架。 本文将利用MATLAB GUI进行基于压缩感知理论的图像重构模型的设计，使模型使用者方便操作界面。MATLAB是Math Works公司用C语言开发的集编程、数据结构和图形用户界面于一身的广泛被大家使用并具备矩阵及科学计算功能的一款较完备的软件，在该软件平台下进行的仿真以及系统模型的设计，在界面和性能上面远远超过很多软件，其专业性更是使其在很多领域有广泛的应用，其中能快速的利用图形用户界面（GUI）方式进行程序设计，这给设计者带来了极大的便利[5]。 1 基于小波变换的压缩感知 本节通过对原始图像采用小波变换，从而获得稀疏的小波系数矩阵，并利用高斯随机测量矩阵对稀疏变换后的小波系数进行测量，得到M个测量值，再通过OMP算法重构小波变换域下的稀疏矩阵，最后通过稀疏逆变换就可以得到重构后的图像。 本节选取大小为256×256的图像X，采样率为0.5对图像进行变化重构。本文实验仿真所得的PSNR值均经过10次仿真测量求平均值所得。 2 模型设计的主要步骤 根据上述基于小波变换的压缩感知进行模型设计[6]，主要步骤包括： （1）根据需求制定模型的重点功能，继而根据功能设计各个功能子模块。 （2）根据初始需求以及大致目标设计出最原始的软件界

几种压缩感知算法

.1压缩感知部分 压缩感知算法主要可分为三类：贪婪迭代算法、凸凸优化（或最优化逼近方法）和基于贝叶斯框架提出的重构算法。由于第三类方法注重信号的时间相关性，不适合图像处理问题，故目前的研究成果主要集中在前两类中。目前已实现6中算法，分别为正交匹配追踪法（）、迭代硬阈值法（）、分段正交匹配追踪法（）、分段弱正交匹配追踪法（）、广义正交匹配追踪（）、基追踪法（）。 1.1 正交匹配追踪法（） 在正交匹配追踪中，残差是总与已经选择过的原子正交的。这意味着一个原子不会被选择两次，结果会在有限的几步收敛。的算法如下 (1)用x表示你的信号，初始化残差e0； (2)选择与e0内积绝对值最大的原子，表示为φ1； (3)将选择的原子作为列组成矩阵Φt，定义Φt列空间的正交投影算子为 通过从e0减去其在Φt所张成空间上的正交投影得到残差e1； (4)对残差迭代执行(2)、(3)步； 其中I为单位阵。需要注意的是在迭代过程中Φt为所有被选择过的原子组成的矩阵，因此每次都是不同的，所以由它生成的正交投影算子矩阵P每次都是不同的。 (5)直到达到某个指定的停止准则后停止算法。 减去的是在所有被选择过的原子组成的矩阵Φt所张成空间上的正交投影，而减去的是在本次被选择的原子φm所张成空间上的正交投影。 经算法重构后的结果如下所示： 算法的使用时间如下：

1.2 迭代硬阈值法（） 目标函数为 这里中的M应该指的是，S应该指的是。这里要求： 之后我们利用式 对目标函数进行变形。接着便是获得极值点： 利用该式进行迭代可以得到极值点，我们需要的是最小值。此时目标函数的最小值就得到了。此时便得到我们需要的公式： 我们要保证向量y的稀疏度不大于M，即，为了达到这一目标，要保留最大的M项（因为是平方，所以要取绝对值），剩余的置零（注意这里有个负号，所以要保留最大的M项）。 算法结果：

压缩感知原理

压缩感知原理(附程序) 1压缩感知引论 传统方式下的信号处理，是按照奈奎斯特采样定理对信号进行采样，得到大量的采样数据，需要先获取整个信号再进行压缩，其压缩过程如图2.1。 图2.1 传统的信号压缩过程 在此过程中，大部分采样数据将会被抛弃，即高速采样后再压缩的过程浪费了大量的采样资源，这就极大地增加了存储和传输的代价。 由于带宽的限制，许多信号只包含少量的重要频率的信息。所以大部分信号是稀疏的或是可压缩的，对于这种类型的信号，既然传统方法采样的多数数据会被抛弃，那么，为什么还要获取全部数据而不直接获取需要保留的数据呢？Candes和Donoho等人于2004年提出了压缩感知理论。该理论可以理解为将模拟数据节约地转换成压缩数字形式，避免了资源的浪费。即，在采样信号的同时就对数据进行适当的压缩，相当于在采样过程中寻找最少的系数来表示信号，并能用适当的重构算法从压缩数据中恢复出原始信号。压缩感知的主要目标是从少量的非适应线性测量中精确有效地重构信号。核心概念在于试图从原理上降低对一个信号进行测量的成本。压缩感知包含了许多重要的数学理论，具有广泛的应用前景，最近几年引起广泛的关注，得到了蓬勃的发展。 2压缩感知原理 压缩感知，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号进行信号重构的技术。或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。压缩感知跳过了采集N个样本这一步骤，直接获得压缩的信号的表示。CS理论利用到了许多自然信号在特定的基 上具有紧凑的表示。即这些信号是“稀疏”的或“可压缩”的。由于这一特性，压缩感知理论的信号编解码框架和传统的压缩过程大不一样，主要包括信号的稀疏表示、编码测量和重构算法等三个方面。

压缩感知磁共振成像技术综述

https://www.wendangku.net/doc/0d12825222.html, 压缩感知磁共振成像技术综述 王水花，张煜东 南京师范大学计算机科学与技术学院，江苏南京210023 【摘 要】目的:综述近年来压缩感知磁共振成像技术的研究进展。方法:磁共振成像是目前临床医学影像中最重 要的非侵入式检查方法之一，然而其成像速度较低，限制其发展。压缩感知是一种新的信号采集与获取理论，它利用信号在特定域上的稀疏性或可压缩性，可通过少量测量重建整个原始信号。压缩感知磁共振成像技术将压缩感知应用到磁共振成像中，可在相同的扫描时间内获得更精细的空间组织结构，也可在相同的空间分辨率下加速成像。结果:本文概述了压缩感知磁共振成像的理论基础，分别从稀疏变换、不相干欠采样、非线性重建三个方面具体阐述，最后讨论了其研究展望与应用现状。结论:压缩感知磁共振成像具有较好的发展潜力，有逐渐增长的医用与商用价值。 【关键词】磁共振成像；压缩感知；稀疏变换；不相干欠采样；非线性重建【DOI 编码】doi:10.3969/j.issn.1005-202X.2015.02.002【中图分类号】R312；R445.2 【文献标识码】A 【文章编号】1005-202X （2015）02-0158-05 Survey on Compressed Sensing Magnetic Resonance Imaging Technique WANG Shui-hua,ZHANG Yu-dong School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China Abstract:Objective This paper focuses on the survey of compressed sensing in magnetic resonance imaging （CSMRI ）.Meth -ods Magnetic resonance imaging is one of the most crucial non-invasive diagnostic implements in routine clinical examination.However,it is often limited by long scan https://www.wendangku.net/doc/0d12825222.html,pressed sensing is a novel theory of signal acquisition and processing.It capitalizes on the signal's sparseness or compressibility in specific domain,allowing the entire original signal to be reconstruct-ed from relatively few measurements.CSMRI is proposed by integrating compressed sensing into MRI,providing more precise spatial tissue structure than normal technique in the same scan time,and accelerating imaging in the same spatial resolution.Results In this study we discussed in depth three components as sparse transform,incoherent subsampling,and nonlinear re-construction.We conclude the paper by discussing the research prospects and applications of CSMRI.Conclusion CSMRI has good development potential,and has increasing values for medical and commercial applications. Key words:magnetic resonance imaging;compressed sensing;sparse transform;incoherent subsampling;nonlinear recon-struction 前言 1971年，纽约州立大学的Paul https://www.wendangku.net/doc/0d12825222.html,uterbur 教授提出磁共振成像(MRI)，并于2003年获得诺贝尔生理医学奖。MRI 利用核磁共振原理，由于能量在不同物 质结构中有不同的衰减[1]，通过外加梯度磁场检测电 磁波，可知构成物体原子核的位置和种类，从而绘制物体内部影像[2-3]。 MRI 是目前少有的对人体无伤害的安全、快速、准确的临床诊断方法，具有多方位、多参数、多模态等优点，不仅可显示人体组织的解剖信息，而且可显示功能信息。MRI 在临床上有广泛的应用，如今每年至少有6000万病例利用MRI 技术进行检查。但MRI 扫描时间过长、成像较慢[4]，造成以下几个问题[5]：（1）给病人造成额外的痛苦；（2）由于器官运动（例如呼吸、眨眼、吞咽等非自主运动）造成图像模糊，增加伪影；（3）无法满足动态实时成像与导航的需要；（4）限制功能成像的推广，如波谱成像、磁敏感加权成像等。 2006年Candes 等[6]在前人的基础上，系统性地 【收稿日期】2014-12-21 【基金项目】国家自然科学基金(610011024)；南京师范大学高层次人才 科研启动基金(2013119XGQ0061,2014119XGQ0080) 【作者简介】王水花，女，助教，研究方向：生物图像处理。【通信作者】张煜东，男，博士，教授，研究方向：医学图像处理。 158--

压缩感知 很好的综述 2012

压缩感知? 许志强? 中国科学院数学与系统科学研究院, 计算数学与科学工程计算研究所, 科学与工程计算国家重点实验室,100190,北京 2012年1月12日 摘要 压缩感知是近来国际上热门的研究方向.其在信号处理中具有很好的应用前景. 此外,它与逼近论、最优化、随机矩阵及离散几何等领域密切相关,由此产生了一些漂 亮的数学结果.本文综述压缩感知一些基本结果并介绍最新进展.主要包括RIP矩阵 编码与?1解码的性能,RIP矩阵的构造,Gelfand宽度,个例最优性及OMP解码等. 1引言 现实世界中,人们经常需要对信号进行观测,例如医学图像成像、CT断层扫描等,以期通过观测信息对原始的信号进行重建.由于计算机的离散化存储,我们可将需重建的信号x抽象为一N维向量,可将对信号x的观测抽象为用一n×N的矩阵Φ与信号x进行乘积.例如在CT扫描中,矩阵Φ通常选择为离散Fourier矩阵.那么,我们所观测的信息为 y=Φx.(1)人们自然而问:为重建信号x,至少需要多少次观测?由线性代数知识可知,为使方程组(1)的解存在且唯一,我们须选择n≥N.也就是说,我们需要至少进行n=N次观测.然而,现实世界中的自然信号通常具有一定规律性.对这种规律性,一种常用的刻画方式是自然信号在一组基底表示下是稀疏的.这里的“稀疏”是指它们用一组基底展开后,大多数系数为0,或者绝对值较小.例如,自然图像用小波基底展开后,一般而言,其展开系数大多 ?国家自然科学基金(11171336)及创新群体(11021101)资助. ?Email:xuzq@https://www.wendangku.net/doc/0d12825222.html, 1

数绝对值较小.这也就是图像能够进行压缩的原理.然而,这同时为人们减少观测次数n 从理论上提供了可能性.因而,压缩感知的主要任务为:对尽量小的n,设计n×N观测矩阵Φ,以及通过Φx快速恢复x的算法.所以,压缩感知的研究主要分为两方面：矩阵Φ的设计;与反求信号x的算法. 本文主要介绍压缩感知的一些基本结果.在每节里,我们采用注记的方式介绍当前的一些研究进展及研究问题,同时提供与之相关的参考文献,以使感兴趣的读者可进一步探索.本文组织结构如下:第2节中我们介绍了稀疏信号精确恢复的编码、解码方法.特别是,我们将介绍矩阵的零空间性质,及RIP矩阵编码与?1解码的性能.我们在第3节中介绍RIP矩阵的构造方法,包括随机矩阵、结构随机矩阵及确定性矩阵.在第4节中,为理解最优编码、解码对的性能,我们介绍了Gelfand宽度与编码、解码对性能的关联.我们在第5节中介绍了编码、解码对在不同范数意义下的个例最优性.最后一节简要介绍实现解码的算法. 2稀疏信号的恢复 为方便介绍压缩感知理论,我们将信号的稀疏性简单理解为信号中非0元素数目较少.我们所指的信号即为一向量x∈R N.我们用Σs表示s-稀疏向量集合,即 Σs:={x∈R N:∥x∥0≤s}, 这里∥x∥0表示x中的非0元素数目.所谓对信号x0∈R N编码,即指用一n×N的矩阵Φ与x0∈R N进行乘积,那么我们得到 y=Φx0. 此处,y∈R n即为我们所观测到的关于x0的信息.所谓解码,就是试图通过y反求x0,也就是寻找一从R n到R N的映射,我们将该映射记为?.我们用?(y)表示反求结果.一般而言,若n

压缩感知重构算法之基追踪

压缩感知重构算法之基追踪（Basis Pursuit ，BP ） 除匹配追踪类贪婪迭代算法之外，压缩感知重构算法另一大类就是凸优化算法或最优化逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法就是基追踪(Basis Pursuit, BP)，该方法提出使用1l 范数替代0l 范数来解决最优化问题，以便使用线性规划方法来求解[1]。本篇我们就来讲解基追踪方法。理解基追踪方法需要一定的最优化知识基础，可参见最优化方法分类中的内容。 1、l1范数和l0范数最小化的等价问题 在文献【2】的第4部分，较为详细的证明了1l 范数与0l 范数最小化在某条件下等价。证明过程是一个比较复杂的数学推导，这里尽量引用文献中的原文来说明。 首先，在文献【2】的4.1节，给出了(P1)问题，并给出了(P1)的线性规划等价形式(LP)，这个等价关系后面再详叙。 4.1 The Case 1p = In the case 1p =, (1P ) is a convex optimization problem. Write it out in an equivalent form, with θ being the optimization variable: 11() min ||||.n P subject to y θ θθΦ= This can be formulated as a linear programming problem: let A be the n by 2m matrix []Φ-Φ. The linear program ()min1,0T n z LP z subject to Az y x =≥. has a solution *z , say, a vector in 2m which can be partitioned as ***[]z u v =; then ***u v θ=- solves 1()P . The reconstruction *1,?n x θ=ψ. This linear program is typically considered computationally tractable. In fact, this problem has been studied in the signal analysis literature under the name Basis Pursuit [7]; in that work, very large-scale underdetermined problems. 2、基追踪实现工具箱l1-MAGIC 若要谈基追踪方法的实现，就必须提到l1-MAGIC 工具箱（工具箱主页：https://www.wendangku.net/doc/0d12825222.html,/~justin/l1magic/），在工具箱主页有介绍：L1-MAGIC is a collection of MA TLAB routines for solving the convex optimization programs central to compressive sampling. The algorithms are based on standard interior-point methods, and are suitable for large-scale problems. 另外，该工具箱专门有一个说明文档《l1-magic: Recovery of Sparse Signals via Convex Programming 》，可以在工具箱主页下载。 该工具箱一共解决了七个问题，其中第一个问题即是Basis Pursuit ： Min-1l with equality constraints. The problem 11()min ||||,P x subject to Ax b = also known as basis pursuit, finds the vector with smallest 1l norm 1||||:||i i x x = ∑ that explains the observations b . As the results in [4, 6] show, if a sufficiently sparse 0x exists such that 0Ax b = then 1()P will find it. When ,,x A b have real-valued entries, 1()P can be recast as an LP (this is discussed in detail in [10]).

基于MATLAB的图像压缩感知算法的实现毕业设计说明书

毕业设计（论文） 课题名称基于MATLAB的图像压缩感知 算法的实现

目录 目录......................................................... I 第1章绪论.. (1) 1.1 研究背景和意义 (1) 1.2 数据压缩技术 (2) 1.2.1 传统数据压缩技术 (2) 1.2.2 压缩感知理论（Compressed/Compressive Sensing/Sampling, CS） (3) 1.3 无线传感器网络 (6) 1.3.1 无线传感器网络概述 (6) 1.3.2 无线传感器网络数据压缩的必要性 (7) 1.4 本文主要工作和内容安排 (8) 第2章压缩感知理论 (9) 2.1压缩感知的前提条件—稀疏性和不相干性 (10) 2.2 三个关键技术 (13) 2.3信号的稀疏表示 (13) 2.4 观测矩阵设计 (15) 2.5 稀疏信号的重构 (17) 2.6 重构算法 (18) 2.7 压缩感知优势及不足 (20) 2.8 压缩感知在传感网中的观测方式 (21) 第3章压缩感知理论应用概述 (22) 3.1 压缩成像 (22) 3.2 模拟信息转换 (23) 3.3 生物传感 (23) 3.4 本章小结 (24)

第4章 CS在无线传感网中的应用 (24) 4.1 研究背景 (25) 4.1.1 基于感知数据相关性的压缩 (25) 4.1.2传统压缩重构方法 (25) 4.1.3 图像压缩重构质量的评价 (26) 4.2 压缩感知理论算法对一维信号的实现 (28) 4.2.1 CS用于WSN的优势 (28) 4.2.2 观测重构模型 (28) 4.2.2 正交匹配追踪算法（OMP） (29) 4.2.3 算法的实现及结果分析 (30) 4.3 压缩感知理论算法对二维图像重构的实现 (34) 4.3.1 基于小波变换的分块压缩感知理论 (34) 4.3.2 实现步骤 (35) 4.3.3 重构结果及分析 (38) 4.4 本章小结 (42) 第5章总结与展望 (42) 5.1 工作总结 (42) 5.2 后续展望 (43) 参考文献 (43) 致谢 (45) 附录 (46)

基于压缩感知的图像重构技术研究

基于压缩感知的图像重构技术研究 压缩感知理论表明，若信号在某变换域具有稀疏表示，且采样矩阵与稀疏矩阵不相关，则可从远低于信号维度的少量非自适应测量值中精确恢复原信号。目前，压缩感知理论已被广泛用于各类磁共振成像中，以便在不降低成像质量的情况下减少采样点数，提高系统扫描速度。 本文即研究从亚采样的磁共振数据中，怎样快速而有效地恢复目标图像。主要研究内容包括：（1）为消除亚采样的磁共振成像重构时可能出现的过光滑（over-smoothed）和混叠伪影现象，将重构问题转化成含复合正则项的约束最小化问题，并提出一种高效的算法来求解。 该算法首先利用Bregman迭代技术，将约束问题转化成一系列无约束问题。然后利用算子分裂技术，将各无约束问题分解成一个梯度问题和一个能使用修改的SBD（Splitting Bregman Denoising）算法来求解的复合正则项的去噪问题。 最后再用加速方案对无约束问题的求解予以加速。本文将该算法称作BFSA （Bregman based Fast SBD Algorithm）。 对非笛卡尔轨迹采样的重构，本文还提出了一种动态更新L的方法。实验结果表明，新算法能够获得比其他算法更好的重构质量。 （2）为了克服现有动态磁共振成像重构速度较慢的问题，本文基于BFSA 算法框架，提出一种高效的动态磁共振成像重构算法ktBFSA。该算法利用SBD3D （Splitting Bregman Denoising for3D images）来求解含复合正则项的3D去噪问题。 实验结果表明，ktBFSA在重构速度和重构质量上都有优势。（3）SENSE （Sensitivity encoding）是常用的并行磁共振成像技术，引入压缩感知后重构

基于先验信息的压缩感知重建算法研究

基于先验信息的压缩感知重建算法研究 随着移动通信、移动互联网、物联网等新兴技术的快速发展,“万物互联”的时代即将到来。由此而产生的的数以万亿数据处理压力,是一个不容小觑的问题。尤其是面对未来的5G通信,传统的奈奎斯特采样定理不仅会大幅增加设备的硬件成本,而且会产生大量的数据冗余。由此可以看出,如何从信号中安全、高效地获取和处理尽可能多的有用信息是促进技术演进的一个重要课题。 Donoho、Candes和Tao等人提出的压缩感知理论可以将压缩与采样两个过程合二为一,将高维度稀疏信号通过压缩采样投影到低维度空间,降低通信设备的采样速率,达到降低硬件成本、减轻采样压力的目的。压缩感知为我们提供了一个全新的采样思路,打破传统采样定理的禁锢,逐渐成为一个全新的信号处理技术。尽管压缩感知在采样率、数据降维等方面拥有极大的优势,但仍有许多问题亟待解决。经过十余年的研究,压缩感知理论体系逐渐完善,主要分为信号的稀疏表示、压缩采样和信号重建三个方向。 信号的稀疏表示是应用压缩感知的前提条件,压缩采样是信号降维的关键技术,信号重建是从压缩信号恢复原信号的必要手段。这三个关键技术相辅相成,共同组成了压缩感知理论的主体框架。在压缩感知的发展过程中,如何有效地利用信号本身的稀疏结构(如块稀疏、稀疏树结构等)或者其他先验信息(支撑集非零概率、测量矩阵的扰动和支撑集部分信息已知等)提升重建性能也是压缩感知的一个重要课题。此外,对压缩感知相关重建算法理论性能(如重建误差、测量矩阵的数学要求、测量值个数等)的研究也是一个十分重要的研究方向。 因此,本文主要聚焦于两个方面:一个是研究可量化的先验信息对压缩感知重建算法的性能影响,为后续的算法研究提供理论支撑;另一个是研究稀疏信号的先验信息和压缩感知重建算法的结合,通过合理建立优化模型,最大化利用信号的先验信息为手段,设计高效、鲁棒的压缩感知重建算法,实现提升重建算法的性能和重建速度的目标。本文利用信号自身的特殊稀疏结构或者先验信息,并纳入到算法的重建过程,建立新的优化模型,提出高效、鲁棒的压缩感知重建算法,并对相关算法的重建性能进行理论分析。本文的研究创新之处主要有以下几点:1.对点对点链路和多点链路压缩感知重建算法的重建性能进行了推导,获得了点对点链路基于支撑集非零概率向量为先验信息场景中的RIP常数性能界以及多点

压缩感知技术综述

压缩感知技术综述 摘要：信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，但其产生的大量数据造成了存储空间的浪费。压缩感知（Compressed Sensing）提出一种新的采样理论，它能够以远低于Nyquist采样速率采样信号。本文详述了压缩感知的基本理论，着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展，并介绍了压缩感知的应用及基于压缩感知SAR成像的仿真。 关键词：压缩感知；稀疏表示；观测矩阵；SAR成像； Abstract: Signal sampling is a necessary means of information world physical world to the digital simulation. Over the years, the base theory of signal sampling is the famous Nyquist sampling theorem, but a large amount of data generated by the waste of storage space. Compressed sensing and put forward a new kind of sampling theory, it can be much less than the Nyquist sampling signal sampling rate. This paper introduces the basic theory of compressed sensing, emphatically introduces the new progress in three aspects of signal sparse representation, design of measurement matrix and reconstruction algorithm, and introduces the application of compressed sensing and Simulation of SAR imaging based on Compressive Sensing Keywords: Compressed sensing; Sparse representation; The observation matrix; SAR imaging; 0 引言 Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。可见，带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩实际上是一种资源浪费，因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言，我们得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist采样机制是冗余的或者说是非信息的。 于是很自然地引出一个问题：能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于Nyquist 采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论，成功实现了信号的同时采样与压缩。