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

《压缩感知理论与应用(附重建算法详述)资料课件.ppt》由会员分享，可在线阅读，更多相关《压缩感知理论与应用(附重建算法详述)资料课件.ppt（166页珍藏版）》请在三一办公上搜索。

1、,压缩感知理论与应用,Compressed sensing:theorem and Applications,一.压缩感知背景知识,二.压缩感知理论,三.压缩感知重建方法,四.压缩感知应用,内容概览,一.压缩感知背景知识,Nyquist-Shannon采样定理,1928年由美国电信工程师H.奈奎斯特首先提出,1933年由苏联工程师科捷利尼科夫首次用公式严 格地表述这一定理1949 年信息论的创始人香农对该定理加以明确 地说明并正式作为定理引用，因此在许多文 献中又称为香农采样定理,Harry Nyquist,Claude Shannon,插值重建,数字信号的获取-Nyquist-Shannon

2、采样定理,信号采样,非带限信号,香农定理的数学表示,香农采样定理后采样理论的发展,Nyquist-Shannon采样定理局限性,问题1:真实信号没有真正带限的；问题2:理想的低通滤波器不存在；,获取的大量数字信号为处理、存储、传输的软硬件增加了很多负担,高分辨率,海量的数据,问题3:当信号的带宽过宽时，采样率过高难于实现,限制了超宽带通信和超宽带雷达的发展；限制医学图像成像的发展，比如MRI；等等。,多种成像形式,采样,压缩,传输/存储,N,K,小波系数,局部放大,大量采样数据有无必要性？,1M,25K 项系数近似,20042006，E Candes（加州理工大学）D.Donoho(斯坦福大学

3、)（Ridgelet和Curvelet的创始人）,一种新的采样方法 以不确定准则为基础,Romberg(佐治亚理工大学)Tao（加州大学洛杉矶分校）,CS提出者,用更一般的测量值代替信号样本值,压缩感知或压缩采样,直接获取压缩后的信号；,二.压缩感知理论,2.1 压缩感知问题描述,三种线性方程组,根据变量个数和方程个数来确定是欠定、适定还是超定方程组,欠定方程组，无穷多解,适定方程组，有唯一解,超定方程组，无解,良态问题,1923年Hadamard提出了良态问题（Well-posed problem）的概念，根据其定义，如果下述条件满足，称为良态问题（1）方程的解是存在的；（2）解是唯一的；（

4、3）解连续地依赖于数据（观测矩阵或数据微小变化导致解很大变动）,病态问题,如果良态问题的三个条件任意一个不能满足，就称问题是病态的（ill-posed problem）,良态与病态问题：,病态问题举例,系数矩阵A或者观测项(常数项)y的微小变化引起解的巨大变化,该问题为病态问题,病态问题求解：用规整化（Regularization）理论处理病态问题,目的是修改一个病态问题为一个良态问题，使得问题的解在物理上合理，并且解连续依赖于数据。,基本思想是利用关于解的先验知识，构造附加约束或改变求解策略，使得逆问题的解变得确定且稳定。即对解进行约束J(x),约束信号x为平滑的,应用Lagrange乘子，

5、将P2问题约束转换为无约束问题,2.如何设计测量矩阵，让其作用于信号后 能保持信号的所有信息不丢失？（对应于香农采样定理中对采样率的要求）,3.如何从测量中重建原信号？（对应依据香农采样定理采样后内插实现重建）,信号应满足什么要求，方可重建？（对应香农采样定理中对信号的带宽要求）,CS关注的问题,信号表示,将信号表示为一组正交基的线性组合,如果合理选择基底，处理系数序列比直接处理信号简单；如果系数序列 具有稀疏结构，可以从实质上降低信号处理的成本，提高压缩效率。,二.压缩采样理论,2.2 信号的稀疏与可压缩性,信号的稀疏（Sparsity）与可压缩性(Compressibility),光滑信号

6、,其Fourier变换,Wavelet变换系数呈现幂次衰减趋势,其全变差（Total Variation）呈现幂次衰减趋势,有界变差函数,Cameraman 原图,4层小波分解,傅里叶幅频,MRI图像,4层小波分解,傅里叶幅频,原图,垂直,水平,全变差,根据信号 x 的先验知识，可以设计规整化项为,R2空间，一维子空间用lp范数进行约束的解,2.3.1不确定原理（测不准原理 Uncertainty Principle,UP）,物理学中经典的测不准原理两个共轭的物理量，如微观粒子的位置和动量，不能同时测准，其中一个量越确定，另一个量的不确定程度就越大,2.3 测量,注：集的势：集合元素的个数,2

7、.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.常用的测量矩阵有高斯和伯努利分布，

8、因为其与 大多数的稀疏表示基相干性小。,测量结果,稀疏信号x,随机投影（测量）矩阵,压缩采样的情况1:信号本身稀疏,信号是时域稀疏的，频域测量结果含有信号的所有信息；,信号,测量,原信号,M=50；S=19；N=100,重建信号,时域信号,频域,1-维信号,信号是频域稀疏的，时域测量结果；,压缩采样的情况2信号可以用一组基稀疏表示,2-维图像信号,2.3.4 一致不确定准则（Uniform Uncertainty Principle,UUP）,严格重建准则（Exact Reconstruction Principle,ERP）,可压缩信号（近似稀疏信号）的重建,（P1）,定理2.4,保证信号不

9、在测量的零空间，信号的范数近似保持,定义 2.3,定理2.5,定理2.6,2.3.6 鲁棒测量,定理2.9,测量A的零空间,如果想从测量中重建所有的稀疏信号x，则对任意一对不同的信号x和x，必然有Ax与Ax。如果来观测Ax=Ax，则得到x-x是2K稀疏的，因此，A能唯一表示所有，则 中不能含有 的向量。有许多方式可以表征这种性质，其中之一为A的Spark,定义Spark：一给定矩阵A的Spark是其最少的线性相关列的个数。,2.3.7 最小化问题的唯一解,P0 问题的唯一解,P1 问题的唯一解,MRI图像,Fourier 采样，22线,令能量最小，未采样的Fourier系数置0,CS重建，令图

10、像的TV范数最小,利用计算机解决实际问题，通常要按以下步骤进行：（1）建立数学模型，即把实际问题抽象为一个数学问题，可以是一个方程组、一个函数、一个微分方程等。,（2）选择数值方法，要考虑所能达到的精度，计算量，方法对数据微小扰动的灵敏度。,（3）编写程序，上机计算。,第二部分 CS中的信号重建,两类主要方法：一、贪婪搜索（Matched Pursuit,匹配追踪）二、基追踪（Basis Pursuit，基追踪）,称为基追踪问题，（Basis Pursuit，BP）,匹配追踪（Matched Pursuit，MP）,一、匹配追踪（Matched Pursuit，简称MP）,MP算法的步骤,正交

11、匹配追踪（Orthogonal Matched Pursuit，简称OMP）,OMP算法步骤,t=t+1;,5：如果 tS,则停止迭代，否则重复步骤1,体现正交思想,由多元函数的微分学知，上式的解一定是驻点,线性规划问题的标准形式,s.t.其中 为MN阶矩阵,二、基追踪问题（BP）,约束条件以及目标函数都是决策变量的线性函数的规划问题称为线性规划(Linear Programming),s.t.,线性规划问题解的概念：(1)可行解。满足约束条件的解可行解集称为线性规划问题的可行域。(2)最优解。使目标函数达到最优值的可行解称为最优解，最优解常用 表示。(3)基。若是中MM阶非奇异矩阵，即|0，

12、则称是线性规划问题的一个基。,s.t.,基向量，基变量 若是线性规划问题的一个基，那么一定是由M个线性无关的列向量组成，不失一般性，可设 称 为基向量，与基向量相对应的变量称为基变量。基的个数 一个线性规划的基通常不是唯一的，但是基的个数也不会超过 个。一旦线性规划的基确定了，那么相应的基向量、基变量和非基变量也就确定了。,(4)基本解。设B是线性规划的一个基，若令n-m个非基变量等于0，则所得的方程组=b的解称为线性规划问题的一个基本解（简称基解）。有一个基就可以求得一个基本解。由基的有限性可知，基本解的个数也不会超过 个。由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5)基

13、本可行解。满足非负条件的基本解称为基本可行解（简称基可行解）。与基本可行解对应的基称为可行基。基本可行解的非零向量的个数小于等于m，并且都是非负的。由于基本可行解的数目一般少于基本解的数目，因此可行基 的数目也要少于基的数目。当基本可行解中有一个或多个基变量是取零值时，称此解为 退化的基本可行解。,求解线性规划：图解法单纯形法内点算法,70,单纯形法的一般步骤如下：（1）寻找一个初始的基本可行解。（2）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。（3）移至目标函数值有所改善的另一个基本可行解，然后转回到步骤（2）。,其基本思路是从一个初始的基本可行解出发，寻

14、找一条达到最优基本可行解的最佳途径。,1947年，Dantzig提出的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。,单纯形法,s.t.,BPDN（Basis Pursuit Denoising）,BP（Basis Pursuit）,s.t.,(1)约束问题,(2)约束问题,问题(2)的解要么是x=0,要么是问题(3)的解,因此说BPDN问题与LASSO等价,(3)无约束问题,3.1无约束最优化方法,无约束问题,三、BPDN 问题,定理:(一阶必要条件）,凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。,定义:凸集,定义:凸函数,定义:凸规划 设

15、D为RN 中非空凸集，f(x)是定义在D上的凸函数，则称规划问题 为凸规划。,凸规划是非线性规划中的一种重要特殊情形，它具有很好的性质。,定理:(1)凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。(2)如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。,多数问题由条件 得到的是一个非线性方程组，求解非常困难，甚至无法得到解析解，因此求解非线性规划问题一般都采用数值计算的迭代方法。即从已知点出发，按照某种算法产生后继点，形成点列,非线性规划迭代方法的基本思想是：要求迭代所采用的算法，使得当 是有穷点列时，其最后一点是该问题的最优解；当 为无穷点列时，有极限点，并

16、且该极限点是问题的最优解。,定理：设 f：具有二阶连续偏导数。则：,Taylor展开式还可写成如下形式：,多元函数的Taylor展开公式,其中,算法的收敛性,如果算法构造出的点列 xk在有限步之内得到问题的最优解x*，或者点列 xk有极限点，并且其极限点是最优解 x*，则称这种算法是收敛的。,如果只有当 x0充分接近最优解 x*时，由算法产生的点列才收敛于 x*，则该算法称为局部收敛。,如果对于任意初始点 x0，由算法产生的点列都收敛于最优解，则这个算法称为全局收敛。,考虑问题,式中函数具有一阶连续偏导数，具有极小点,若现在已求得 的第k次近似值，为求得第k+1次近似值，需要选定方向 p,将f

17、(x)在xk处进行一阶泰勒展开，得到,如果忽略高阶无穷小项，,因为,3.1.1 最速下降法,有,说明搜索方向应该与梯度的点积小于0,因为,说明夹角为180o时目标函数下降最快，称为负梯度方向,负梯度方向使目标函数 下降最快，又称之为最速下降方向。,算法：最速下降法,在相继两次迭代中，搜索方向是相互正交的。可见，最速下降法逼近极小点的路线是锯齿形的，而且越靠近极小点步长越小，即越走越慢。,最速下降法具有整体收敛性，但由于其收敛速度慢，所以它不是好的实用算法。然而一些有效算法是通过对它进行改进或利用它与其他收敛快的算法相结合而得到的。是基本算法之一。,3.1.2 牛顿法(Newton),算法：牛顿

18、法,牛顿法的优缺点,3.1.3 共轭梯度法(Conjugate Gradient),1.共轭方向及其性质,定理：设矩阵A为对称正定，求解方程组 的解等价于求二次泛函 f(x)的极小点,共轭梯度法的基本思想是 在共轭方向法和最速下降法之间建立某种联系，为了节省存储单元和计算量，在迭代过程中逐步形成共轭方向。即用迭代点处的负梯度向量为基础产生一组共轭方向的方法，叫做共轭梯度法。下面具体介绍对于正定二次函数规划问题的共轭梯度法,共轭梯度法特点,是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯

19、度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。,CG是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便所需存储量小，稳定性高，而且不需要任何外来参数。,用共轭梯度法求得的 有如下的误差估计,其中,PCG（Preconditioned Conjugate Gradient）,当矩阵A仅有少数几个互不相同的特征值或者非常良态时，共轭梯度法就会收敛的非常之快。当矩阵A是病态的，想办法将其转化为一个良态的等价方程组，然后再应用共

20、轭梯度法于转化后的方程组,其中，这里的C对阵正定，目的是通过选择C，使得 是良态的，然后再应用CG算法,考虑约束非线性规划问题 其中，可行域记为，是 上的连续函数。,基本思想有，构造广义拉格朗日函数，惩罚范数使得约束问题转换为无约束问题；将非线性问题线性化，然后通过解线性规划问题求原问题的解等；,3.2约束问题求解,定义（1）式的广义拉格朗日函数为,则存在向量，,（此条件叫Kuhn-Tucker约束规范）,3.2.1 外点法,构造一个由目标函数与约束函数组成的惩罚函数，对惩罚函数实行极小化。先考虑只含有不等式约束的问题：s.t 构造一个函数：,将 作为t，显然当 时，当 时，构造函数：,求解无

21、约束问题 若(5)式问题有解，设其最优解为，则由(3)式和(4)式应有：这就是说 因此 不仅是问题(5)式的极小解，也是问题(2)式的极小解。因此将问题(2)式的求解化为无约束问题(5)式的求解。,上述函数 的函数性态不好，它在t=0点不连续，也没有导数。希望构造出一个在任意点t处函数及其导数都连续的辅助函数。可选择如下的函数：函数(6)式在t为任意值时，与 都连续，且当 时仍有,当 时 为了使辅助函数能更快地满足要求，将引入一个充分大的正数M(0)，修改 为,求解问题(5)式就变为求解无约束问题(8)式,称函数 为惩罚函数（或罚函数），其中第二项 为惩罚项。称M为罚因子。惩罚函数只对不满足约

22、束条件的点实行惩罚。当 时，满足各个，故罚项等于0，不受惩罚；当 时，必有，故罚项0，对极小化罚函数的问题，就要受惩罚。,在实际计算中，罚因子M的值选得过小或过大都不好。如果选得过小，则罚函数的极小点远离约束问题的最优解，计算效率很差；如果M过大，则给罚函数的极小化增加计算上的困难。因此，一般策略是取一个趋向无穷大的严格递增正数列，从某个 开始，对每个 求解：,当 趋向于正无穷大时，点列 就从可行域外部趋于原问题的极小点，“外点法”正是因此而得名,第1步：给定初始点，初始罚因子（例如），放大系数（如取 或10），允许误差。令。第2步：求解罚函数 的无约束极小化问题。以 为初始点，选择适当的方法

23、求解，得其极小点。第3步：判断精度。在 点，若罚项，则停止计算，得到原问题的近似极小点；否则令，置，返回第2步。,外点法,考虑非线性规划 s.t 记 为可行域内部。即 是可行域 中所有严格内点（即不包括可行域边界上的点）的集合。,3.2.2 内点法,与外点法不同，内点法要求整个迭代过程始终在可行域内部进行，初始点是一个严格的内点，再在可行域边界上设置一道“障碍”，以阻止搜索点到可行域边界上去。,构造障碍函数（取倒数或对数函数）：或 其中 是很小的正数，通常称为障碍因子，称 或 为障碍项。,障碍函数应具备的功能：可行域内部或离边界较远处，障碍函数与原目标函数尽可能接近，而在边界上时，应变成很大的

24、值，因此满足该要求的障碍函数其极小值不会在可行域的边界上达到。,内点法计算步骤,第1步：给定严格内点 为初始点，初始障碍因子（如取），缩小系数（如取 或0.2），允许误差，置。第2步：构造障碍函数，障碍函数可取(14)式形式，也可取(15)式形式。第3步：求解障碍函数 的无约束极小化问题。以 为初始点，求解 得其极小点。是可行域中所有严格内点的集合。第4步：判断精度。若收敛准则得到满足，则迭代停止，取 作为原问题极小点 的近似值。否则取，置，转第3步。,内点法的优缺点,优点：由于迭代总是在可行域内进行，每一个中间结果都是可行解，可以作为近似解。缺点：选取初始可行点较困难，且只适用于含有不等式约

25、束的非线性规划问题。,3.3 其他算法3.3.1 ISTA(Iterative Shrinkage-Thresholding Algorithm）,1.考虑无约束的最小化连续可微函数f(x),解决这个问题的最简单方法就是用梯度算法产生x序列这个公式可以等价为如下二次形式把这种梯度算法应用到非光滑l1正则化问题中那么x的迭代序列为,将公式(5)的第二项和第三项结合，并去掉常数项，则公式(5)可表示为 L1范数是可分离的那么(5)式的计算就简化为求解一维最小化问题，通过CHAMBOLLE,R.A.DEVORE等人的证明x迭代步骤可以写成如下形式 收缩算子定义为如下形式 确保x收敛的关键条件是步长的

26、设置,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(Fast Composite Splitting Algorithm),FCSA基于变量可分离和算子可分离技术，将复杂的复合正则化问题分解为两个简单的子问题并行求

27、解，然后对子问题的最优解进行加权平均，经过若干次迭代重建出目标图像。FCSA计算复杂度低，每次迭代中的复杂度边界为O(NlogN)，其中N为待重建图像的像素个数。FCSA还具有收敛速度快等优点，将其应用于MR图像重建可加速成像速度，提高重建精度。,求解过程大致可分为三个步骤：首先，利用变量分离技术将x分离为两个变量x1和x2；然后，利用算子分离技术将复合最优化问题分解为x1的TV正则化子问题，以及x2的l1范数最小化子问题分别进行求解；最后，对两个子问题的最优解进行加权平均。,变量分离,算子分离,加权平均,计算复杂度低，收敛速度快,快速合成分离算法（Fast Composite Splitti

28、ng Algorithm，简称FCSA）,借鉴FISTA，快速收敛,HALF-QUADRATIC MINIMIZATION METHODS,目标函数由数据保真项和规整化项组成,图像去噪、去模糊和很多逆问题中（如地震映像、X-射线断层成像）常使用数据保真项，而规整化项是,其中g（x）是一阶或者二阶差分算子,由于代价函数中包括边缘保持的规整化项，对于数据y成非线性，而且当A是为病态矩阵时，最小化问题很难求解，因此引入half-quadratic方法。,如果ATA是可逆的，或 则目标函数有唯一最小解,为解决该问题，HQ 方法重新构造新的目标函数,这里新增加了辅助变量b,因此有,由于引进的的规整项是半

29、二次，因此得名,一种是乘性的,一种是加性的,HQ规整化用于简化 为 非凸函数，并且A有很多非零元素时的最小化问题的求解。,采用交替最小化函数的方法,具体的,对任意的，选择为,对任意，向量 使得,根据以上公式，可知,因此，序列,当 收敛。特别的,对于乘性的形式，对偶函数,则,将上式带入目标函数，有,对任意的，选择为,对于乘性形式，有,当b选定后，x就是选择使得,由,可得,其中,从而,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,