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

压缩感知理论与应用Compressedsensing:theoremandApplications一.压缩感知背景知识二.压缩感知理论三.压缩感知重建方法四.压缩感知应用内容概览一.压缩感知背景知识Nyquist-Shannon采样定理

1928年由美国电信工程师H.奈奎斯特首先提出 1933年由苏联工程师科捷利尼科夫首次用公式严

格地表述这一定理 1949年信息论的创始人香农对该定理加以明确

地说明并正式作为定理引用，因此在许多文

献中又称为香农采样定理HarryNyquist

ClaudeShannon

插值重建数字信号的获取----Nyquist-Shannon采样定理信号采样非带限信号香农定理的数学表示香农采样定理后采样理论的发展Nyquist-Shannon采样定理局限性问题1:真实信号没有真正带限的；问题2:理想的低通滤波器不存在；获取的大量数字信号为处理、存储、传输的软硬件增加了很多负担高分辨率大量的传感器图像数据库，照相阵列，分布式无线传感网越来越多的成像形式X-Ray，GammaRay,PET，MRI,红外，超声波，毫米波SAR成像海量的数据问题3:当信号的带宽过宽时，采样率过高难于实现

限制了超宽带通信和超宽带雷达的发展；限制医学图像成像的发展，比如MRI；等等。多种成像形式采样压缩传输/存储NK小波系数局部放大大量采样数据有无必要性？1M25K项系数近似原始图像近似后的图像2004~2006，

ECandes（加州理工大学）

D.Donoho(斯坦福大学)

（Ridgelet和Curvelet的创始人）

一种新的采样方法

以不确定准则为基础Romberg(佐治亚理工大学)

Tao（加州大学洛杉矶分校）CS提出者用更一般的测量值代替信号样本值压缩感知或压缩采样直接获取压缩后的信号；压缩采样传输/存储NM接收重建二.压缩感知理论2.1压缩感知问题描述

三种线性方程组根据变量个数和方程个数来确定是欠定、适定还是超定方程组欠定方程组，无穷多解适定方程组，有唯一解超定方程组，无解良态问题1923年Hadamard提出了良态问题（Well-posedproblem）的概念，根据其定义，如果下述条件满足，称为良态问题（1）方程的解是存在的；（2）解是唯一的；（3）解连续地依赖于数据（观测矩阵或数据微小变化导致解很大变动）病态问题

如果良态问题的三个条件任意一个不能满足，就称问题是病态的（ill-posedproblem）

良态与病态问题：病态问题举例系数矩阵A或者观测项(常数项)y的微小变化引起解的巨大变化,该问题为病态问题

病态问题求解：用规整化（Regularization）理论处理病态问题目的是修改一个病态问题为一个良态问题，使得问题的解在物理上合理，并且解连续依赖于数据。基本思想是利用关于解的先验知识，构造附加约束或改变求解策略，使得逆问题的解变得确定且稳定。即对解进行约束J(x)约束信号x为平滑的应用Lagrange乘子，将P2问题约束转换为无约束问题

2.如何设计测量矩阵，让其作用于信号后

能保持信号的所有信息不丢失？

（对应于香农采样定理中对采样率的要求）3.如何从测量中重建原信号？

（对应依据香农采样定理采样后内插实现重建）信号应满足什么要求，方可重建？（对应香农采样定理中对信号的带宽要求）CS关注的问题信号表示将信号表示为一组正交基的线性组合

如果合理选择基底，处理系数序列比直接处理信号简单；如果系数序列具有稀疏结构，可以从实质上降低信号处理的成本，提高压缩效率。二.压缩采样理论2.2信号的稀疏与可压缩性信号的稀疏（Sparsity）与可压缩性(Compressibility)光滑信号其Fourier变换,Wavelet变换系数呈现幂次衰减趋势其全变差（TotalVariation）呈现幂次衰减趋势有界变差函数

给定一个定义于有界开集Ω上的可微函数f，其全变差（thetotalvariation）

为对于图像x而言，其TV范数为Cameraman原图4层小波分解傅里叶幅频MRI图像4层小波分解傅里叶幅频原图垂直水平全变差

根据信号x的先验知识，可以设计规整化项为

R2空间，一维子空间用lp范数进行约束的解2.3.1不确定原理（测不准原理

UncertaintyPrinciple,UP）物理学中经典的测不准原理两个共轭的物理量，如微观粒子的位置和动量，不能同时测准，其中一个量越确定，另一个量的不确定程度就越大

2.3测量离散时间不确定准则（DiscreteTimeUncertaintyPrinciple）注：集的势：集合元素的个数2.3.2部分Fourier变换已知的信号重建与RobustUncertaintyPrinciplesCS提出的最初研究：2004年，EmmanuelCandes,JustinRomberg和TerenceTao对以下问题进行了研究MRI图像Fourier采样，22线Fourier幅度M>=logN.S定理与UP的关系，以及RUP（RobustUncertaintyPrinciple）2.3.3随机采样与重建

定义2.1互相干

互

定理2.3

几点说明：2.信号表示越稀疏、两组基之间的互相干性越小，所需

要的样本数就越少3.常用的测量矩阵有高斯和伯努利分布，因为其与

大多数的稀疏表示基相干性小。测量结果稀疏信号x随机投影（测量）矩阵压缩采样的情况1:信号本身稀疏

信号是时域稀疏的，频域测量结果含有信号的所有信息；信号测量原信号M=50；S=19；N=100重建信号时域信号频域1-维信号信号是频域稀疏的，时域测量结果；压缩采样的情况2信号可以用一组基稀疏表示2-维图像信号2.3.4一致不确定准则（UniformUncertainty

Principle,UUP）

严格重建准则（ExactReconstructionPrinciple,ERP）可压缩信号（近似稀疏信号）的重建（P1）

定理2.4保证信号不在测量的零空间，信号的范数近似保持定义2.3

定理2.5定理2.62.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问题的唯一解

称A有则A具有k阶零空间性质

MRI图像Fourier采样，22线令能量最小，未采样的Fourier系数置0CS重建，令图像的TV范数最小

利用计算机解决实际问题，通常要按以下步骤进行：（1）建立数学模型，即把实际问题抽象为一个数学问题，可以是一个方程组、一个函数、一个微分方程等。

（2）选择数值方法，要考虑所能达到的精度，计算量，方法对数据微小扰动的灵敏度。

（3）编写程序，上机计算。第二部分CS中的信号重建两类主要方法：一、贪婪搜索（MatchedPursuit,匹配追踪）二、基追踪（BasisPursuit，基追踪）

称为基追踪问题，（BasisPursuit，BP）匹配追踪（MatchedPursuit，MP）一、匹配追踪（MatchedPursuit，简称MP）MP算法的步骤正交匹配追踪（OrthogonalMatchedPursuit，简称OMP）

OMP算法步骤

t=t+1;5：如果

t>S,则停止迭代，否则重复步骤1体现正交思想由多元函数的微分学知，上式的解一定是驻点线性规划问题的标准形式s.t.其中为M×N阶矩阵

二、基追踪问题（BP）约束条件以及目标函数都是决策变量的线性函数的规划问题称为线性规划(LinearProgramming)s.t.

线性规划问题解的概念：

(1)可行解。满足约束条件的解

可行解集称为线性规划问题的可行域。

(2)最优解。使目标函数达到最优值的可行解称为最优解，最优解常用表示。

(3)基。若Ｂ是Ａ中M×M阶非奇异矩阵，即|Ｂ|≠0，则称Ｂ是线性规划问题的一个基。s.t.

基向量，基变量

若Ｂ是线性规划问题的一个基，那么Ｂ一定是由M个线性无关的列向量组成，不失一般性，可设

称为基向量，

与基向量相对应的变量称为基变量。

基的个数一个线性规划的基通常不是唯一的，但是基的个数也不会超过个。一旦线性规划的基确定了，那么相应的基向量、基变量和非基变量也就确定了。(4)基本解。设B是线性规划的一个基，若令n-m个非基变量等于0，则所得的方程组ＡＸ=b的解称为线性规划问题的一个基本解（简称基解）。有一个基就可以求得一个基本解。由基的有限性可知，基本解的个数也不会超过个。由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5)基本可行解。满足非负条件的基本解称为基本可行解（简称基可行解）。与基本可行解对应的基称为可行基。基本可行解的非零向量的个数小于等于m，并且都是非负的。由于基本可行解的数目一般少于基本解的数目，因此可行基的数目也要少于基的数目。

当基本可行解中有一个或多个基变量是取零值时，称此解为

退化的基本可行解。可行解

基本解求解线性规划：图解法单纯形法内点算法70单纯形法的一般步骤如下：（1）寻找一个初始的基本可行解。（2）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。（3）移至目标函数值有所改善的另一个基本可行解，然后转回到步骤（2）。

其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。

1947年，Dantzig提出的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。单纯形法Lasso问题

s.t.BPDN（BasisPursuitDenoising）BP（BasisPursuit）s.t.(1)约束问题(2)约束问题问题(2)的解要么是x=0,要么是问题(3)的解,因此说BPDN问题与LASSO等价(3)无约束问题3.1无约束最优化方法无约束问题定义：设函数f(x)存在一阶偏导数，x∈Rn

，向量Ñ)(xf=Tnxfxfxføöççè涶¶¶¶¶,,,21为f(x)在点x处的梯度。…定义设函数存在二阶偏导数，x∈R，则称矩阵)(xfnúúúúúúúúûùêêêêêêêêë鶶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶2222122222212212212212nnnnnxfxxfxxfxxfxfxxfxxfxxfxfLLL为在点x处的Hesse矩阵。)(xf)(2xfÑ=………三、BPDN问题定理:(一阶必要条件）

凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。设，若对D中任意两点，连接的线段仍属于D；换言之，对,

则称D为凸集。称为的凸组合。定义:凸集对凸的一元函数的几何意义为：在曲线上任取两点P1(x1,),P2(x2,)弦位于弧之上（见图）。)(xf)(1xf(x2)f21PP21PPx1x2x(x,y)p1p2)(xf设D为RN

中非空凸集，若对,

恒有则称f(x)为D上的凸函数；进一步，若时，上式仅〝<〞成立,则称f(x)为D上严格凸函数。定义:凸函数定义:凸规划设D为RN

中非空凸集，f(x)是定义在D上的凸函数，则称规划问题为凸规划。若规划ïîïíì===ljhmigtsfji,,2,1,0)(,,2,1,0)(..)(minxxx……中,和

为凸函数,是线性函数,则上述问题为凸规划。)(xf)(xig)(xih

凸规划是非线性规划中的一种重要特殊情形，它具有很好的性质。定理:(1)凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。

(2)如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。多数问题由条件得到的是一个非线性方程组，求解非常困难，甚至无法得到解析解，因此求解非线性规划问题一般都采用数值计算的迭代方法。即从已知点出发，按照某种算法产生后继点，形成点列非线性规划迭代方法的基本思想是：要求迭代所采用的算法，使得当是有穷点列时，其最后一点是该问题的最优解；当为无穷点列时，有极限点，并且该极限点是问题的最优解。

定理：设f：具有二阶连续偏导数。则：

Taylor展开式还可写成如下形式：

多元函数的Taylor展开公式其中算法的收敛性

如果算法构造出的点列{xk}在有限步之内得到问题的最优解x*

，或者点列{xk}有极限点，并且其极限点是最优解

x*

，则称这种算法是收敛的。

如果只有当

x0充分接近最优解

x*时，由算法产生的点列才收敛于

x*

，则该算法称为局部收敛。

如果对于任意初始点

x0

，由算法产生的点列都收敛于最优解

，则这个算法称为全局收敛。考虑问题式中函数具有一阶连续偏导数，具有极小点若现在已求得的第k次近似值，为求得第k+1次近似值，需要选定方向p将f(x)在xk处进行一阶泰勒展开，得到如果忽略高阶无穷小项，因为3.1.1最速下降法有说明搜索方向应该与梯度的点积小于0,因为说明夹角为180o时目标函数下降最快，称为负梯度方向

负梯度方向使目标函数

下降最快，又称之为最速下降方向。算法：最速下降法

在相继两次迭代中，搜索方向是相互正交的。可见，最速下降法逼近极小点的路线是锯齿形的，而且越靠近极小点步长越小，即越走越慢。

最速下降法具有整体收敛性，但由于其收敛速度慢，所以它不是好的实用算法。然而一些有效算法是通过对它进行改进或利用它与其他收敛快的算法相结合而得到的。是基本算法之一。3.1.2牛顿法(Newton)算法：牛顿法

牛顿法的优缺点3.1.3共轭梯度法(ConjugateGradient)1.共轭方向及其性质定理：设矩阵A为对称正定，求解方程组

的解等价于求二次泛函

f(x)

的极小点共轭梯度法的基本思想是

在共轭方向法和最速下降法之间建立某种联系，为了节省存储单元和计算量，在迭代过程中逐步形成共轭方向。即用迭代点处的负梯度向量为基础产生一组共轭方向的方法，叫做共轭梯度法。下面具体介绍对于正定二次函数规划问题的共轭梯度法

共轭梯度法特点是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。

CG是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便所需存储量小，稳定性高，而且不需要任何外来参数。用共轭梯度法求得的

有如下的误差估计其中PCG（PreconditionedConjugateGradient）

当矩阵A仅有少数几个互不相同的特征值或者非常良态时，共轭梯度法就会收敛的非常之快。当矩阵A是病态的，想办法将其转化为一个良态的等价方程组，然后再应用共轭梯度法于转化后的方程组其中，这里的C对阵正定，目的是通过选择C，使得是良态的，然后再应用CG算法考虑约束非线性规划问题

其中

，可行域记为，

，，是上的连续函数。

基本思想有，构造广义拉格朗日函数，惩罚范数使得约束问题转换为无约束问题；将非线性问题线性化，然后通过解线性规划问题求原问题的解等；3.2约束问题求解定义（1）式的广义拉格朗日函数为则存在向量，（此条件叫Kuhn-Tucker约束规范）3.2.1外点法构造一个由目标函数与约束函数组成的惩罚函数，对惩罚函数实行极小化。先考虑只含有不等式约束的问题：

s.t

构造一个函数：

将

作为t，显然当

时，

，

当

时，

构造函数：

求解无约束问题

若(5)式问题有解，设其最优解为，则由(3)式和(4)式应有：

这就是说

因此不仅是问题(5)式的极小解，也是问题(2)式的极小解。因此将问题(2)式的求解化为无约束问题(5)式的求解。

上述函数的函数性态不好，它在t=0点不连续，也没有导数。希望构造出一个在任意点t处函数及其导数都连续的辅助函数。可选择如下的函数：

函数(6)式在t为任意值时，与都连续，且当时仍有

当时为了使辅助函数能更快地满足要求，将引入一个充分大的正数M(>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(IterativeShrinkage-ThresholdingAlgorithm）1.考虑无约束的最小化连续可微函数f(x),解决这个问题的最简单方法就是用梯度算法产生x序列这个公式可以等价为如下二次形式把这种梯度算法应用到非光滑l1正则化问题中那么x的迭代序列为将公式(5)的第二项和第三项结合，并去掉常数项，则公式(5)可表示为

L1范数是可分离的那么(5)式的计算就简化为求解一维最小化问题，通过CHAMBOLLE,R.A.DEVORE等人的证明x迭代步骤可以写成如下形式收缩算子定义为如下形式确保x收敛的关键条件是步长的设置

2.一般问题的近似模型

对于任何L>0,F(x)=f(x)+g(x)在y点的二次近似模型为它的唯一最小解为与(5)式同理，忽略掉常数项的影响，可以表示为前面讲的g(x)为l1范数是这个一般问题的特例那么基本的ISTA步骤即为3.3.2