(R)恒成立:
A f 2
m=-
n=-
||
2
B f 2(7)则函数集合{ mn }组成一框架.正常数A 和B 分别表示
框架的下边界和上边界,度量了框架的冗余性.
利用框架理论进行稀疏表示的好处就是利用冗余性可以得到更加有效的表示[80].一方面,框架字典的设计具有较强的理论基础,一些常见的变换如冗余DCT 变换、二进小波、多小波、小波包等都能够构成冗余的框架.另一方面,框架字典由给定的框架结构决定,改变函数集合{ mn }的参数取值,就可以方便地得到不同的字典原子,丰富的原子会更大可能地符合信号本身所固有的特性.当取极限情况A =B 时,则称该框架是紧框架.当{ mn }是线性独立时,框架就不是冗余的,变为Riesz 基.当A =B =1,则该框架变为正交基.
3.4 字典学习
以上字典均或多或少的需要利用信号的先验信息,原子类型一旦确定就不再变化,当研究的信号发生变化时,所确定的字典不一定再适合.在超完备冗余字典的情况下,为了对很多类型的信号都能得到较好的表示结果,需要自适应的冗余字典.自适应冗余字典设计的思路是通过字典学习算法获得更符合信号内容,特征,或者纹理信息的原则.但是,冗余性会带来字典中原子数目的剧增,而且在冗余字典下自适应求解信号的最佳稀疏逼近是一个NP 难问题,那么如何设计快速、有效且复杂度低的优化算法,是需要考虑的问题.自适应冗余字典可以随着不同的输入信号做出调整[81~87],近年来在图像去噪、图像去马赛克、图像修复和识别等领域中均有着成功的应用.字典学习[81,82]就是从数据中学习稀疏表示下最优表示,使得字典中原子尺度和特性更接近于需要表示的图像信号.为实现上述功能,已涌现出众多的字典学习算法,其中大多数是基于贝叶斯模型的最大似然值和最大后验概率,通过获取图像信号的先验来选择更合适的原子组成自适应字典,获得字典原子.其中被广泛应用的有MOD 算法[81],ILS DLA [83],RLS DLA [84],SL0 D LA [85],KSVD 算法[82],以及在此基础上发展起来的多尺度KSVD 版本,EK SVD [86],DK SVD [87]等.众多的应用实验结果表明,
1655
第 7 期焦李成:压缩感知回顾与展望
KSVD算法对各种图像处理任务均具有更好的效果.
4 观测系统
源于Kashin创立的范函分析和逼近论的压缩感知
理论有两个核心内容,一个是稀疏性,由信号本身决定,另外一个就是不相关性,由感知系统和信号共同确定.压缩感知理论联合了观测和稀疏矩阵之间的稀疏观念和不相关观念,通过重构满足未完成的测量集最稀疏可能信号[73].压缩感知在很大程度上依靠随机观测矩阵,因为它提供了广泛的观测-稀疏矩阵不相干对,给重构也提供了条件,这就产生了CS理论.在对信号进行稀疏表示后,接下来要设计与表达系统不相干的感知系统,即观测采样矩阵.
4.1 随机观测
压缩感知理论成立的条件之一就是要求感知矩阵和稀疏矩阵低相关的情况.直觉上,可以看到观测矩阵和稀疏矩阵是不相关的,所以采样加进去的新信息在已知的稀疏矩阵基上并不被表示.目前随机矩阵在观测矩阵中被广泛使用,例如高斯随机矩阵,在很大概率上对于固定的字典矩阵不相关.当 是高斯随机矩阵时,可以证明 能以较大概率满足约束等距特性,因此可以通过选择一个其中每一个元素都满足N(0,1/N)的独立正态分布的高斯观测矩阵获得.高斯观测矩阵的优点在于它几乎与任意稀疏信号都不相关,因而所需的观测次数最小.随机观测矩阵属于非适应性的测量,在实际实现中具有复杂度较高,难以在大规模问题中应用的缺点.
4.2 确定性观测
目前,除了如前所述的随机观测矩阵之外,不少学者基于RIP理论提出了多种确定性测量矩阵,例如Chirp测量矩阵、Alltop序列形成的测量矩阵、半Fourier 矩阵、结构Fourier矩阵等等.此外,来自于快速算法的Noiselets也被证明和正交基字典之间具有低相关的性质.最近有学者指出可以在压缩感知中采用自适应性的观测矩阵[88]:基于相关性理论,将投影矩阵和观测矩阵的非相关条件可以等价为Gramma矩阵:
Gram:(A CS)T A C S(8)的单位阵逼近问题:
min
(A C S)T A C S-I 22
s.t.A C S=
(9)即,首先产生一个随机观测矩阵,然后利用信号的稀疏基的信息,训练学习出一个优化观测矩阵,相比随机观测矩阵,
优化之后得到的观测矩阵与字典矩阵之间具有更低的相干性.采用最近Martin提出K SVD方法求解
式(9)中的优化问题,可以根据字典矩阵优化求解确定性的观测矩阵,观测矩阵的优化过程如图4所示.
将优化观测矩阵用于压缩感知理论应用中,能够提高信号的重构精度或者在相同的重构精度下具有更少的测量数目.
4.3 压缩信息获取
正如前面指出的那样,压缩感知理论在有限维矢量空间描述信号,在将其实际应用时必须要考虑其物理实现,即采样方式.目前常采用的压缩观测的实现方法包括随机下采样[89]、模拟信息转换器(AIC)采样[90]以及随机滤波器[91]等.AIC压缩滤波器设计要经过三个关键步骤:解调、滤波、ADC低速率采样,如图5所示.
由图中可以看出:模拟信号x(t)首先经过一个伪随机序列,即PN序列p c(t),进行调制,然后经过一个模拟低通滤波器h(t),最后,通过一个传统的低速AD 转换器进行采样得到观测数据y(n).利用这样的AIC 采样模型,就实现了在更少的数据下对信号的描述.
另外一种压缩信息获取的实现方式就是随机滤波器,通过一个单位脉冲响应为随机信号的FIR数字滤波器与原始信号进行卷积,然后将卷积后的信号下采样的办法实现,同样适用于稀疏的可压缩的信号,记随机滤波器h,原始信号x,那么长度为M的下采样向量y =D (h*x),实现结构如图6(a)所示.这种结构的优点之一在于它可以利用FFT快速实现,如图6(b)所示.
关于压缩感知框架下的压缩信息获取,也有部分学者认为可以在AD采样之后进行压缩观测.例如目前已有的一些压缩成像设备中,既有一些像单像素相机那样
1656 电 子 学 报2011年
在AD采样之前进行压缩观测的成像设备,也有一些在传统的成像设备基础上再加上一个线性观测器(又称随机反转板、成像码盘等),通过在后端的计算平台上求解非线性优化问题,可以获得分辨率更高的影像.
5 压缩感知信号恢复
利用压缩感知理论可以实现从低分辨观测中恢复出高分辨信号,其付出的代价就是在信号重建时的软件代价.
5.1 l1范数下的凸化压缩感知框架
如前所述,由Cand s和Donoho提出的l
1
范数下的凸化压缩感知恢复框架是一个里程碑式的工作,它的基本思想是将式(5)的非凸的优化目标用式(6)的l1范数来代替[3].在该框架下的压缩感知信号恢复得到了许多数学领域的学者的广泛关注,并提出了一系列的方法,包括内点法、GPSR、FPC等.然而,这存在如下问题.第一,l1范数和l0范数优化解等价性的条件不易判断.验证给定矩阵是否满足RIP是一个NP难问题,目前只有Candes,Tao[92,93]和Donoho等借助Johnson Linden strauss(JL)引理[94]和随机矩阵理论[95]证明了满足特定分布的某些随机矩阵,能以较高的概率满足RI P;第二,
虽然l
1范数是距离l
范数最近的凸稀疏测度,但只有
在很严格的条件下l1范数和l0范数优化的结果才有等价性[93],一般的实际信号都无法满足;第三,一般情
况下l
1范数与真实稀疏解的差距过大.l
1
范数无法区
分稀疏系数的位置,所以尽管整体上重构信号在欧氏距离上逼近原信号,但是存在位置混淆的现象,从而容易出现不期望的人工效应;第四,虽然经证明[3]:在l1范数凸化压缩感知框架下,仅用O(K log(N/K))个独立同分布的高斯观测即能以高概率精确重构稀疏度为K 的信号,即,高概率重建需要的观测数目需要满足M cK,c log2(N/K+1),重构的计算复杂度的量级在O(N3),这对于较长信号,其计算复杂度难以忍受.5.2 l p范数下的松弛压缩感知框架
一个自然的改进方法是l
p
范数下的松弛压缩感知框架.A Manduca等人指出[96]:尽管没有理论上全局极小点唯一性的保证,实践中很多非凸的重构模型在低
采样率下优于l
1
范数重构模型.R Gribonval等人[97]分
析了欠定系统的l
p
范数稀疏重构中的参数p和有限等距常数 组成的p- 平面进行的划分,结果如图7所示.虽然获得一些理论结果的指导,但由于有限等距常数指标都是不可计算的,因此在工程应用中欠缺实际意义.
5.3 l0范数下的非凸压缩感知框架
从上述分析可以看到:在l
1
范数下的凸化压缩感
知框架和l
p
范数下的松弛压缩感知框架中,通过对信息算子A C S= 的RI P约束,即需要信息算子具有好
的有限等距性质,来回避l
范数的求解,导致了CS重构中存在理论分析和求解质量上的一些困难和瓶颈问
题.直接从l
范数优化入手构建非凸压缩感知框架不失为一种可行的策略,因为一方面,l0解具有最稀疏的形式,另一方面,非凸CS框架可以缓解RIP约束带来的诸多问题,我们称之为Non RI P非凸CS框架.图8给出
了l
、l
p
和l
1
范数优化问题和解的稀疏性对比
.
和基于RIP的凸化和松弛压缩感知相比:Non RI P
约束的非凸CS框架的优化目标直接针对l
范数和信号先验设计;在该框架下,信号的先验可以方便的引入到优化问题模型,观测矩阵不再局限于满足特定分布的随机矩阵,对于不同的矩阵 ,Non RIP具有一致可恢复(Unifor m Recoverability)的能力,因此更适用被噪声污染的工程实践中所获得的信号,这有利于突破目前凸化和松弛压缩感知框架在理论分析和求解质量上的瓶颈问题.
6 压缩感知的应用
6.1 压缩感知超宽带信号处理
Yonina C.Eldar提出了模拟信号在平移不变空间的
压缩感知实现[98].该方法对有限维模型进行了扩展,将压缩采样应用到模拟域上,使得低速率采样下的超宽带信号处理成为可能.它定义了连续时间信号的稀疏性,对连续稀疏信号在平移不变空间实现了低速率采
1657
第 7 期焦李成:压缩感知回顾与展望
样.国内学者石光明等人提出的基于低速率采样压缩感知的UWB回声信号探测[99],Wei Dai等人提出的阶层加权码和限制性整数压缩感知[100]以及Jose L Parede s 等人提出的压缩感知超宽带信道估计[101]等压缩感知的一些发展,都是建立在该模型的基础上的.Matthe w A Herman等人将CS应用到高分辨率雷达探测中[36],通过发射充足的 不相关 脉冲,利用CS技术来获得高分辨的目标探测性能.
6.2 压缩成像
和传统的成像方式完全不同;压缩感知成像可以从以远低于Nyquist采样率的采样率获取高质量的图像,有效降低了传感器数目与硬件成本,为微波、医疗成像提供了新的理论和方法,目前在医疗成像、光学成像、对地观测等领域得到了成功的应用.第一个被广泛认可的实际系统就是美国Rice大学Baraniuk等人研制出的单像素相机,类似的系统还有Kir研制的Analog to Infor mation Conver ter(AIC)、莱斯大学R Baraniuk教授研制的单像素相机和A/I转换器、麻省理工学院研制的MRI RF脉冲设备、麻省理工学院W T Free man教授研制的编码孔径相机、耶鲁大学研制的超谱成像仪、伊利诺伊州立大学O Milenkovic研制的DNA微阵列传感器,以及我国中科院研制的CS滤波器和混沌腔等.美国DARPA(Defense Advanced Research Projects Agenc y)资助的MONTAGE(Multiple Optical Non Redundant Aperture Generalized Sensors)研究计划极具应用潜力,目前已完成焦平面编码等技术可行性的实验验证.在国内,自2009年973计划开始资助中科院电子所、北京航空航天大学、西安电子科技大学、清华大学、上海交通大学等单位开展 稀疏微波成像 的研究.
6.3 压缩机器学习
在有限维的压缩感知框架中,观测向量可以看作是原始数据的一组特征,因此可以采用压缩感知理论建立压缩机器学习框架,把机器学习中典型的分类与回归问题在该框架下以更简洁的方式求解.
此外,Jarvis Haupt等人将压缩感知用于处理网络数据,提出了网络数据压缩感知[102].由于网络数据信息量比较大,因此可以将每个传感器节点的数据进行观测,就可以利用CS理论解决网络数据信息量比较大的问题.
7 总结与展望
压缩感知理论利用了信号的稀疏特性,将原来基于奈奎斯特采样定理的信号采样过程转化为基于优化计算恢复信号的观测过程.本文对压缩感知理论框架的全过程进行了描述,详细阐述了压缩感知理论所涉及的关键技术,综述了国内外研究成果、存在的公开问题及最新的相关理论.尽管目前关于CS的研究非常多,但作者认为有如下几点内容可供读者参考:
(1)在稀疏表示方面,低秩表示和流形结构与稀疏性有着密切联系,将其引入信号的稀疏表示有望得到更好的结果;
(2)在压缩观测方面,目前的做法大都采用线性观测的方式,如果能考虑实际环境中的可能噪声,在观测时引入某些局部的非线性操作,将有望得到更加鲁棒的观测;
(3)在优化重建方面,如果能联合信号的先验和稀疏性先验求解优化问题,将有望得到更好的恢复效果.
参考文献
[1]D https://www.wendangku.net/doc/c217341980.html,pressed sensing[J].IEEE Transactions on In
formation Theory,2006,52(4):1289-1306.
[2]E Cand s,M Wakin.An i ntroduction to compressive sampling
[J].IEEE Signal Processing Magazine,2008,25(2):21-30.
[3]D Donoho,Y Tsaig.Extensions of compressed sensing[J].
Signal Processing,2006,86(3):533-548.
[4]E Cand s,J Romberg,T Tao.Robus t uncertainty principles:ex
act signal reconstruction from highly incomplete frequency in formation[J].IEEE Transactions on Information Theory,2006, 52(2):489-509.
[5]E Cand s,T Tao.Near optimal signal reco very from random
projections:U niversal encoding strategies?[J].IEEE Transac tions on Information Theory,2006,52(12):5406-5425. [6]S Sarvotham,D Baron,R G Baraniu k.Measu rements vs.bits:
comp ressed sensing meets information theory[A].Allerton Conference on Commu nication,Control,and Computing,M on ticello[C].IL,September2006.
[7]M Akcakaya,V Tarokh.A frame cons truction and a universal
distortion bound for sparse repres entations[J].IEEE Transac tions on Signal Pro cessing,2008,56(6):2443-2450.
[8]B Babadi,N Kalouptsidis,V Tarokh.asymptotic achievability
of the Cram r Rao bound for noisy compressive sampling[J].
IEEE Transactions on Signal Processing,2009,57(3):1233-1236.
[9]B M ichael,M Wakin,J Laska,et https://www.wendangku.net/doc/c217341980.html,pressive imaging for
video representation and coding[A].Proc.Picture Coding Sym po sium(PCS)[C].Beijing,China,April2006.
[10]M L ustig,D Donoho,J M Pauly.Sparse MRI:the application
of compressed sensing for rapid MR imaging[J].M agnetic Resonance in M edicine,December2007,58(6):1182-1195.
[11]J Provost,F Lesage.The application of compressed sensing for
photo aco us tic tomography[J].IEEE Transaction on Medical Imaging,2009,28(4):585-594.
[12]H Ju ng,K Sung,S Kris hna,E Y Kim,J C Ye.K t FOCU SS:
A general compressed sensing framework for high resolution
1658 电 子 学 报2011年
dynamic MRI[J].Magnetic Resonance in M edicine,2009, 61:103-116.
[13]Y C Kim,S S Narayanan,K S N ayak.Accelerated three di
mensional upper airway M RI using compressed sensing[J].
M agnetic Resonance in Medicine,2009,61:1434-1440. [14]J Trzasko,A Manduca.Highly under s ampled magnetic reso
nance image reconstruction via homotopic ell 0 minimization [J].IEEE Transactions on Medical Imaging,2009,28(1):106 -121.
[15]S Hu,M Lustig,et https://www.wendangku.net/doc/c217341980.html,press ed sensing for resolution en
hancement of hyperpolarized13C flyback3D MRSI[J].Jour nal of M agnetic Resonance,2008,192(2):258-264. [16]W L Chan,K Charan,et al.A single pixel terahertz imaging
system based on compressive sensing[J].Applied Physics Letter s,2008,93(12):101-105.
[17]J W Ma.Single pixel remote sensing[J].IEEE Transactions
on Geoscience and Remote Sensing Letters,2009,6(2):199 -203.
[18]H Y Y u and G https://www.wendangku.net/doc/c217341980.html,pressed sensing based interior to
mography[J].Phy sics in M edicine and Biolo gy,2009,54: 2791-2805.
[19]M Duarte,M Davenport,et al.Single pixel imaging via com
pressive s ampling[J].IEEE Signal Processing Magazine, 2008,25(2):83-91.
[20]J Romberg.Imaging v ia compressive sampling[J].IEEE Sig
nal Processing Magazine,2008,25(2):14-20.
[21]R Baraniuk and P https://www.wendangku.net/doc/c217341980.html,pressive radar imaging[A].
IEEE Radar Conference[C].Waltham,Massachusetts,April 2007.128-133.
[22]G T aub ck and F Hlawatsch.A compress ed s ensing technique
for OFDM channel estimation in mobile environments:Ex plo iting channel sparsity for reducing pilots[A].IEEE Int.
Conf.on Acous tics,Speech,and Signal Pro cessing(ICASSP)
[C].L as Vegas,N evada,April2008.2885-2889.
[23]W Bajwa,J Haupt,A Sayeed and R N owak.Jo int source
channel commu nication for distributed estimation in sensor networks[J].IEEE T ransactions on Signal Pro cessing,2007,
53(10):3629-3653.
[24]W U Bajwa,J Haupt,G Raz,R https://www.wendangku.net/doc/c217341980.html,pressed channel
sensi ng[A].Conf on Info Sciences and Systems(CISS)[C].
Princeton,New Jersey,March2008.
[25]Y Mo s tofi,P https://www.wendangku.net/doc/c217341980.html,pressed mapping of commu nication
signal s trength[A].M ilitary Commu nications Conference
[C].San Diego,CA,No vember2008.
[26]W U Bajwa,A Sayeed,R https://www.wendangku.net/doc/c217341980.html,pressed sensing of
wireless channels in time,frequency,and s pace[A].A silomar
Conf on Signals,Systems,and Computers[C].Pacific Grove,
California,October2008.
[27]J Wright,A Y ang,Arvind Ganesh,Shankar Shastry,Yi M a.
Robust face reco gnition via sparse repres entation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009,31(2):210-227.
[28]M Elad.Optimized projections for compressed sensing[J].
IEEE Transaction on Signal Processing,2007,55(12):5695-
5702.
[29]O Maillard,R Muno https://www.wendangku.net/doc/c217341980.html,press ed Leas t Squares Regression
[A].Neu ral Information Processing Systems(NIPS)[C].
Vancouver,Canada,December2009.
[30]J M airal,F Bach,J Ponce,G Sapiro,A Zisserman.Discrimina
tive learned dictionaries for lo cal image analysis[A].IEEE Conf on Compu ter Vision and Pattern Recogni tion(CV PR)
[C].Anchorage,Processing,2008.
[31]R Calderbank,S Jafarpou r,and R https://www.wendangku.net/doc/c217341980.html,pressed learn
ing:U niversal sparse di mensionality reduction and learning in the measu rement domain[R].Technical report,Rice Universi ty,2009.
[32]W Dai,M Sheikh,O M ilenkovic,R G https://www.wendangku.net/doc/c217341980.html,pressive
sensing DNA microarrays[R].Rice U niversity T echnical.Re port ECE-07-06,M ay2007.1-8.
[33]W Dai,O M ilenkovic,M A Sheikh,and R G Baraniuk.Probe
design for compressive s ensing DNA microarrays[A].IEEE International Conference on Bioinformatics and Biomedicine
[C].IEEE Press,2008.163-169.
[34]M A Sheikh,S Sarvotham,O Milenkovic,R G Baraniuk.DNA
array decoding from nonlinear measurements by belief propa gation[A].14th IEEE/SP Works hop on Statistical Signal Pro cessing[C].Madis on,WI,U SA,Aug.2007.215-219. [35]M Sheikh,O Milenkovic,R G Baraniuk.Designing compres
sive sensing DNA microarray s[A].IEEE Workshop on Com putational Advances in Mul ti Sensor Adaptive Processing (CAMSAP)[C].St Thomas,U S Virgin Islands,December 2007.
[36]M Herman,T Strohmer.High resolution radar via compressed
sensing[J].IEEE Transactions on Signal Processing,2009,57
(6):2275-2284.
[37]K R Varshney,M etin,J W Fisher,A S Wills ky.Sparse rep
resentation in structured dictionaries with application to syn thetic aperture radar[J].IEEE Trans actions on Signal Pro cessing,2008,56(8):3548-3561.
[38]R Neelamani,C Krohn,J Krebs,M Deffenbaugh,J Romberg.
Efficient seismic forward modeling using simultaneous random sources and sparsity[A].Society of Exploration Geophysicists (SEG)Annual M eeting[C].L as Vegas(NV),November 2008.
[39]G Hennenfent,F J Herrmann.Simply denoise:wavefield re
construction via jittered undersampli ng[J].Geophysics,2008,
73(13):V19-V28.
[40]J Bobin,J L Starck,R https://www.wendangku.net/doc/c217341980.html,pressed sensing in as
1659
第 7 期焦李成:压缩感知回顾与展望
tronomy[J].Applied M athematics and Computation,2008, 206(2):980-988.
[41]D Shamsi,P Boufounos,F K oushanfar.Noninvasive leakage
power tomography of integrated circuits by compressive sens ing[A].Pro ceeding of the13th International Symposium on Low Power Electronics and Design[C].Bangalore,India, 2008.
[42]R M Willet,M E G ehm,D J Brady.M ultiscale recons truction
for computational spectral imaging[A].Proc SPIE,6498, SPIE IS and Electronic Imaging[C].2007.
[43]V K Go yal,A K Fletcher,S https://www.wendangku.net/doc/c217341980.html,pressive sampling
and lo ssy comp ression[J].IEEE Signal Pro cessing Magazine, 2008,25(2):48-56.
[44]L Baboulaz,P L Dragotti.Exact featu re extraction using finite
rate of inno vation principles with an application to image su per resolu tion[J].IEEE Transactions on Image Pro cessing, 2009,18(2):281-298.
[45]D Baron,M F D u arte,M ichael B Wakin,Shriram Sarvotham,
Richard G Baraniuk.D istributed compressive sensing[J].Neu ral Information Pro cessing Systems(NIPS),2005.
[46]V Cevher,A G urbuz,J M cClellan,R https://www.wendangku.net/doc/c217341980.html,pressive
wireless arrays for bearing es timation of sparse sources in an gle domain[A].IEEE Int Conf on Acoustics,Speech,and Sig nal Processing(ICASSP)[C].Las V egas,Nevada,April 2008.
[47]A G u rbuz,J M cClellan,V Cevher.A compressive beamform
ing method[A].IEEE Int Conf on Acoustics,Speech,and Sig nal Pro cessing(ICASSP)[C].Las V egas,Nevada,April 2008.
[48]D Takhar,V Bansal,M Wakin,M D uarte,D Baron,J Laska,
K F Kelly,R G Baraniuk.A compressed sensing camera:New theory and an implementation using digital micromirrors[A].
Proc Comput Imaging IV at SPIE Electronic Imaging[C].San Jose,Jan.2006.
[49]H Jung,J C Ye,E Y Kim.Improved k t BLASK,k t SEN SE
using FOCUSS[J].Phy s Med Biol,2007,52:3201-3226.
[50]S Ji,Y Xue,L Carin.Bayesian compressive sensing[J].IEEE
Transactions on Signal Processing,2008,56(6):2346-2356.
[51]Y T Qi,D H Liu,D Dunson,L Carin.Bayesian multi task
compressive sensing w ith dirichlet p ro cess priors[A].Interna tional Conference on Machine L earning(ICM L)[C].Helsin ki,Finland,2008.768-775.
[52]M W Seeger,H N https://www.wendangku.net/doc/c217341980.html,pressed sensing and bayesian ex
perimental design[A].Int Conf on Machine Learni ng(ICML)
[C].Helsinki,Finland,2008.912-919.
[53]A M Brucks tein,M Elad,M Z ibulevsky.A non negative and
s parse enough solu tion of an underdetermined linear system of equations is unique[A].ISCCSP[C].M al ta,2008.762-767.
[54]B M atei,Y M eyer.A variant on the compressed sensing of
Emmanuel Cand s[OL].https://www.wendangku.net/doc/c217341980.html,/cs.
[55]M F D uarte,R G Baraniuk.Spectral Compressive Sensing
[OL].https://www.wendangku.net/doc/c217341980.html,/cs,(Preprint). [56]W Guo,W Y i n.Edge CS:an edge guided compressive sensing
recons truction[R].Rice University CAAM Technical Report TR10-02,2010.
[57]M F Duarte,R G Baraniuk.Kronecker Compressive Sensing
[OL].http://www.ds https://www.wendangku.net/doc/c217341980.html,/cs,(Preprint). [58]L Gan.Blo ck compressed sensing of natu ral i mages[A].Conf
on Digital Signal Processi ng(DSP)[C].Cardiff,UK,July 2007.
[59]M Mis hali,Y C Eldar.Blind mul ti band signal reconstruction:
compressed sensing for analog signals[J].IEEE Transactions on Signal Processing,2009,57(3):993-1009.
[60]M Mishali,Y C Eldar.From theory to practice:Sub Nyquist
sampli ng of sparse w ideband analog signals[J].IEEE Journal of Selected Topics on Signal Processing,2010,4(2):375-
391.
[61]M A Davenport,P T Boufouno s,M B Wakin,R G Baraniuk.
Signal processing with compressive measurements[J].IEEE Journal of Selected Topics on Signal Processing,2010,4(2): 445-460.
[62]S G M allat,Z F Zhang.Matching pu rsuits with time frequency
dictionaries[J].IEEE Transactions on Signal Processing, 1993,41(12):3397-3415.
[63]J A Tropp,A C Gilbert.Signal recovery from random mea
su rements via orthogonal matching pursuit[J].IEEE Transac tions on Information Theory,2007,53(12):4655-4666. [64]M Fornasier,H Rau hut.Iterative thresho lding algorithms[J].
Applied and Computational Harmonic Analysis,2008,25(2): 187-208.
[65]S Fo ucart,M Lai.Sparses t solutions of underdetermined linear
sy s tems via lp mi nimization for0[66]T Cai,L Wang,G X u.Shifting inequality and recovery of
sparse signals[J].IEEE Transactions on Signal Processing,
2010,58(3):1300-1308.
[67]T Tony Cai,L Wang,G W X u.N ew bounds for res tricted i
sometry constants[J].IEEE T ransactions on Information The ory,2010,56(9):4388-4394.
[68]D L Donoho,X Huo.Uncertainty principles and ideal atomic
decompo si tion[J].IEEE Transactions on Information Theory, 1999,47(7):2845-2862.
[69]M Elad,A M Brucks tein.A generalized uncertainty p rinciple
and sparse representation i n pai r s of bases[J].IEEE Transac tions on Information Theory,2002,48(9):2558-2567. [70]B S Kashin,V N T emlyakov.A remark on Compressed Sens
ing[J].Mathematics and Statis tics,2007,82(5-6):748-
755.
1660 电 子 学 报2011年
[71]E Cand s,Y C Eldarb,D Needella,P https://www.wendangku.net/doc/c217341980.html,pressed
sensi ng with coherent and redu ndant dictionaries[J].Applied and Compu tational Harmonic Analysis,2011,31(1):59-73.
[72]R Chartrand.Exact reconstruction of sparse signals via non
convex minimization[J].IEEE Signal Process L ett,2007,14
(10):707-710.
[73]R Chartrand,V Staneva.Restricted isometry properties and
nonconvex compressive sensing[J].Inverse Problerms,2008,
24(035020):1-14.
[74]E Cand s,M B Wakin,S P Boyd.Enhancing spar si ty by
reweighted l1minimization[J].Journal of Fourier Analysis and Applications,2008,14(5):877-905.
[75]Z B Xu,H Y Wang,X Y Chang.L1/2Reg ularizer[J].Sci
China Ser F Inf Sci,Jan.2009,52(1):1-9.
[76]E L Pennec,S Mallat.Sparse geometrical image representa
tion with bandelets[J].IEEE Transactions on Image Process ing,2005,l4(41):423-438.
[77]张春梅,尹忠科,肖明霞.基于冗余字典的信号超完备表
示与稀疏分解[J].科学通报,2006,51(6):628-633. [78]M Elad.Sparse and Redundant Representations:From Theory
to Applications i n Signal and Image Pro cessing[M].Springer, 2010.
[79]R J Duffin,A C Schaeffer.A class of non harmonic Fo u rier
series[J].Trans.AM S72,1952:341-366.
[80]K Engan,S O Aase,J Hakon Husoy.M ethod of optimal direc
tions for frame design,acoustics,speech,and signal processing
[A].Proceedings of ICA SSP 99[C].1999.2443-2446.
[81]M Elad,M Aharon.Image denoising via sparse and redundant
representations over learned dictionaries[J].IEEE Transac tions on Image Pro cessing,2006,15(12):3736-3745. [82]M Aharon,M Elad,A Bruckstein.K SVD:an algorithm for
designing overcomplete dictionaries for sparse representation [J].IEEE Transactions on Signal Pro cessing,2006,54(11): 4311-4322.
[83]K Engan,K Skretting,J H Husoy.A family of iterative L S
bas ed dictionary learning algorithms,ILS DLA,for sparse sig nal rep resentation[J].Digital Signal Process,2007,17:32-
49.
[84]K Skretting,K Engan.Recursive least squares dictionary learn
ing algorithm[J].IEEE Transactions on Signal Pro cessing, 2010,58(4):2121-2130.
[85]H Z ayyani,M Babaie Z adeh.Thres holded smoothed L0(SL0)
dictionary learning for spar s e representations[A].IEEE Inter national Conference on Acoustics,Speech and Signal Process ing[C].19-24Apr.2009.1825-1828.
[86]R Mazhar,P D Gader.EK S VD:Optimized dictionary design
for sparse representations[A].19th International Conference on Pattern Recognition[C].8-11Dec.2008.1-4.
[87]Q Z hang,B X Li.Discriminative K SVD for dictionary learn
ing in face recogni tion[A].IEEE Conference on Computer Vision and Pattern Recognition(CVPR)[C].13-18June 2010.2691-2698.
[88]J M Duarte Carvajalino,G Sapiro.Learning to sense sparse
signals:simultaneous sensing matrix and s parsifying dictionary optimization[J].IEEE Transactions on Image Processing,
2009,18(7):1395-1408.
[89]S Wei.Random Sampling Using Shannon Interpolation and
Poisson Summation Formulae[R/OL].Technical Report,
https://www.wendangku.net/doc/c217341980.html,/abs/0909.2292
[90]T Ragheb,S Kirolos,et al.Implementation models for analog
to information conversion via random sampli ng[A].IEEE In ternational Midwest Symposium on Circuits and Systems[C].
2007.
[91]J A Tropp,M B Wakin,M F Duarte,D Baron,R G Bara
niuk r.Random filters for compressive sampling and recon s truction[A].Proc ICA SSP2006[C].Toulo use,France, 2006.
[92]D L Donoho,M Elad.Optimal spar s e representation in general
(nonorthogo i nal)dictionaries via L1minimization[J].Proc Nat Aca Sci,2003,100(5):2197-2202.
[93]E Cand s,T Tao.Decoding by linear programming[J].IEEE
Transactions on Information Theory,2005,51(12):4203-
4215.
[94]D L Donoho.For mo s t large undetermined systems of equa
tions,the minimal l1 norm near solution approximates the spar sest near solu tion[J].Comm on Pu re and Applied Math,
2006,59(7):907-934.
[95]R Baraniu k,M Davenport,R D eVore,M Wakin.A simple
pro of of the restricted isometry p roperty for random matrices [J].Constr Approx,2008,28(3):253-263.
[96]J Trzas ko,A M anduca.Relaxed conditions for sparse signal
recovery with general concave priors[J].IEEE Transaction on Signal Processing,2009,57(11):4347-4354.
[97]M Davies,and R Gribonval.Restricted isometry constant
where l p spar s e reco very can fail for0Transactions on Information Theory,2009,55(5):2203-
2214.
[98]Y C https://www.wendangku.net/doc/c217341980.html,pressed sensing of analog signals in shift in
variant spaces[J].IEEE Transactions on Signal Processing, 2009,57(8):2986-2997.
[99]G M Shi,J L i n,X Y Chen,F Qi,D H Liu,L Z hang.UWB e
cho signal detection with ultra low rate sampling based on compressed sensing[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2008,55(4):379-383.
[100]W Dai,O M ilenkovic.Weighted superimpo sed codes and constrained integer compress ed sensi ng[J].IEEE Transac
tions on Information Theory,2009,55(5):2215-2229. [101]J L Paredes,G R Arce,Z M Wang.U ltra wideband com
1661
第 7 期焦李成:压缩感知回顾与展望
pressed sensing:channel es timation[J].IEEE Journal of Se lected T opics in Signal Processing,2007,1(3):383-395.[102]J Haupt,W U Bajwa,M Rabbat,R https://www.wendangku.net/doc/c217341980.html,pressed sensing for networked data[J].IEEE Signal Processing
Magazine,2008,25(2):92-101.
作者简介
焦李成 男,1959年生于陕西.西安电子科技大学电子工程学院教授、博导,CCF高级会员,主要研究领域为智能算法,机器学习,非线性科学,小波理论及其应用.
E mail:lchjiao@mail.xi https://www.wendangku.net/doc/c217341980.html,
杨淑媛 女,1978年生于山东.西安电子科技大学电子工程学院教授、博导.主要研究领域为智能信号与图像处理、机器学习等. 刘 芳 女,1963年生于北京.西安电子科技大学计算机学院教授、博导.主要研究领域为智能信息处理、模式识别等.
侯 彪 男,1974年生于陕西.西安电子科技大学电子工程学院教授、博导.主要研究领域为合成孔径雷达图像处理.
1662 电 子 学 报2011年
压缩感知简介
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代码重构出来一维和二维的图形，进而比较这几种算法的性能。
压缩感知理论综述(原创)
压缩感知理论综述 摘要：信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，但其产生的大量数据造成了存储空间的浪费。压缩感知（Compressed Sensing）提出一种新的采样理论，它能够以远低于Nyquist采样速率采样信号。本文详述了压缩感知的基本理论，着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展，并介绍了压缩感知的应用及仿真，举例说明基于压缩感知理论的编解码理论在一维信号、二维图像处理上的应用。 关键词：压缩感知；稀疏表示；观测矩阵；编码；解码 一、引言 Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。可见，带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩实际上是一种资源浪费，因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言，我们得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist采样机制是冗余的或者说是非信息的。 于是很自然地引出一个问题：能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于Nyquist 采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论，成功实现了信号的同时采样与压缩。 简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架
几种压缩感知算法
.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项）。 算法结果：
压缩感知 很好的综述 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/c217341980.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压缩感知理论
压缩感知理论 一、压缩感知理论简介 压缩感知，又称压缩采样，压缩传感。它作为一个新的采样理论，它通过开发信号的稀疏特性，在远小于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 ，常用的测量矩阵有高斯随机阵等。接下来是算法的重构，由于用少数信号恢复原来的大信号，这是一个欠定问题，一般用最优化方法来求解。这就是压缩感知理论体系的基本理论。 四、对这一创新案例的分析
压缩感知磁共振成像技术综述
https://www.wendangku.net/doc/c217341980.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/c217341980.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/c217341980.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--
压缩感知原理
压缩感知原理(附程序) 1压缩感知引论 传统方式下的信号处理，是按照奈奎斯特采样定理对信号进行采样，得到大量的采样数据，需要先获取整个信号再进行压缩，其压缩过程如图2.1。 图2.1 传统的信号压缩过程 在此过程中，大部分采样数据将会被抛弃，即高速采样后再压缩的过程浪费了大量的采样资源，这就极大地增加了存储和传输的代价。 由于带宽的限制，许多信号只包含少量的重要频率的信息。所以大部分信号是稀疏的或是可压缩的，对于这种类型的信号，既然传统方法采样的多数数据会被抛弃，那么，为什么还要获取全部数据而不直接获取需要保留的数据呢？Candes和Donoho等人于2004年提出了压缩感知理论。该理论可以理解为将模拟数据节约地转换成压缩数字形式，避免了资源的浪费。即，在采样信号的同时就对数据进行适当的压缩，相当于在采样过程中寻找最少的系数来表示信号，并能用适当的重构算法从压缩数据中恢复出原始信号。压缩感知的主要目标是从少量的非适应线性测量中精确有效地重构信号。核心概念在于试图从原理上降低对一个信号进行测量的成本。压缩感知包含了许多重要的数学理论，具有广泛的应用前景，最近几年引起广泛的关注，得到了蓬勃的发展。 2压缩感知原理 压缩感知，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号进行信号重构的技术。或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。压缩感知跳过了采集N个样本这一步骤，直接获得压缩的信号的表示。CS理论利用到了许多自然信号在特定的基 上具有紧凑的表示。即这些信号是“稀疏”的或“可压缩”的。由于这一特性，压缩感知理论的信号编解码框架和传统的压缩过程大不一样，主要包括信号的稀疏表示、编码测量和重构算法等三个方面。
基于压缩感知的自适应数字波束形成算法
第35卷第2期电子与信息学报Vol.35 No.2 2013年2月 Journal of Electronics & Information Technology Feb. 2013 基于压缩感知的自适应数字波束形成算法 王 建 盛卫星* 韩玉兵 马晓峰 (南京理工大学电子工程与光电技术学院南京 210094) 摘要：该文根据目标在空间的稀疏性，提出了接收端的基于压缩感知理论的自适应数字波束形成算法。在阵元稀布的情况下，用压缩感知的压缩采样理论，恢复出缺失通道的回波信息，然后用恢复的信号做数字波束形成。该算法所形成的波束具有波束旁瓣低，指向误差小，干扰方向零陷深，而且没有栅瓣等优点，波束性能接近满阵时候的波束性能，而且使用该方法减少的阵元数远远大于其他稀布阵方法减少的阵元数。采用蒙特卡罗方法对该方法进行了性能评估，给出了不同信噪比、不同干噪比、不同快拍情况下的计算结果，仿真结果也验证了该算法的正确性。 关键词：压缩感知；数字波束形成；稀布阵；多测量欠定系统正则化聚焦求解算法 中图分类号：TN911.72 文献标识码：A 文章编号：1009-5896(2013)02-0438-07 DOI: 10.3724/SP.J.1146.2012.00517 Adaptive Digital Beamforming Algorithm Based on Compressed Sensing Wang Jian Sheng Wei-xing Han Yu-bing Ma Xiao-feng (School of Electronic Engineering and Optoelectronic Technology, Nanjing University of Science and Technology, Nanjing 210094, China) Abstract: A new adaptive digital beamforming in receiving end based on compressed sensing is proposed. In the case of sparse array antenna, receiving signal from absence elements can be reconstructed by using the theory of compressed sensing. Adaptive digital beamforming techniques are then adopted to form antenna beams, whose main lobe is steered to desired direction and nulls are steered to the directions of interferences. Simulation results with Monte Carlo method show that the beam performances of the proposed method are approaching to that of full array antenna, and actual antenna elements can be reduced greatly. Key words:Compressed sensing; Digital beamforming; Sparse arrays; Regularized M-FOCUSS 1 引言 阵列天线的口径越大，则波束越窄，增益越高，但所需的阵元数也越多，设备量越大。大型阵列，特别是数字波束形成天线或固态有源相控阵天线，每个天线单元都有一个对应的T/R组件，因而阵列的阵面造价十分昂贵，是雷达耗资的主要部分。在阵列口径尺寸一定的前提下，减少T/R组件数目主要有两种方法：一种是子阵技术，但子阵技术的应用不可避免地会引起栅瓣，从而会减小阵列波束电扫描的范围；另一种方法是稀疏布阵技术。传统的稀布阵方式通常可以节省一半左右的T/R组件，它采用遗传算法等各种优化算法对阵元的位置进行优化，以尽可能降低阵列天线波束的副瓣。但是，这样的优化通常只是针对阵列的静态方向图进行的，当波束扫描或进行自适应干扰抑制时，很难保证波束的性能。 2012-05-02收到，2012-11-12改回 *通信作者：盛卫星 shengwx@https://www.wendangku.net/doc/c217341980.html, 压缩感知(Compressed Sensing, CS)理论[14]?是一个充分利用信号的稀疏性(或可压缩性)的全新信号采集、编解码理论。该理论指出，只要信号是稀疏的或可压缩的(即在某个变换域上是稀疏的)，那么就可以用一个与变换基不相关的采样矩阵将变换所得的高维信号投影到一个低维空间上，然后通过求解一个优化问题，从这些少量的投影中以高概率重构出原信号。压缩感知理论突破了传统的奈奎斯特采样定理的束缚，实现了对未知信号的边感知边压缩。在一定条件下，只需采样少量数据，就可以通过重构算法精确地恢复出原信号。由于采样数据少，恢复数据精确，该技术已被广泛应用于数据采集[5]、医学成像、雷达[68]?、通信等领域。 本文通过对压缩感知理论以及数字波束形成(DBF)技术的研究，提出了一种双基地系统的DBF 接收阵下的基于压缩感知的自适应数字波束形成算法。该方法适用于DBF接收阵的应用场合。由于发射能量的空间合成和发射方向图等原因，该方法尚不能适用于发射波束形成。该方法利用目标在空域
形象易懂讲解算法II——压缩感知课件
形象易懂讲解算法II——压缩感知 之前曾经写过一篇关于小波变换的回答，得到很多赞，十分感动。之后一直说要更新，却不知不觉拖了快一年。。此次更新，思来想去，决定挑战一下压缩感知（compressed sensing, CS）这一题目。 在我看来，压缩感知是信号处理领域进入21世纪以来取得的最耀眼的成果，并在磁共振成像、图像处理等领域取得了有效应用。压缩感知理论在其复杂的数学表述背后蕴含着非常精妙的思想。基于一个有想象力的思路，辅以严格的数学证明，压缩感知实现了神奇的效果，突破了信号处理领域的金科玉律——奈奎斯特采样定律。即，在信号采样的过程中，用很少的采样点，实现了和全采样一样的效果。 正是被它的精妙思想所打动，我选择它作为专栏第二篇的主题。理解压缩感知的难度可能要比之前讲的小波还要大，但是我们从中依然可以梳理出清晰的脉络。这篇文章的目标和之前一样，我将抛弃复杂的数学表述，用没有公式的语言讲清楚压缩感知的核心思路，尽量形象易懂。我还绘制了大量示意图，因为排版问题，我将主要以PPT的形式呈现，并按slice标好了序号。 --------------------------------------------------------------------------------------------------------------------------- 一、什么是压缩感知（CS）？ compressed sensing又称compressed sampling，似乎后者看上去更加直观一些。没错，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维
压缩感知技术综述
压缩感知技术综述 摘要：信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的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 采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论，成功实现了信号的同时采样与压缩。
基于MATLAB的图像压缩感知算法的实现(含源文件)
毕业设计（论文） 课题名称基于MATLAB的图像压缩感知 算法的实现 目录 目录......................................................... I
第1章绪论 (6) 1.1 研究背景和意义 (6) 1.2 数据压缩技术 (7) 1.2.1 传统数据压缩技术 (7) 1.2.2 压缩感知理论（Compressed/Compressive Sensing/Sampling, CS） (8) 1.3 无线传感器网络 (10) 1.3.1 无线传感器网络概述 (10) 1.3.2 无线传感器网络数据压缩的必要性 (12) 1.4 本文主要工作和内容安排 (13) 第2章压缩感知理论 (14) 2.1压缩感知的前提条件—稀疏性和不相干性 (14) 2.2 三个关键技术 (17) 2.3信号的稀疏表示 (18) 2.4 观测矩阵设计 (20) 2.5 稀疏信号的重构 (22) 2.6 重构算法 (23) 2.7 压缩感知优势及不足 (24) 2.8 压缩感知在传感网中的观测方式 (25) 第3章压缩感知理论应用概述 (27) 3.1 压缩成像 (27) 3.2 模拟信息转换 (27) 3.3 生物传感 (28) 3.4 本章小结 (28) 第4章 CS在无线传感网中的应用 (29) 4.1 研究背景 (29) 4.1.1 基于感知数据相关性的压缩 (29) 4.1.2传统压缩重构方法 (29)
4.1.3 图像压缩重构质量的评价 (30) 4.2 压缩感知理论算法对一维信号的实现 (32) 4.2.1 CS用于WSN的优势 (32) 4.2.2 观测重构模型 (33) 4.2.2 正交匹配追踪算法（OMP） (33) 4.2.3 算法的实现及结果分析 (34) 4.3 压缩感知理论算法对二维图像重构的实现 (38) 4.3.1 基于小波变换的分块压缩感知理论 (38) 4.3.2 实现步骤 (39) 4.3.3 重构结果及分析 (42) 4.4 本章小结 (45) 第5章总结与展望 (46) 5.1 工作总结 (46) 5.2 后续展望 (46) 参考文献 (47) 致谢 (49) 附录 (50) 摘要 数据压缩技术是提高无线数据传输速度的有效措施之一。传统的数据压缩技术是基于奈奎斯特采样定律进行采样，并根据数据本身的特性降低其冗余度，从而达到压
压缩感知重构算法之基追踪
压缩感知重构算法之基追踪（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/c217341980.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]).
