压缩感知理论介绍

压缩感知?

许志强?

中国科学院数学与系统科学研究院,

计算数学与科学工程计算研究所,

科学与工程计算国家重点实验室,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.doczj.com/doc/f810859161.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

那么,给定一编码、解码对(Φ,?),我们关心其性能,即:

∥x0??(Φx0)∥X,

此处X为一给定范数.本文中,我们通常选择X为?p范数,并用下标p表示?p范数.当x0中非0元素数目较小的时候,一种较为自然的解码?0(y)是如下规划问题的解:

∥x∥0

P0:min

x∈R N

s.t.Φx=y.

这里,∥x∥0表示x中非0元素的数目.我们用符号?0(y)表示P0的解.也就是说,?0(y)为在所有满足线性方程组Φx=y的向量中,选择非0元素数目最少的.如果我们对矩阵Φ加些许限制,由P0定义的解码,可精确恢复s-稀疏向量:

定理 2.1假定Φ∈R n×N是一个任2s列均线性无关的矩阵.我们选择解码为?0,那么,对任意的x0∈Σs,

?0(Φx0)=x0.

根据定理2.1,如果我们选取观测次数n=2s,那么就存在一编码、解码对(Φ,?)使得对任意的x0∈Σs,均有?(Φx0)=x0.这意味着:如果我们希望恢复一个嵌入在N维空间的s-稀疏向量,那么2s次观测次数就足够了.

但是,问题P0的求解是十分不平凡的.事实上,P0是一个NP完全问题[14,31].那么,我们能否找到一个更为有效的解码算法?一个令人惊讶的事实是,如果矩阵Φ满足一定条件,那么回答则是肯定的,但我们要在观测次数上付出些许代价.我们现在将解码?1(y)定义为如下问题的解:

∥x∥1

P1:min

x∈R N

s.t.Φx=y.

如所知,P1可转化为如下的线性规划问题：

t1+t2+···+t N

P2:min

t∈R N

s.t.Φx=y

?t j≤x j≤t j,j=1,...,N

t j≥0,j=1,...,N.

从一个简单的论证可看出,P1的解与P2的解相同.因此,可找到有效的算法对P1求解.但是,一个自然的问题是:P1的解与P0的解等价吗?或者是,

对什么样的观测矩阵Φ,P1的解与P0的解总一致?

为回答这一问题,我们首先介绍矩阵的零空间性质.零空间性质思想的主要出发点是：解码通常是从集合

{x∈R N:Φx=y}.

中按一定规则挑选我们需要的元素.由线性代数知识可知,解集{x∈R N:Φx=y}可由原始的信号x0,与矩阵的Φ的零空间

KerΦ:={x∈R N:Φx=0}

所确定.因此,人们考虑通过刻画矩阵Φ的零空间,从而给出P1解与P0解一致的充要条件.我们首先介绍零空间性质的定义.为描述方便,我们介绍如下符号:对于指标集T?{1,...,N}及向量v∈R N,我们将v中指标在T中的元素取出,形成一个新的向量,标记为v T∈R#T.我们用T c表示T的补集.类似的,我们可定义矩阵ΦT.

定义 2.1我们称矩阵Φ满足s-阶零空间性质,如果对任意的v∈KerΦ,均有

∥v T∥1<∥v T c∥1,对任意的T?{1,...,N},#T=s.

直观上,我们将零空间性质理解为KerΦ的非0元素较为均匀的分布,不会明显的集中于某s个元素上.采用零空间性质,我们有

定理 2.2我们选择解码为?1.那么,对任意的x∈Σs,

?1(Φx)=x

如果和仅仅如果Φ满足s-阶零空间性质.

注 2.1用类似于零空间性质的方式,描述?1解码可恢复s-稀疏信号,在人们研究L1最佳逼近时就已经出现(参考[33]).与定理2.2一致的形式首先出现在[23].此外,文[18,19]也隐含了类似的结果.

虽然可以用零空间性质给出P1的解与P0的解一致的充要条件.但是,零空间性质并不容易操作,无论在理论还是计算方面.也就是说,给一个矩阵Φ,难以从理论上证明其是否满足零空间性质,也不容易在计算机上快速验证.因而,人们考虑了另外一种刻画方式,即是所谓的矩阵RIP性质(Restricted Isometry Property).

我们首先介绍RIP性质的定义[9].我们说矩阵Φ满足s-阶RIP性质,如果存在常数δs∈[0,1)使得

(1?δs)∥x∥2≤∥Φx∥2≤(1+δs)∥x∥2(2)

ΦT所有特征值位于区间对任意的x∈Σs成立.实际上,(2)等价于Grammian矩阵Φ?

T

[1?δs,1+δs],这里#T≤s.我们称δs为RIP常数.

我们首先看一下如何从直观上理解RIP矩阵.倘若δs=0,那么矩阵Φ为一标准正交矩阵.因而也是一方阵.然而在压缩感知中,我们希望矩阵Φ是“扁”的,也就是n

下面定理给出了解码?1能够精确恢复s-稀疏信号的一个充分条件.

定理 2.3([6,7])假定编码矩阵Φ满足2s 阶RIP 性质,且RIP 常数δ2s ≤√2?1.

我们选择解码?1.那么,对任意的x ∈Σs ,均有

?1(Φx )=x.上述定理表明,我们可用RIP 矩阵编码、?1解码精确恢复s -稀疏信号.然而,现实世界中的信号并非严格稀疏的,通常仅仅是近似稀疏.对于此类信号,如果我们仍然用RIP 矩阵Φ进行编码,选则解码为?1,那么我们能较好的恢复非稀疏信号吗?令人惊讶的是,我们仍然能较好的完成任务.为介绍这方面的结果,我们首先介绍最佳s -项逼近误差的概念.给定范数∥·∥X ,那么信号x ∈R N 的在范数∥·∥X 意义下最佳s -项逼近误差为

σs (x )X :=min z ∈Σs

∥x ?z ∥X .对于K ?R N ,我们令

σs (K )X :=max x ∈K

σs (x )X .下面定理指出,对于一般信号,我们采用RIP 矩阵编码与用?1作解码,那么恢复效果可用?1范数意义下的最佳逼近误差刻画.

定理 2.4假定编码矩阵Φ满足2s 阶RIP 性质,且RIP 常数δ2s ≤√2?1.我们选择解码为?1.那么对任意的x ∈R N ,我们有

∥?1(Φx )?x ∥2≤C 0σs (x )1√s

,此处C 0为一常数.

注 2.2定理2.3与定理2.4首先在[7]中被证明.但给出的RIP 常数较为粗糙.在[6]中,E.Cand`e s 将RIP 常数改进为δ2s ≤√2?1.仍有一些论文考虑改进定理2.3中的RIP 常数√2?1[4,21].特别是，Mo 和Li 将该常数改进为δ2s <0.4931[30].此外,Davies 和Gribonval 建构一个例子表明,如果δ2s ≥1√2,那么?1解码不能恢复一些s -稀疏信号.注意到这些研究均是针对δ2s ,也就是要求矩阵满足2s 阶RIP 条件.在[5]中,Cai,Wang 和Xu 考虑了矩阵满足s -阶RIP 条件的情况,给出了P 1能恢复s -稀疏信号的充分条件为δs <0.307.此外,我们特别指出,借助离散几何中的多面体理论,在文[16]中,Donoho 给出了?1解码能精确恢复s -稀疏信号的充要条件.

注 2.3对于0

min x ∈R N ∥x ∥p s .t .Φx =y.

这里∥x ∥p :=(∑N j =1|x j |p )

1/p .事实上,当0

注 2.4在本文中,我们假定信号的稀疏性指非0元素较少.但是,很多应用问题里面,信号是在一“字典”或者紧框架表示下是稀疏的.对于此类情况,文[11]进行了研究.并将定理2.4进行了推广.但是,这个方向仍值得进一步深入探索.

我们现在回到本文开始所提出的问题：

如果选择解码为?1,为精确恢复所有s -稀疏信号,观察次数n 最少应为多少?

文[22]给出了如下定理:

定理 2.5假定Φ∈R n ×N 及解码为?1.那么,如果

?1(Φx )=x,

对任意x ∈Σ2s ,则

n ≥c 1s log

(N c 2s ),这里c 1=1log 9≈0.455且c 2=4.

根据上述定理,如果解码选择为?1,那么我们至少需要进行n =O (s log

(N s )

)次观测,才能精确恢复s -稀疏信号.这个下界能够达到吗?也就是说,对于n =O (s log (N s )),我们能否构造观测矩阵Φ∈R n ×N ,使得对任意x ∈Σs ,均有?1(Φx )=x ?根据定理2.3,我们可将该问题归结为能否构造满足s -阶RIP 条件的矩阵Φ∈R n ×N 使得n =O (s log (N s ))?我们将在下节回答该问题.

3RIP 矩阵

根据定理2.3和定理2.4,为保证?1解码能恢复稀疏或者近似稀疏信号,我们需要构造RIP 矩阵.我们希望对于给定的n,N ∈Z ,构造一n ×N 的矩阵Φ,以使其对尽量大的s 满足s -阶RIP 条件.那么,如何构造此类矩阵?当前的主要构造方法有：随机矩阵、结构随机矩阵与确定性矩阵.

3.1随机矩阵

我们考虑两类随机矩阵：Gaussian随机矩阵与Bernoulli随机矩阵.所谓Gaussian随机矩阵,即指矩阵中的元素?i,j是独立的随机变量且服从如下分布:

?i,j～N(0,1 n )

即服从期望为0,方差为1

n

的Gaussian分布.所谓Bernoulli矩阵,即指矩阵Φ中的元素以

相同的概率取1√

n 或?1√

n

.

定理 3.1假定n×N的矩阵Φ是一个Gaussian或者Bernoulli随机矩阵.那么,当

s≤C1n/log(N/s)

矩阵Φ是一个s-阶RIP矩阵的概率不小于

1?exp(?C2n),

此处常数C1,C2仅仅依赖于RIP常数δ.

注 3.1一个类似于定理3.1的结果最早由Kashin得到[24].文[10,41]中也给出了定理3.1的证明.一个比较简单的证明方法是[1]中所介绍的.此外,文[1]也给出了RIP 性质与Johnson-Lindenstrauss引理的关联.

注 3.2定理3.1表明Gaussian随机矩阵或Bernoulli随机矩阵满足s=O(n/log(N/s))阶的RIP性质.根据逼近论中的宽度理论,对于给定的n,N∈N,这里的s已经达到了最佳阶.

3.2确定性矩阵

虽然随机矩阵能产生尺寸接近最优的RIP矩阵.在工程实际中,人们更希望构造一个确定性RIP矩阵.因为确定性矩阵更利于工程设计,此外,从构造解码算法角度来看,确定性矩阵利于降低内存、设计快速的恢复算法等.然而,现在仍然缺少令人满意的确定性RIP矩阵构造方法.当前的构造方法主要是基于矩阵的列相干性.

假定矩阵Φ=(a1,...,a D)∈C n×N,这里n≤N.我们假定矩阵Φ中的列元素标准化,即∥a i∥2=1.矩阵Φ的列相干性定义为

M(Φ):=max

i=j

|?a i,a j?|.

下式给出了M (Φ)的一个下界,也称为Welch 界[43]

M (Φ)≥√N ?n (n ?1)N .(3)

当等号成立的时候,我们称矩阵Φ为最优Grassmannian 框架.文[20]中指出,只有当N ≤n 2,等号才有可能成立(参考[40]).

下面定理显示了矩阵的列相干性与RIP 性质之间的关联[15,2].

定理 3.2假定a 1,...,a N 是矩阵Φ的列元素且其列相干性为μ.那么,矩阵Φ满足RIP 常数为δs =(s ?1)μ的s -阶RIP 性质.

人们能够构造出满足条件

μ=O (log N √n log n )

的矩阵(参考[25,15,45]).我们在此介绍作者在[45]中提出的一种构造方法,其主要利用了数论中的Weil 指数和定理[42]:

定理 3.3([42])假定p 是一个素数.假定f (x )=m 1x +···+m d x d ,且存在一个j ,1≤j ≤d ,使得p m j .那么

p ∑x =1

e 2πi

f (x )p ≤(d ?1)√p.给定正整数q 和d ,我们下面构造一n ×N 矩阵Φ,这里n ≥2q +1为素数,且N =(2q +1)d .那么,矩阵Φ的第j 行定义为

Φj,·=[exp(2πi ?x j ,k ?)√n ]k ∈[?q,q ]d

∈C (2q +1)d ,(4)

这里

x j =[j,j 2,...,j d ]/n mod 1.下面的定理刻画了由(4)所定义的矩阵Φ的列相干性[45].

定理 3.4给定正整数q 和d ,令n ≥2q +1为素数,且N =(2q +1)d .假设n ×N 矩阵Φ由(4)定义.那么,

M (Φ)≤d ?1√n

.

根据Bertrand-Chebyshev 定理,在区间[2q +1,4q +2]中必存在一素数.因此,我们可以假定n ≤4q +2.那么,对定理3.4中的Φ,我们有

M (Φ)≤d ?1√n ≤2log N √n log n .组合定理3.2和定理3.4,我们有

定理 3.5定理3.4中的Φ满足s =O (√n

d )阶RIP 条件．　

在文[45]中,作者也通过数值试验显示该确定性矩阵Φ与随机矩阵的编码效果基本一致.但是,根据定理3.1,随机矩阵能够满足s =O (n/log(N/s ))阶RIP 性质.这要优于由(4)所定义的确定性矩阵Φ的O (√n/d ).

当N ≥2n ,根据Welch 界,对任意的n ×N 矩阵Φ,

μ=M (Φ)≥1√

2(n ?1).因而s ?1

√2(n ?1)≤(s ?1)μ<1.我们由此得到,矩阵Φ满足s ≤√2n 阶RIP 条件.这个界说明,如果我们仅仅分析矩阵

的列相干性,难以论证确定性矩阵满足s =O (n/log(N/s ))阶RIP 性质.最近,借助加性组合与解析数论的工具,Bourgain 等人证明了,当d =2,由(4)所定义的矩阵Φ满足s =n 1/2+?0阶RIP 性质,这里?0是一个充分小的正数.这突破了由分析矩阵的列相干性所带来的1/2瓶颈s =O (n 1/2).然而,Bourgain 等人的证明需假定d =2.如何将其证明扩展到一般的整数d ,仍然是一个挑战性问题.3.3结构随机矩阵

由于Gaussian 矩阵与Bernoulli 矩阵随机性较强,确定性矩阵难以证明具有阶数较好的RIP 性质.本节中,我们将介绍介于确定与随机矩阵之间的一种矩阵：结构随机矩阵.与确定性矩阵相比,结构随机矩阵多了些随机性,因而可以证明其具有较好的RIP 性质,同时,结构随机矩阵的随机性较弱,一般仅具有行随机.更为重要的是,在很多实际应用中,观测矩阵为一结构随机矩阵.我们在此介绍部分随机Fourier 矩阵.我们假定Ψ为N ×N 的离散Fourier 矩阵.也就是,Ψ中的元素为

Ψj,k =1√exp (?2πijk N ),j,k ∈{0,...,N ?1}.

4宽度与最优编码、解码10

我们可在矩阵Ψ中随机选择n行,得到一个n×N的矩阵Ψn,我们称之为部分随机Fourier 矩阵.部分随机Fourier矩阵具有较强的应用背景.例如,很多时候人们观测到的是部分频率信息.这时候,观测矩阵就是一部分随机Fourier矩阵.那么,文[10]中作者证明,矩阵Ψn高概率的满足s=O(n/(log N)6)阶RIP性质.在[38]中,这个结果被改进为s=O(n/(log N)4).然而,人们相信这个结果并非最优的.因而,证明矩阵Ψn高概率的满足s=O(n/log(N/s))阶RIP性质,仍然是一挑战性问题.更多的关于结构随机矩阵的介绍,可参考[36].

4宽度与最优编码、解码

假定K?R N是我们感兴趣的信号集合.我们用A n,N表示所有尺寸为n×N的编码、解码对集合.前面我们已经介绍了一对具体的编码、解码,即矩阵Φ为RIP矩阵,解码为?1.而且我们也看到,该编码、解码对具有优良的性能.我们现在考虑如下问题：对于信号集合K,最优编码、解码对(Φ,?)∈A n,N的性能是什么?我们可用严格的数学语言将该问题描述如下:给定范数X,E n(K)X是什么?这里,

E n(K)X:=inf

(Φ,?)∈A n,N sup

x∈K

∥?Φx?x∥X.

我们将看到,E n(K)X与Gelfand宽度紧密相关.所谓集合K?R N在附范空间(R N,∥·∥X)中n阶Gelfand宽度,即指

d n(K)X:=inf

A∈R n×N

sup

v∈K∩ker A

∥v∥X.

下面的定理显示了E n(K)X与d n(K)X之间的关联.其证明可参考[12].

定理 4.1假定K是R N的一个子集且满足K=?K及K+K=C0K,这里C0是一个大于0的常数,且∥·∥X为一范数.那么

d n(K)X≤E n(K)X≤C0d n(K)X,1≤n≤N.

上面定理显示,我们可用集合K的Gelfand宽度的结果来刻画最优编码、解码对的性能.而Gelfand宽度在经典的逼近论中已有较为丰富的研究,可参考[34,35].我们下面利用该定理,导出一个令人感兴趣的结果.令

B N1:={x∈R N:∥x∥1≤1}.

一个经典的不等式是：

σs(x)2≤

1

√

s

∥x∥1.

我们看到,如果我们选择x ∈B N 1,那么σs (x )2≤1√s

.通过这个不等式,我们可有12√s ≤σs (B N 1)2≤1√s .(5)

人们已经对B N 1的Gelfand 宽度进行了深入研究(参考[22]).特别是,存在常数C 1,C 2

使得C 1min {1,√log(N/n )n }≤d n (B N 1)2≤C 2min {1,√log(N/n )n

}.(6)如果我们希望存在一个常数C 3,使得

E n (B N 1)2≤C 3σs (B N 1)2,

那么,根据定理4.1,(5)和(6),则有

s ≤c 0

n log(N/n )

,这里,c 0为一绝对常数.

注 4.1定理4.1显示了编码、解码对(Φ,?)的最优性能与宽度之间的关联.基于这个关联,人们能更好的理解压缩感知中编码、解码对的性能.此外,用压缩感知中发展的方法,文[22]亦解决了宽度理论中的一些经典问题.5个例最优性

如前所述,对于s -稀疏信号x ,我们一般希望寻找一编码、解码对(Φ,?)∈A n,N 使得?(Φx )=x .那么,对于一般的信号x ∈R N ,我们应该设置什么样的恢复误差才比较合理?一个选择是最佳s 项逼近误差的常数倍,也就是C 0σs (x )X ,这里C 0是一个绝对常数.容易看到,如果x 为s -稀疏信号,那么σs (x )X =0.本节里,我们将讨论,如果选择恢复误差为C 0σs (x )X ,最小观测次数n 至少为多少?

我们说(Φ,?)在范数X 下,满足s -阶个例最优性,倘若

∥?(Φx )?x ∥X ≤C 0σs (x )X ,?x ∈R N .(7)

我们通常选择范数X 为?p 范数.我们主要考虑编码矩阵为RIP 矩阵,解码为?1的情形.我们首先考虑X 为?1范数.

定理 5.1([12])令Φ是3s -阶RIP 矩阵,且RIP 常数为δ3s ≤δ<(√2?1)2/3.那

么,

∥?1(Φx )?x ∥1≤C 0σs (x )1,

?x ∈R N ,

这里C 0=2√2+2?(2√2?2)δ√2?1?(√2+1)δ.从上述定理可看出,定理5.1中定义的编码、解码对在范数?1下具有个例最优性.如前所述,我们可以构n ×N 造矩阵Φ满足s -阶RIP 条件且有n ≥cs log(N/s ),这里c 是一个固定常数.因而,我们只需做O (s log(N/s ))次观测,就可以得到?1范数下的个例最优性.那么,在O (s log(N/s ))次观测的条件下,我们能够达到?2范数下的个例最优性吗?文[12]表

明,在范数?2下,即使要达到1-阶个例最优性,观测次数n ≥N/C 20

.这个结论表明,如果我们希望在?2范数下达到个例最优性,那么观测次数与信号的真实维数基本一致.也就是说,在?2范数个例最优性的评判标准下,人们难以在观测次数上“偷工减料”.

注 5.1给定一x 0∈R N .文[12]研究了概率意义下的?2个例最优性.特别的,文[12]证明了,如果选择Φ∈R n ×N 为Gaussian 矩阵或者Bernoulli 矩阵,这里n =O (s log(N/n )).那么,存在一解码?,使得

∥?(Φx 0)?x 0∥2≤C 0σs (x 0)2

高概率成立.更进一步,文[44]证明了,如果Φ为Gaussian 随机矩阵,解码?选择为P 1的解,那么

∥?(Φx 0)?x 0∥2≤C 0σs (x 0)2

高概率成立.

定理2.4给出了如下结果

∥?(Φx )?x ∥2≤C 0σs (x )1√s ,对所有x ∈R N .

这里的编码、解码对为定理2.4中的编码、解码对.注意到,该结果中左右两边采用了不同的范数.这启发人们将个例最优性的定义推广到一般范数情形.我们说(Φ,?)满足s -阶(q,p )个例最优性,如果

∥?(Φx )?x ∥p ≤C 0σs (x )q s 1/q ?1/p ,对所有x ∈R N .

那么,下面定理给出了一组满足(q,p )个例最优性的编码、解码对.

6算法13

定理 5.2([12])令Φ是满足2k+?k-阶RIP条件,且RIP常数δ

2k+?k

≤δ<1,这里

?k:=k (

N

k

)2?2/q

.

解码?定义为

?(y):=Argmin z∈kerΦσs(z)p.那么,(Φ,?)满足常数为C0的(p,q)个例最优性,这里

C0=21p+321+δ

1?δ

+21+1p?1q.

6算法

本节里,我们介绍解码实现的一些算法.如前所述,我们可将P1转化为线性规划问题.但是,由于我们需要求解的问题规模较大,一些常规的求解线性规划的方法,如单纯形算法及内点算法等,并不能达到令人满意的效果.考虑到问题本身的特殊性,即矩阵A是稠密的,然而需要恢复的信号x0则是稀疏的.人们由此构造了一些迭代算法,如Bregman迭代算法[3,32,48],ADM算法[47]及Proximity算法[27,28]等.Bregman迭代算法已经被证明等价于增广的Lagrangian方法.本文主要介绍另外一种解码算法:贪婪算法.一般而言,当矩阵行数远小于列数,贪婪算法在实际计算中通常有更好的表现.

贪婪算法通常为寻找如下问题的近似解

min

x∈R N

∥x∥0

s.t.∥Φx?y∥2≤ε.

其基本思路就是在Φ中选择最少的列,以使其形成对y的近似表示.最常用的一种贪婪算法为OMP算法[26].该算法首先计算y在当前已选择列张成空间正交投影补,然后计算该正交投影补与Φ中列内积绝对值的大小.我们通常每次选取使内积绝对值达到最大的列.OMP算法也有多种变形,可参考[37].

我们在Algorithm1中详细描述了OMP算法.

我们用OMP s(y)表示OMP算法迭代s步所产生的结果.自然的,人们关心OMP算法的性能[46,29,49].鉴于RIP矩阵是压缩感知中较为流行的一类矩阵,人们自然考虑如果选择编码矩阵为RIP矩阵,解码OMP算法的性能如何?因为定理2.4是对?1解码性能较好的刻画.人们希望将定理2.4扩展到OMP算法.而这最终在文[46]中完成.

Algorithm1OMP s(y)

输入:编码矩阵Φ,向量y,最大稀疏度s

输出:恢复的信号x?.

初始值:r0=y,c0=0,Λ0=?,?=0.

while?≤s do

match:h?=ΦT r?

identity:Λ?+1=Λ?∪{argmax j|h?(j)|}

update:c?+1=argmin

z:supp(z)?Λ?+1

∥y?Φz∥2

r?+1=y?Φc?+1

?=?+1

end while

x?=c s+1

定理 6.1([46])假定0<δ<1,且Φ满足RIP条件δ2s+(1+δ)δ2αs≤δ.那么,对

任意的x∈R N,

∥OMP2(α?1)s(Φx)?x∥2≤C2σs(x)1/√s,

这里α=?16+15δ?且C2=2(1+δ)(√

11+20δ+1)+3.

注 6.1根据定理6.1,为了使OMP算法达到s-阶(2,1)个例最优性,OMP算法需要进行约50s次迭代(如果我们选择δ接近1).那么,一个令人感兴趣的公开问题是,什么是最小的常数n0,使得OMP算法在迭代n0s次后具有s-阶(2,1)个例最优性?此外,文[46]也考虑了OMP算法的(p,q)个例最优性.

致谢:本文在袁亚湘院士建议及鼓励下完成,在此表示感谢.

参考文献

[1]R.G.Baraniuk,M.Davenport,R.A.DeVore and M.Wakin,A simple proof of the restricted

isometry property for random matrices.Constr Approx,2008,28:253–263.

[2]J.Bourgain,S.J.Dilworth,K.Ford,S.Konyagin and D.Kutzarova,Explicit constructions

of RIP matrices and related problems.Duke Math.J,2011,159:145-185.

[3]J.Cai,S.Osher,and Z.Shen,Convergence of the linearized Bregman iteration for?1-norm

minimization.Mathematics of Computation,2009,78:2127-2136.

[4]T.Cai,L.Wang,and G.Xu,Shifting inequality and recovery of sparse signals.IEEE Trans.

Signal Process,2010,58:1300–1308.

[5]T.Cai,L.Wang,and G.Xu,New Bounds for Restricted Isometry Constants,IEEE Trans-

actions on Information Theory,2010,56:4388-4394.

[6] E.Cand`e s,The restricted isometry property and its implications for compressed sensing,C.

R.Math.Acad.Sci.Paris,Series I,2008,346:589-592.

[7] E.J.Cand`e s,J.Romberg,and T.Tao,Stable signal recovery from incomplete and inaccurate

measurements,Comm.Pure Appl.Math.,59(8)(2006)1207-1223.

[8] E.Cand`e s,J.Romberg,T.Tao,Robust uncertainty principles:Exact signal reconstruction

from highly incomplete frequency information,IEEE https://www.doczj.com/doc/f810859161.html,rm.Theory,2006,52:489-509.

[9] E.Cand`e s,T.Tao,Decoding by linear programming,Issue Date:Dec.2005,51:4203-4215.

[10] E.J.Cand`e s and T.Tao,Near-optimal signal recovery from random projections and universal

encoding strategies,This paper appears in:Information Theory,IEEE Transactions on Issue Date:Dec.2006,52:5406-5425.

[11] E.J.Cand′e s,Y.C.Eldar,D.Needell,and P.Randall,Compressed Sensing with Coherent and

Redundant Dictionaries,Applied and Computational Harmonic Analysis,2011,31:59-73.

[12] A.Cohen,W.Dahmen and R.DeVore,Compressed sensing and best k-term approximation,

J.Amer.Math.Soc.2009,22:211–231.

[13]Chartrand,R.,Staneva,V.:Restricted isometry porperties and nonconvex compressive sens-

ing.Inverse Problems2009,24:1-14.

[14]G.Davis,S.Mallat and M.Avellaneda,Adaptive greedy approximations,Constr.Approx.,

1997,13:57–98.

[15]R.DeVore,Deterministic constructions of compressed sensing matrices,Journal of Complexity

2007,23:918-925.

[16] D.L.Donoho,“Neighborly polytopes and sparse solutions of underdetermined linear equa-

tions,”Technical report,Department of Statistics,Stanford University,2005.

[17]M.E.Davies and R.Gribonval,Restricted isometry constants where?p sparse recovery can

fail for0

[18] D.L.Donoho and X.Huo,Uncertainty principles and ideal atomic decompositions,IEEE

https://www.doczj.com/doc/f810859161.html,rm.Theory,2011,47:2845–2862.

[19]M.Elad and A.M.Bruckstein,A generalized uncertainty principle and sparse representation

in pairs of bases,IEEE https://www.doczj.com/doc/f810859161.html,rm.Theory,2002,48:2558–2567.

[20]H.G.Feichtinger and T.Strohmer,editors.Gabor Analysis and algorithms:Theory and

Applications.Birkh¨a user,Boston,1998.

[21]S.Foucart and https://www.doczj.com/doc/f810859161.html,i,Sparsest solutions of underdetermined linear systems via?1-

minimization for0

[22]S.Foucart,A.Pajor,H.Rauhut and T.Ullrich,The Gelfand widths of?p-balls for0

Jounal of Complexity,2010,26:629-640.

[23]R.Gribonval and M.Nielsen,Sparse representations in unions of bases,IEEE https://www.doczj.com/doc/f810859161.html,rm.

Theory2003,49:3320–3325.

[24] B.S.Kashin,Widths of certain?nite-dimensional sets and classes of smooth functions,Izv.

Akad.Nauk SSSR,Ser.Mat.1977,41:334-351;English transl.in https://www.doczj.com/doc/f810859161.html,SR Izv.1978,11: 317-333.

[25] B.S.Kashin,On widths of octahedron,Uspekhi Matem.Nauk1975,30:251-252(Russian).

[26]S.Mallat and Z.Zhang.Matching Pursuits with time-frequency dictionaries.IEEE Trans.

Signal Process.,1993,41:3397-3415/

[27] C.A.Micchelli,Lixin Shen,and Yuesheng Xu,Proximity algorithms for image models:de-

noising,Inverse Problems,2011,27.

[28] C.A.Micchelli,Lixin Shen,Yuesheng Xu and Xueying Zeng,Proximity algorithms for the

L1/TV image denoising model,https://www.doczj.com/doc/f810859161.html,put.Math.,2011.

[29]Q.Mo,Y.Shen,Remarks on the Restricted Isometry Property in Orthogonal Matching

Pursuit algorithm,arXiv:1101.4458.

[30]Q.Mo,S.Li,New bounds on the restricted isometry constantδ2k,https://www.doczj.com/doc/f810859161.html,p.Harm.Anal.,

2011,31:460-468.

[31] B.K.Natarajan,Sparse approximate solutions to linear systems,SIAM https://www.doczj.com/doc/f810859161.html,put.1995,24:

227–234.

[32]S.Osher,Y.Mao,B.Dong,and W.Yin,Fast linearized Bregman iteration for compressed

sensing and sparse denoising,Commun.Math.Sci.2010,8:93-111.

[33] A.Pinkus,On L1-Approximation,Cambridge Tracts in Mathematics93,Cambridge Univer-

sity Press,Cambridge,1989.

[34] A.Pinkus,N-Widths in Approximation Theory,Springer-Verlag,Berlin,1985.

[35] A.Pinkus,N-widths and Optimal Recovery,Lect.Notes AMS Short Course ed.,in:Proc.

Symp.Appl.Math.,1986,36:51–66.

[36]H.Rauhut,Compressive Sensing and Structured Random Matrices,In M.Fornasier,editor,

Theoretical Foundations and Numerical Methods for Sparse Recovery,Volume9of Radon Series Comp.Appl.Math.,pages1-92.deGruyter,2010.

[37]L.Rebollo-Neira and Z.Xu,Adaptive non-uniform B-spline dictionaries on a compact interval,

Signal Processing，2010,90.

[38]M.Rudelson and R.Vershynin,On sparse reconstruction from Fourier and Gaussian mea-

surements,Communications on Pure and Applied Mathematics,2008,61:1025–1045.

[39]Y.Shen,S.Li,Restricted p-isometry property and its application for nonconvex compressive

sensing,Adv Comput Math.DOI10.1007/s10444-011-9219-y.

[40]T.Strohmer and R.Heath,Grassmannian frames with applications to coding and communi-

cation,https://www.doczj.com/doc/f810859161.html,put.Harmon.Anal.2003,14:257-275.

[41]S.J.Szarek.Condition numbers of random https://www.doczj.com/doc/f810859161.html,plexity,1991,7:131–149.

[42] A.Weil,On some exponential sums,PNAS,USA,1948,34:204-207.

[43]L.R.Welch,Lower bounds on the maximum cross-correlation of signals,IEEE https://www.doczj.com/doc/f810859161.html,.

Theory,1974,20:397-399.

[44]P.Wojtaszczyk,Stability and instance optimality for gaussian measurements in compressed

sensing,https://www.doczj.com/doc/f810859161.html,put.Math.2010,10:1-13.

[45]Z.Xu,Deterministic sampling of sparse trigonometric polynomials,Journal of Complexity

2011,27:133-140.

[46]Z.Xu,A remark about orthogonal matching pursuit algorithm,arXiv:1005.3093.

[47]J.Yang and Y.Zhang,Alternating direction algorithms for?1-problems in compressed sensing,

SIAM https://www.doczj.com/doc/f810859161.html,PUT.,Vol.33,No.1,pp.250–278.

[48]W.Yin,S.Osher, D.Goldfarb,and J.Darbon,Bregman iterative algorithms for?1-

minimization with applications to compressed sensing,SIAM Journal on Imaging Sciences, 2008,1:143-168.

[49]T.Zhang,Sparse recovery with orthogonal matching pursuit under RIP,IEEE Transactions

on Information Theory,2011,57:6215-622.

压缩感知简介

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.doczj.com/doc/f810859161.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 ，常用的测量矩阵有高斯随机阵等。接下来是算法的重构，由于用少数信号恢复原来的大信号，这是一个欠定问题，一般用最优化方法来求解。这就是压缩感知理论体系的基本理论。 四、对这一创新案例的分析

压缩感知原理

压缩感知原理(附程序) 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维

压缩感知技术综述

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

压缩感知理论综述

压缩感知理论综述摘要：信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的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 一、引言 在过去的半个世纪里，奈奎斯特采样定理几乎支配着所有的信号或图像等

压缩感知

压缩感知正交匹配追踪算法重构二维图像 摘要 在传统采样过程中，为了避免信号失真，采样频率不得低于信号最高频率的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 范数模型 从数学意义上讲，基于压缩感知理论的信号重建问题就是寻找欠定方程组(程的数