搜档网
当前位置:搜档网 › 压缩感知原理

压缩感知原理

压缩感知原理
压缩感知原理

压缩感知原理

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

文献[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-范数问题: 0min 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)算法。

压缩感知简介

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<

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

压缩感知理论综述 摘要:信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来,指导信号采样的理论基础一直是著名的Nyquist采样定理,但其产生的大量数据造成了存储空间的浪费。压缩感知(Compressed Sensing)提出一种新的采样理论,它能够以远低于Nyquist采样速率采样信号。本文详述了压缩感知的基本理论,着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展,并介绍了压缩感知的应用及仿真,举例说明基于压缩感知理论的编解码理论在一维信号、二维图像处理上的应用。 关键词:压缩感知;稀疏表示;观测矩阵;编码;解码 一、引言 Nyquist采样定理指出,采样速率达到信号带宽的两倍以上时,才能由采样信号精确重建原始信号。可见,带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加,携带信息的信号带宽越来越宽,以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是,信号压缩实际上是一种资源浪费,因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言,我们得到以下结论:带宽不能本质地表达信号的信息,基于信号带宽的Nyquist采样机制是冗余的或者说是非信息的。 于是很自然地引出一个问题:能否利用其它变换空间描述信号,建立新的信号描述和处理的理论框架,使得在保证信息不损失的情况下,用远低于Nyquist 采样定理要求的速率采样信号,同时又可以完全恢复信号。与信号带宽相比,稀疏性能够直观地而且相对本质地表达信号的信息。事实上,稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论,成功实现了信号的同时采样与压缩。 简单地说,压缩感知理论指出:只要信号是可压缩的或在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号,可以证明这样的投影包含了重构信号的足够信息。在该理论框架

压缩感知 很好的综述 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.sodocs.net/doc/118160591.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

陆吾生-压缩感知方法及其在稀疏信号和图像处理中的应用

陆吾生教授短期课程“压缩感知方法及其在稀疏信号和图像 处理中的应用”资料 1. 课程介绍_压缩感知方法及其在稀疏信号和图像处理中的应 用.doc 2. 陆吾生教授短期课程“压缩感知方法及其在稀疏信号和图像处理中的应用”的讲义 Lecture_Notes_CS_LWS_Final.pdf 3. 各章所涉及到的Matlab程序 Main functions Main functions.zip(内含 ex3_1.m (for Example 3.1) ex3_2.m (for Example 3.2) gp_denoise.m (for Algorithm GP in Sec.3.2) fgp_denoise.m (for Algorithm FGP in Sec.3.2) gp_deblurr.m (for Algorithm GPB in Sec.3.3) ) Auxiliary functions Auxiliary functions.zip(内含gen_dct.m oper_L.m oper_Lt.m proj_bound.m proj_pair.m gp_denoise_w.m) Data Data.zip(内含camera256.mat 及 lena256.mat)

4. 陆吾生“压缩感知方法及其在稀疏信号和图像处理中的应用”课程(1A-6B)上课录像 Lecture_LWS_1A.rmvb 2010.11.09.(220M) Lecture_LWS_1B.rmvb 2010.11.09.(231M) Lecture_LWS_2A.rmvb 2010.11.11.(252M) Lecture_LWS_2B.rmvb 2010.11.11.(193M) Lecture_LWS_3A.rmvb 2010.11.12.(225M) Lecture_LWS_3B.rmvb 2010.11.12.(200M) Lecture_LWS_4A.rmvb 2010.11.16.(239M) Lecture_LWS_4B.rmvb 2010.11.16.(169M) Lecture_LWS_5A.rmvb 2010.11.18.(239M) Lecture_LWS_5B.rmvb 2010.11.18.(226M) Lecture_LWS_6A.rmvb 2010.11.19.(256M) Lecture_LWS_6B.rmvb 2010.11.19.(224M) 5. 陆吾生教授2010.11.17.在上海大学所做的学术报告,题为:

压缩感知理论

压缩感知理论 一、压缩感知理论简介 压缩感知,又称压缩采样,压缩传感。它作为一个新的采样理论,它通过开发信号的稀疏特性,在远小于Nyquist 采样率的条件下,用随机采样获取信号的离散样本,然后通过非线性重建算法完美的重建信号。压缩感知理论一经提出,就引起学术界和工业界的广泛关注。它在信息论、图像处理、地球科学、光学、微波成像、模式识别、无线通信、大气、地质等领域受到高度关注,并被美国科技评论评为2007年度十大科技进展。 二、压缩感知产生背景 信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来,指导信号采样的理论基础一直是著名的Nyquist 采样定理。定理指出,只有当采样速率达到信号带宽的两倍以上时,才能由采样信号精确重建原始信号。可见,带宽是Nyquist 采样定理对采样的本质要求。但是,对于超宽带通信和信号处理、核磁共振成像、雷达遥感成像、传感器网络等实际应用,信号的带宽变得越来越大,人们对信号的采样速率、传输速度和存储空间的要求也变得越来越高。为了缓解对信号传输速度和存储空间的压力,当前常见的解决方案是信号压缩但是,信号压缩实际上是一种严重的资源浪费,因为大量采样数据在压缩过程中被丢弃了,它们对于信号来说是不重要的或者只是冗余信息。故而就有人研究如何很好地利用采集到的信号,压缩感知是由 E. J. Candes 、J. Romberg 、T. T ao 和D. L. Donoho 等科学家于2004 年提出,压缩感知方法抛弃了当前信号采样中的冗余信息。它直接从连续时间信号变换得到压缩样本,然后在数字信号处理中采用优化方法处理压缩样本。这里恢复信号所需的优化算法常常是一个已知信号稀疏的欠定线性逆问题。 三、压缩感知理论 压缩感知理论主要涉及到三个方面,即信号的稀疏表示、测量矩阵的设计和重构算法的构造。稀疏信号广义上可理解为信号中只有少数元素是非零的,或者信号在某一变换域内少数元素是非零的。那么在我们如果只保留这些非零数据,丢弃其他的系数,则可以减小储存该信号需要的空间,达到了压缩(有损压缩)的目的,同时,这些系数可以重构原始信号,不过一般而言得到的是X 的一个逼近。在实际生活中有很多数字信号都是稀疏信号或者在某一变换域内是稀疏的,这样压缩感知理论的第一个方面就可以得到满足。如果信号N x R ∈在某变换域内是稀疏的,可以用一组正交基12[,,,]N ψψψψ= 线性组合表示:1 N i i i x s s ψ===ψ∑,其中式中,是对应于正交基的投影系数。由稀疏性可知其内只含有少数不为零的数,感知信号y 可表示为:y x s s =Φ=Φψ=Θ,Φ就为测量矩阵,Ψ为稀疏表示矩阵,当测量矩阵与稀疏表示矩阵不相关时就可以从s 中不失真的恢复出原始信号x ,常用的测量矩阵有高斯随机阵等。接下来是算法的重构,由于用少数信号恢复原来的大信号,这是一个欠定问题,一般用最优化方法来求解。这就是压缩感知理论体系的基本理论。 四、对这一创新案例的分析

压缩感知原理

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

压缩感知原理

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

(完整word版)压缩感知原理

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

压缩感知技术综述

压缩感知技术综述 摘要:信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来,指导信号采样的理论基础一直是著名的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 采样定理要求的速率采样信号,同时又可以完全恢复信号。与信号带宽相比,稀疏性能够直观地而且相对本质地表达信号的信息。事实上,稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论,成功实现了信号的同时采样与压缩。

压缩感知

压缩感知正交匹配追踪算法重构二维图像 摘要 在传统采样过程中,为了避免信号失真,采样频率不得低于信号最高频率的2倍。然而,对于数字图像、视频的获取,依照香农定理会导致海量的采样数据,大大增加了存储和传输的代价。压缩感知采用非自适应性投影来保持信号的原始结构,能够通过数值最优化问题准确重构原始信号。该理论指出,如果信号是稀疏的或者在某个基下可压缩,那么用少量的观测值就可以保持信号的结构和相关信息。基于该理论,用于精确重构信号的采样需求数量可以远低于观测的维度,这极大地缓解了宽带信号处理的压力。正交匹配追踪算法正是压缩感知信号检测的一种算法。本文将介绍正交匹配追踪算法的原理以并给出了测试效果。 一、压缩感知简介 压缩感知是一种新的信息获取理论,是建立在信号稀疏表示、测量矩阵的非相关性以及逼近理论上的一种信号采集和重建的方法。该理论指出,只要信号是稀疏的或者在某个基下时刻压缩的,就可以通过远低于奈奎斯特采样定理要求的采样率获取信号的结构信息,再通过重构算法完成信号的精确重构。 压缩感知理论只要包括两个部分:将信号在观测向量上投影得到观测值,以及利用重构算法由观测值重构信号。 设x 是一个长度为N 的信号,其稀疏度为()N K K <,系数度为K 指x 本身有K 个非零元素,或者在某种变化域ψ内的展开系数有K 个非零元素。 信号(假设信号在变换域ψ内K 系数)在观测向量上的投影可以表示为: N M M i x y i <==,,,1,, φ 其中,y i 为压缩感知获取的M 个采样值,() φi M i 1 =是一组观测向量,由 () φi M i 1 =组成 的观测基Φ与变换基ψ不相关。 重构信号的关键是找出信号x 在ψ域中的稀疏表示,可以通过l 0范数优化问题找到具有系数结构的解: x y t s T x Φ=ψ. .min 由于上式的优化问题是一个难求解的NP-hard 问题,所以可以用l 1约束取代l 0约束: x y t s T x Φ=ψ. .min 1 此时,压缩感知获得的采样值已经保持了原信号的结构及相关信息,因此可以不需要重构信号,利用检测算法直接从采样值中提取特征量进行判断,完成信号检测任务。 二、正交匹配追踪算法 1.最小0l 范数模型 从数学意义上讲,基于压缩感知理论的信号重建问题就是寻找欠定方程组(程的数

压缩感知理论综述

压缩感知理论综述摘要:信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来,指导信号采样的理论基础一直是著名的Nyquist采样定理,但其产生的大量数据造成了存储空间的浪费。压缩感知(Compressed Sen si ng)提出一种新的采样理论,它能够以远低于Nyquist采样速率采样信号。本文详述了压缩感知的基本理论,着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展,并介绍了压缩感知的应用及仿真,举例说明基于压缩感知理论的编解码理论在一维信号、二维图像处理上的应用。 关键词:压缩感知;稀疏表示;观测矩阵;编码;解码 一、引言 Nyquist采样定理指出,采样速率达到信号带宽的两倍以上时,才能由采样信号精确重建原始信号。可见,带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加,携带信息的信号带宽越来越宽,以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是,信号压缩实际上是一种资源浪费,因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言,我们得到以下结论:带宽不能本质地表达信号的信息,基于信号带宽的Nyquist采样机制是冗余的或者说 是非信息的。 于是很自然地引出一个问题:能否利用其它变换空间描述信号,建立新的信号描述和处理的理论框架,使得在保证信息不损失的情况下,用远低于Nyquist 采样定理要求的速率采样信号,同时又可以完全恢复信号。与信号带宽相比,稀疏性能够直观地而且相对本质地表达信号的信息。事实上,稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论,成功实现了信号的同时采样与压缩。 简单地说,压缩感知理论指出:只要信号是可压缩的或在某个变换域是稀疏的,那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号,可以证明这样的投影包含了重构信号的足够信息。在该理论框架 下,采样速率不再取决于信号的带宽,而在很大程度上取决于两个基本准则:稀疏性

压缩感知技术研究进展分析

压缩感知技术研究进展 摘要:信号采样是联系模拟信源和数字信息的桥梁.人们对信息的巨量需求 造成了信号采样、传输和存储的巨大压力. 如何缓解这种压力又能有效提取承载在信号中的有用信息是信号与信息处理中急需解决的问题之一. 近年国际上出现的压缩感知理论(Compressed Sensing,CS)为缓解这些压力提供了解决方法. 本文综述了CS 理论框架及关键技术问题, 并介绍了仿真实例、应用前景, 评述了其中的公开问题,对研究中现存的难点问题进行了探讨,最后对CS技术做了一下总结和展望. 关键词:压缩感知;稀疏表示;观测矩阵;编码;解码 Advances in Theory and Application of Compressed Sensing Abstract:Sampling is the bridge between analog source signal and digital signal. With the rapid progress of information technologies, the demands for information are increasing dramatically. So the existing systems are very difficult to meet the challenges of high speed sampling, large volume data transmission and storage. How to acquire information in signal efficiently is an urgent problem in electronic information fields. In recent year s, an emerging theory of signal acquirement. compressed sensing(CS) provides a golden opportunity for solving this problem. This paper reviews the theoretical framework and the key technical problems of compressed sensing and introduces the latest developments of signal sparse representation, design of measurement matrix and reconstruction algorithm. Then this paper also reviews several open problems in CS theory and discusses the existing difficult problems. In the end, the application fields of compressed sensing are introduced. Key words:compressed sensing;sparse representation; the observation matrix; coding;decoding 一、引言 在过去的半个世纪里,奈奎斯特采样定理几乎支配着所有的信号或图像等

相关主题