压缩感知理论与应用(附重建算法详述)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,压缩感知理论与应用,Compressed sensing:,theorem and Applications,一,.,压缩感知背景知识,二,.,压缩感知理论,三,.,压缩感知重建方法,四,.,压缩感知应用,内容概览,一,.,压缩感知背景知识,Nyquist-Shannon,采样定理,1928,年由美国电信工程师,H.,奈奎斯特首先提出,1933,年由苏联工程师科捷利尼科夫首次用公式严,格地表述这一定理,1949,年信息论的创始人香农对该定理加以明确,地说明并正式作为定理引用，因此在许多文,献中又称为香农采样定理,Harry Nyquist,Claude Shannon,插值重建,数字信号的获取,-Nyquist-Shannon,采样定理,信号采样,非带限信号,香农定理的数学表示,香农采样定理后采样理论的发展,Nyquist-,Shannon,采样定理局限性,问题,1:,真实信号没有真正带限的；,问题,2:,理想的低通滤波器不存在；,获取的大量数字信号为处理、存储、传输的软硬件增加了很多负担,高分辨率,大量的传感器,图像数据库，照相阵列，分布式无线传感网,越来越多的成像形式,X-Ray,，,Gamma Ray, PET,，,MRI,红外，超声波，毫米波,SAR,成像,海量的数据,问题,3:,当信号的带宽过宽时，采样率过高难于实现,限制了超宽带通信和超宽带雷达的发展；限制医学图像成像的发展，比如,MRI,；等等。,多种成像形式,采样,压缩,传输,/,存储,N,K,小波系数,局部放大,大量采样数据有无必要性？,1M,25K,项系数近似,原始图像,近似后的图像,20042006,，,E Candes,（,加州理工大学）,D.Donoho (,斯坦福大学,),（,Ridgelet,和,Curvelet,的创始人）,一种新的采样方法,以不确定准则为基础,Romberg (,佐治亚理工大学,),Tao,（,加州大学洛杉矶分校）,CS,提出者,用更一般的测量值代替信号样本值,压缩感知或压缩采样,直接获取压缩后的信号；,压缩,采样,传输,/,存储,N,M,接收,重建,二,.,压缩感知理论,2.1,压缩感知问题描述,三种线性方程组,根据变量个数和方程个数来确定是,欠定、适定,还是,超定,方程组,欠定方程组，无穷多解,适定方程组，有唯一解,超定方程组，无解,良态问题,1923,年,Hadamard,提出了良态问题（,Well-posed problem,）的,概念，根据其定义，如果下述条件满足，称为良态问题,（,1,）方程的解是存在的；,（,2,）解是唯一的；,（,3,）解连续地依赖于数据（观测矩阵或数据微小变化导致解很大变动）,病态问题,如果良态问题的三个条件任意一个不能满足，,就称问题是病态的（,ill-posed problem,）,良态与病态问题：,病态问题举例,系数矩阵,A,或者观测项,(,常数项,)y,的微小变化引起解的巨大变化,该问题为病态问题,病态问题求解：,用规整化（,Regularization,）理论处理病态问题,目的,是修改一个病态问题为一个良态问题，使得问题的解在物理上合理，并且解连续依赖于数据。,基本思想,是利用关于解的先验知识，构造附加约束或改变求解策略，使得逆问题的解变得确定且稳定。即对解进行约束,J(x),约束信号,x,为平滑的,应用,Lagrange,乘子，将,P,2,问题约束转换为无约束,问题,2.,如何设计测量矩阵，让其作用于信号后,能保持信号的所有信息不丢失？,（对应于香农采样定理中对采样率的要求）,3.,如何从测量中重建原信号？,（对应依据香农采样定理采样后内插实现重建）,信号应满足什么要求，方可重建？,（对应香农采样定理中对信号的带宽要求）,CS,关注的问题,信号表示,将信号表示为一组正交基的线性组合,如果合理选择基底，处理系数序列比直接处理信号简单；,如果系数序列 具有稀疏结构，可以从实质上降低信号处理的成本，提高压缩效率。,二,.,压缩采样理论,2.2,信号的稀疏与可压缩性,信号的稀疏（,Sparsity,）与可压缩性,(,Compressibility,),光滑信号,其,Fourier,变换,Wavelet,变换系数呈现幂次衰减趋势,其全变差（,Total Variation,）呈现幂次衰减趋势,有界变差函数,给定一个定义于有界开集,上的可微函数,f,，其全变差（,the total variation,）,为,对于图像,x,而言，其,TV,范数为,Cameraman,原图,4,层小波分解,傅里叶幅频,MRI,图像,4,层小波分解,傅里叶幅频,原图,垂直,水平,全变差,根据信号,x,的先验知识,，,可以设计规整化项为,R,2,空间，一维子空间用,lp,范数进行约束的解,2.3.1,不确定原理（测不准原理,Uncertainty Principle, UP,）,物理学中经典的测不准原理,两个共轭的物理量，如微观粒子的位置和动量，不能同时测准，,其中一个量越确定，另一个量的不确定程度就越大,2.3,测量,离散时间不确定准则,（,Discrete Time Uncertainty Principle,）,注：集的势：集合元素的个数,2.3.2,部分,Fourier,变换已知的信号重建与,Robust Uncertainty Principles,CS,提出的最初研究：,2004,年，,Emmanuel Candes, Justin Romberg,和,Terence Tao,对以下问题进行了研究,MRI,图像,Fourier,采样，,22,线,Fourier,幅度,M=logN.S,定理与,UP,的关系，以及,RUP,（,Robust Uncertainty Principle,）,2.3.3,随机采样与重建,定义,2.1,互相干,互,定理,2.3,几点说明,：,2,.,信号表示越稀疏,、,两组基之间的互相干性越小，所需,要的样本数就越少,3,.,常用的测量矩阵有高斯和伯努利分布，因为其与,大多数的稀疏表示基相干性小。,测量结果,稀疏信号,x,随机投影,（测量）矩阵,压缩采样的情况,1:,信号本身稀疏,信号是时域稀疏的，频域测量结果含有信号的所有信息,；,信号,测量,原信号,M=50,；,S=19,；,N=100,重建信号,时域信号,频域,1-,维信号,信号是频域稀疏的，时域测量结果,；,压缩采样的情况,2,信号可以用一组基稀疏表示,2-,维图像信号,2.3.4,一致不确定准则,（,Uniform Uncertainty Principle, UUP,）,严格重建准则（,Exact Reconstruction Principle, ERP,）,可压缩信号（近似稀疏信号）的重建,（,P,1,）,定理,2.4,保证信号不在测量的零空间，信号的范数近似保持,定义,2.3,定理,2.5,定理,2.6,2.3.6,鲁棒测量,定理,2.9,测量,A,的零空间,如果想从测量中重建所有的稀疏信号,x,，则对任意一对不同的信号,x,和,x,， 必然有,Ax,与,Ax,。如果来观测,A,x,=A,x,，则得到,x-x,是,2K,稀疏的， 因此，,A,能唯一表示所有 ，则 中不能含有 的向量。有许多方式可以表征这种性质，其中之一为,A,的,Spark,定义,Spark,：一给定矩阵,A,的,Spark,是其最少的线性相关列的个数。,2.3.7,最小化问题的唯一解,P,0,问题的唯一解,P,1,问题的唯一解,称,A,有,则,A,具有,k,阶零空间性质,MRI,图像,Fourier,采样，,22,线,令能量最小 ，未采样的,Fourier,系数置,0,CS,重建，令图像的,TV,范数最小,利用计算机解决实际问题，通常要按以下步骤进行：,（,1,）建立数学模型，即把实际问题抽象为一个数学问题，可以是一个方程组 、一个函数、一个微分方程等。,（,2,）选择数值方法，要考虑所能达到的精度，计算量，方法对数据微小扰动的灵敏度。,（,3,）编写程序，上机计算。,第二部分,CS,中的信号重建,两类主要方法：,一、贪婪搜索 （,Matched Pursuit,匹配追踪）,二、基追踪 （,Basis Pursuit,， 基追踪）,称为基追踪问题，（,Basis Pursuit,，,BP,）,匹配追踪（,Matched Pursuit,，,MP,）,一、匹配追踪（,Matched Pursuit,，简称,MP,）,MP,算法的步骤,正交匹配追踪（,Orthogonal,Matched Pursuit,，简称,OMP,）,OMP,算法步骤,t,=,t,+1;,5,：如果,t,S,则停止迭代，否则重复步骤,1,体现正交思想,由多元函数的微分学知，上式的解一定是驻点,线性规划问题的标准形式,s.t.,其中 为,M,N,阶矩阵,二、基追踪问题（,BP,）,约束条件以及目标,函数都是决策变量,的线性函数的规划,问题称为,线性规划,(Linear Programming),s.t.,线性规划问题解的概念：,(1),可行解,。满足约束条件的解,可行解集称为线性规划问题的可行域。,(2),最优解,。使目标函数达到最优值的可行解称为最优解，,最优解常用 表示。,(3),基,。若是中,MM,阶非奇异矩阵，即,|,|0,，则称是线性规,划问题的一个基。,s.t.,基向量，基变量,若是线性规划问题的一个基，那么一定是由,M,个线性无关的列向量组成，不失一般性，可设,称 为,基向量,，,与基向量相对应的变量称为,基变量,。,基的个数,一个线性规划的基通常不是唯一的，但是,基的个数,也不会超过 个。一旦线性规划的基确定了，那么相应的基向量、基变量和非基变量也就确定了。,(,4),基本解,。设,B,是线性规划的一个基，若令,n-m,个非基变量等于,0,，则,所得的方程组,=b,的解称为线性规划问题的一个基本解（简称基解）。,有一个基就可以求得一个基本解。,由基的有限性可知，基本解的个数也不会超过 个。,由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。,(5),基本可行解,。满足非负条件的基本解称为基本可行解,（简称基可行解）。,与基本可行解对应的基称为,可行基,。,基本可行解的非零向量的个数小于等于,m,，并且都是非负的。,由于基本可行解的数目一般少于基本解的数目，因此可行基,的数目也要少于基的数目。,当基本可行解中有一个或多个基变量是取零值时，称此解为,退化的基本可行解,。,可行解,基本解,求解线性规划：,图解法,单纯形法,内点算法,单纯形法的一般步骤如下：,（,1,）寻找一个,初始的基本可行解,。,（,2,）检查现行的基本可行解是否,最优,，如果为最优，则停止迭代，已找到最优解，否则转一步。,（,3,）移至目标函数值有所改善的,另一个基本可行解,，然后转回到步骤（,2,）。,其,基本思路,是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。,1947,年，,Dantzig,提出的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。,单纯形法,70,Lasso,问题,s.t.,BPDN,（,Basis Pursuit Denoising,）,BP,（,Basis Pursuit,）,s.t.,(1),约束问题,(2),约束问题,问题,(2),的解要么是,x=0,要么是问题,(3),的解,因此说,BPDN,问题与,LASSO,等价,(3),无约束问题,3.1,无约束最优化方法,无约束问题,定义,：设函数,f,(,x,),存在一阶偏导数，,x,R,n,，向量,),(,x,f,=,T,n,x,f,x,f,x,f,2,1,为,f,(,x,),在点,x,处的梯度。,定义,设函数 存在二阶偏导数，,x,R,，则称矩阵,),(,x,f,n,2,2,2,2,1,2,2,2,2,2,2,1,2,2,1,2,2,1,2,2,1,2,n,n,n,n,n,x,f,x,x,f,x,x,f,x,x,f,x,f,x,x,f,x,x,f,x,x,f,x,f,L,L,L,为 在点,x,处的,Hesse,矩阵。,),(,x,f,),(,2,x,f,=,三、,BPDN,问题,定理,: (,一阶必要条件,）,凸集,和,凸函数,在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。,设 ，若对,D,中任意两点 ，连接,的线段仍属于,D,；换言之，对,则称,D,为,凸集,。 称为 的,凸组合,。,定义,:,凸集,对凸的一元函数 的几何意义为：在曲线上任取两点,P,1,(,x,1, ),P,2(,x,2, ),弦 位于弧 之上（见图）。,),(,x,f,),(,1,x,f,(x,2,),f,2,1,P,P,2,1,P,P,x,1,x,2,x,(,x,y,),p,1,p,2,),(,x,f,设,D,为,R,N,中非空凸集，若对,恒有,则称,f,(x),为,D,上的,凸函数,；进一步，若 时，上式仅,0),，修改 为,求解问题,(5),式就变为求解无约束问题,(8),式,称函数 为惩罚函数（或罚函数），其中第二项 为惩罚项。称,M,为罚因子。,惩罚函数只对不满足约束条件的点实行惩罚。当,时，满足各个 ，故罚项等于,0,，不受惩罚；当 时，必有 ，故罚项,0,，对极小化罚函数的问题，就要受惩罚。,在实际计算中，罚因子,M,的值选得过小或过大都不好。如果选得过小，则罚函数的极小点远离约束问题的最优解，计算效率很差；如果,M,过大，则给罚函数的极小化增加计算上的困难。因此，一般策略是取一个趋向无穷大的严格递增正数列 ，从某个,开始，对每个 求解：,当 趋向于正无穷大时，点列 就从可行域外部趋于原问题的极小点，“外点法”正是因此而得名,第,1,步：给定初始点 ，初始罚因子 （例如 ），放大系数 （如取 或,10,），允许误差 。令,。,第,2,步：求解罚函数 的无约束极小化问题。,以 为初始点，选择适当的方法求解 ，得其极小点 。,第,3,步：判断精度。,在 点，若罚项 ，则停止计算，得到原问题的近似极小点 ；否则令 ，置,，返回第,2,步。,外点法,考虑非线性规划,s.t,记,为可行域内部。即 是可行域 中所有严格内点（即不包括可行域边界上的点）的集合。,3.2.2,内点法,与外点法不同，内点法要求整个迭代过程始终在,可行域内部,进行，初始点是一个严格的内点，再在可行域边界上设置一道,“障碍”,，以阻止搜索点到可行域边界上去。,构造,障碍函数,（取倒数或对数函数）：,或,其中 是很小的正数，通常称为障碍因子，称,或 为障碍项。,障碍函数应具备的功能：可行域内部或离边界较远处，障碍函数与,原目标函数尽可能接近,，而在,边界上时，应变成很大的值,，因此满足该要求的障碍函数其极小值不会在可行域的边界上达到。,内点法计算步骤,第,1,步：给定严格内点 为初始点，初始障碍因子 （如取 ），缩小系数 （如取 或,0.2,），允许误差 ，置,。,第,2,步：构造障碍函数 ，障碍函数可取,(14),式形式，也可取,(15),式形式。,第,3,步：求解障碍函数 的无约束极小化问题。,以 为初始点，求解,得其极小点 。 是可行域中所有严格内点的集合。,第,4,步：判断精度。,若收敛准则得到满足，则迭代停止，取 作为原问题极小点 的近似值。否则取 ，置 ，转第,3,步。,内点法的优缺点,优点：由于迭代总是在可行域内进行，每一个中间结果都是可行解，可以作为近似解。,缺点：选取初始可行点较困难，且只适用于含有不等式约束的非线性规划问题。,3.3,其他算法,3.3.1,ISTA(Iterative Shrinkage-Thresholding Algorithm,）,1.,考虑无约束的最小化连续可微函数,f(x),解决这个问题的最简单方法就是用梯度算法产生,x,序列,这个公式可以等价为如下二次形式,把这种梯度算法应用到非光滑,l1,正则化问题中,那么,x,的迭代序列为,将公式,(5),的第二项和第三项结合，并去掉常数项，则公式,(5),可表示为,L,1,范数是可分离的那么,(5),式的计算就简化为求解一维最小化问题，通过,CHAMBOLLE,R.A.DEVORE,等人的证明,x,迭代步骤可以写成如下形式,收缩算子定义为如下形式,确保,x,收敛的关键条件是步长的设置,2.,一般问题的近似模型,对于任何,L0,F(x)=f(x)+g(x),在,y,点的二次近似模型为,它的唯一最小解为,与,(5),式同理，忽略掉常数项的影响，可以表示为,前面讲的,g(x),为,l1,范数是这个一般问题的特例,那么基本的,ISTA,步骤即为,3.3.2,FISTA,算法,FISTA,与,ISTA,的主要区别就是收缩算子：,ISTA,作用于前一步迭代值，,FISTA,作用于前两步迭代值的混合,经证明,ISTA,的收敛率为,FISTA,的收敛率为,3.3.3 FCSA,(,F,ast,C,omposite,S,plitting,A,lgorithm),FCSA,基于变量可分离和算子可分离技术，将复杂的复合正则化问题分解为两个简单的子问题并行求解，然后对子问题的最优解进行加权平均，经过若干次迭代重建出目标图像。,FCSA,计算复杂度低，每次迭代中的复杂度边界为,O,(,N,log,N,),，其中,N,为待重建图像的像素个数。,FCSA,还具有收敛速度快等优点，将其应用于,MR,图像重建可加速成像速度，提高重建精度。,求解过程,大致可分为三个步骤：,首先，利用变量分离技术将,x,分离为两个变量,x,1,和,x,2,；,然后，利用算子分离技术将复合最优化问题分解为,x,1,的,TV,正则化子问题，以及,x,2,的,l,1,范数最小化子问题分别进行求解；,最后，对两个子问题的最优解进行加权平均。,变量分离,算子分离,加权平均,计算复杂度低，收敛速度快,快速合成分离算法（,Fast Composite Splitting Algorithm,，简称,FCSA,）,借鉴,FISTA,，快速收敛,HALF-QUADRATIC MINIMIZATION METHODS,目标函数由数据保真项和规整化项组成,图像去噪、去模糊和很多逆问题中（如地震映像、,X-,射线断层成像）常使用数据保真项，而规整化项是,其中,g,（,x,）是一阶或者二阶差分算子,由于代价函数中包括边缘保持的规整化项，对于数据,y,成非线性，而且当,A,是为病态矩阵时，最小化问题很难求解，因此引入,half-quadratic,方法。,如果,A,T,A,是可逆的，或 则目标函数有唯一最小解,为解决该问题，,HQ,方法重新构造新的目标函数,这里新增加了辅助变量,b,其中 是二次函数；,满足,因此有,由于引进的的规整项是半二次，因此得名,一种是乘性的,一种是加性的,HQ,规整化用于简化 为 非凸函数，并且,A,有很多非零元素时的最小化问题的求解。,采用交替最小化函数的方法,具体的,对任意的 ， 选择为,则第,k,次的解为,若第,k,-1,次的解为 ，,对任意 ，向量 使得,根据以上公式，可知,因此，序列,当 收敛。特别的,对于乘性的形式，对偶函数,则,将上式带入目标函数，有,对任意的 ， 选择为,对于乘性形式，有,当,b,选定后，,x,就是选择使得,由,可得,其中,从而,