搜索
压缩感知∗许志强†中国科学院数学与系统科学研究院,计算数学与科学工程计算研究所,科学与工程计算国家重点实验室,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)资助.yEmail:xuzq@lsec.cc.ac.cn12稀疏信号的恢复2数绝对值较小.这也就是图像能够进行压缩的原理.然而,这同时为人们减少观测次数n从理论上提供了可能性.因而,压缩感知的主要任务为:对尽量小的n,设计n×N观测矩阵Φ,以及通过Φx快速恢复x的算法.所以,压缩感知的研究主要分为两方面：矩阵Φ的设计;与反求信号x的算法.本文主要介绍压缩感知的一些基本结果.在每节里,我们采用注记的方式介绍当前的一些研究进展及研究问题,同时提供与之相关的参考文献,以使感兴趣的读者可进一步探索.本文组织结构如下:第2节中我们介绍了稀疏信号精确恢复的编码、解码方法.特别是,我们将介绍矩阵的零空间性质,及RIP矩阵编码与ℓ1解码的性能.我们在第3节中介绍RIP矩阵的构造方法,包括随机矩阵、结构随机矩阵及确定性矩阵.在第4节中,为理解最优编码、解码对的性能,我们介绍了Gelfand宽度与编码、解码对性能的关联.我们在第5节中介绍了编码、解码对在不同范数意义下的个例最优性.最后一节简要介绍实现解码的算法.2稀疏信号的恢复为方便介绍压缩感知理论,我们将信号的稀疏性简单理解为信号中非0元素数目较少.我们所指的信号即为一向量x∈RN.我们用Σs表示s-稀疏向量集合,即Σs:={x∈RN:∥x∥0≤s},这里∥x∥0表示x中的非0元素数目.所谓对信号x0∈RN编码,即指用一n×N的矩阵Φ与x0∈RN进行乘积,那么我们得到y=Φx0.此处,y∈Rn即为我们所观测到的关于x0的信息.所谓解码,就是试图通过y反求x0,也就是寻找一从Rn到RN的映射,我们将该映射记为∆.我们用∆(y)表示反求结果.一般而言,若nN,则有无数个x∈RN满足y=Φx.因而,只有借助信号稀疏性的特征,我们才有可能反求原始的信号x0.那么,给定一编码、解码对(Φ,∆),我们关心其性能,即:∥x0−∆(Φx0)∥X,此处X为一给定范数.本文中,我们通常选择X为ℓp范数,并用下标p表示ℓp范数.当x0中非0元素数目较小的时候,一种较为自然的解码∆0(y)是如下规划问题的解:P0:minx∈RN∥x∥0s.t.Φx=y.2稀疏信号的恢复3这里,∥x∥0表示x中非0元素的数目.我们用符号∆0(y)表示P0的解.也就是说,∆0(y)为在所有满足线性方程组Φx=y的向量中,选择非0元素数目最少的.如果我们对矩阵Φ加些许限制,由P0定义的解码,可精确恢复s-稀疏向量:定理2.1假定Φ∈Rn×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)定义为如下问题的解:P1:minx∈RN∥x∥1s.t.Φx=y.如所知,P1可转化为如下的线性规划问题：P2:mint∈RNt1+t2+···+tNs.t.Φx=y−tj≤xj≤tj,j=1,...,Ntj≥0,j=1,...,N.从一个简单的论证可看出,P1的解与P2的解相同.因此,可找到有效的算法对P1求解.但是,一个自然的问题是:P1的解与P0的解等价吗?或者是,对什么样的观测矩阵Φ,P1的解与P0的解总一致?为回答这一问题,我们首先介绍矩阵的零空间性质.零空间性质思想的主要出发点是：解码通常是从集合{x∈RN:Φx=y}.中按一定规则挑选我们需要的元素.由线性代数知识可知,解集{x∈RN:Φx=y}可由原始的信号x0,与矩阵的Φ的零空间KerΦ:={x∈RN:Φx=0}2稀疏信号的恢复4所确定.因此,人们考虑通过刻画矩阵Φ的零空间,从而给出P1解与P0解一致的充要条件.我们首先介绍零空间性质的定义.为描述方便,我们介绍如下符号:对于指标集T⊂{1,...,N}及向量v∈RN,我们将v中指标在T中的元素取出,形成一个新的向量,标记为vT∈R#T.我们用Tc表示T的补集.类似的,我们可定义矩阵ΦT.定义2.1我们称矩阵Φ满足s-阶零空间性质,如果对任意的v∈KerΦ,均有∥vT∥1∥vTc∥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性质(RestrictedIsometryProperty).我们首先介绍RIP性质的定义[9].我们说矩阵Φ满足s-阶RIP性质,如果存在常数δs∈[0,1)使得(1−δs)∥x∥2≤∥Φx∥2≤(1+δs)∥x∥2(2)对任意的x∈Σs成立.实际上,(2)等价于Grammian矩阵Φ⊤TΦT所有特征值位于区间[1−δs,1+δs],这里#T≤s.我们称δs为RIP常数.我们首先看一下如何从直观上理解RIP矩阵.倘若δs=0,那么矩阵Φ为一标准正交矩阵.因而也是一方阵.然而在压缩感知中,我们希望矩阵Φ是“扁”的,也就是nN,同时保留类似于正交矩阵的特征.因而,RIP矩阵的定义(2),事实上刻画了矩阵Φ中任取s列所形成的n×s矩阵接近于正交矩阵的程度.RIP常数δs越接近于0,其任取s列所形成的子矩阵也就越接近于正交.从某种意义上来说,性质也就越好.下面定理给出了解码∆1能够精确恢复s-稀疏信号的一个充分条件.2稀疏信号的恢复5定理2.3([6,7])假定编码矩阵Φ满足2s阶RIP性质,且RIP常数δ2s≤√2−1.我们选择解码∆1.那么,对任意的x∈Σs,均有∆1(Φx)=x.上述定理表明,我们可用RIP矩阵编码、∆1解码精确恢复s-稀疏信号.然而,现实世界中的信号并非严格稀疏的,通常仅仅是近似稀疏.对于此类信号,如果我们仍然用RIP矩阵Φ进行编码,选则解码为∆1,那么我们能较好的恢复非稀疏信号吗?令人惊讶的是,我们仍然能较好的完成任务.为介绍这方面的结果,我们首先介绍最佳s-项逼近误差的概念.给定范数∥·∥X,那么信号x∈RN的在范数∥·∥X意义下最佳s-项逼近误差为σs(x)X:=minz∈Σs∥x−z∥X.对于K⊂RN,我们令σs(K)X:=maxx∈Kσs(x)X.下面定理指出,对于一般信号,我们采用RIP矩阵编码与用∆1作解码,那么恢复效果可用ℓ1范数意义下的最佳逼近误差刻画.定理2.4假定编码矩阵Φ满足2s阶RIP性质,且RIP常数δ2s≤√2−1.我们选择解码为∆1.那么对任意的x∈RN,我们有∥∆1(Φx)−x∥2≤C0σs(x)1√s,此处C0为一常数.注2.2定理2.3与定理2.4首先在[7]中被证明.但给出的RIP常数较为粗糙.在[6]中,E.Candes将RIP常数改进为δ2s≤√2−1.仍有一些论文考虑改进定理2.3中的RIP常数√2−1[4,21].特别是，Mo和Li将该常数改进为δ2s0.4931[30].此外,Davies和Gribonval建构一个例子表明,如果δ2s≥1√2,那么∆1解码不能恢复一些s-稀疏信号.注意到这些研究均是针对δ2s,也就是要求矩阵满足2s阶RIP条件.在[5]中,Cai,Wang和Xu考虑了矩阵满足s-阶RIP条件的情况,给出了P1能恢复s-稀疏信号的充分条件为δs0.307.此外,我们特别指出,借助离散几何中的多面体理论,在文[16]中,Donoho给出了∆1解码能精确恢复s-稀疏信号的充要条件.注2.3对于0p1,人们也考虑了如下定义的∆p解码:minx∈RN∥x∥ps.t.Φx=y.3RIP矩阵6这里∥x∥p:=(∑Nj=1|xj|p)1/p.事实上,当0p1,∥·∥p为一拟范数.相比于∆1解码,∆p解码所需观测次数较少,但解码复杂度会有所增加[39,13].注2.4在本文中,我们假定信号的稀疏性指非0元素较少.但是,很多应用问题里面,信号是在一“字典”或者紧框架表示下是稀疏的.对于此类情况,文[11]进行了研究.并将定理2.4进行了推广.但是,这个方向仍值得进一步深入探索.我们现在回到本文开始所提出的问题：如果选择解码为∆1,为精确恢复所有s-稀疏信号,观察次数n最少应为多少?文[22]给出了如下定理:定理2.5假定Φ∈Rn×N及解码为∆1.那么,如果∆1(Φx)=x,对任意x∈Σ2s,则n≥c1slog(Nc2s),这里c1=1log9t0.455且c2=4.根据上述定理,如果解码选择为∆1,那么我们至少需要进行n=O(slog(Ns))次观测,才能精确恢复s-稀疏信号.这个下界能够达到吗?也就是说,对于n=O(slog(Ns)),我们能否构造观测矩阵Φ∈Rn×N,使得对任意x∈Σs,均有∆1(Φx)=x?根据定理2.3,我们可将该问题归结为能否构造满足s-阶RIP条件的矩阵Φ∈Rn×N使得n=O(slog(Ns))?我们将在下节回答该问题.3RIP矩阵根据定理2.3和定理2.4,为保证ℓ1解码能恢复稀疏或者近似稀疏信号,我们需要构造RIP矩阵.我们希望对于给定的n,N∈Z,构造一n×N的矩阵Φ,以使其对尽量大的s满足s-阶RIP条件.那么,如何构造此类矩阵?当前的主要构造方法有：随机矩阵、结构随机矩阵与确定性矩阵.3RIP矩阵73.1随机矩阵我们考虑两类随机矩阵：Gaussian随机矩阵与Bernoulli随机矩阵.所谓Gaussian随机矩阵,即指矩阵中的元素ϕi,j是独立的随机变量且服从如下分布:ϕi,j∼N(0,1n)即服从期望为0,方差为1n的Gaussian分布.所谓Bernou