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

1、压缩感知理论与应用压缩感知理论与应用Compressed sensing: theorem and Applications一一. .压缩感知背景知识压缩感知背景知识二二. .压缩感知理论压缩感知理论三三. .压缩感知重建方法压缩感知重建方法四四. .压缩感知应用压缩感知应用内容概览内容概览一一. . 压缩感知背景知识压缩感知背景知识Nyquist-ShannonNyquist-Shannon采样定理采样定理1928年由美国电信工程师年由美国电信工程师H.奈奎斯特首先提出奈奎斯特首先提出1933年由苏联工程师科捷利尼科夫首次用公式严年由苏联工程师科捷利尼科夫首次用公式严 格地表述这一定理格地表

2、述这一定理1949 年信息论的创始人香农对该定理加以明确年信息论的创始人香农对该定理加以明确 地说明并正式作为定理引用，因此在许多文地说明并正式作为定理引用，因此在许多文 献中又称为香农采样定理献中又称为香农采样定理Harry Nyquist Claude Shannon 插值重建插值重建数字信号的获取数字信号的获取-Nyquist-Shannon-Nyquist-Shannon采样定理采样定理信号采样信号采样非带限信号非带限信号香农定理的数学表示香农定理的数学表示香农采样定理后采样理论的发展香农采样定理后采样理论的发展Nyquist-Nyquist-Shannon采样定理局限性采样定理局限性

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

4、于实现 限制了超宽带通信和超宽带雷达的发展；限制医学图限制了超宽带通信和超宽带雷达的发展；限制医学图像成像的发展，比如像成像的发展，比如MRI；等等。；等等。多种成像形式多种成像形式采样采样压缩压缩传输传输/存储存储NKx小波系数小波系数局部放大局部放大大量采样数据有无必要性？大量采样数据有无必要性？1M 25K 项系数近似项系数近似原始图像原始图像 近似后的图像近似后的图像20042006， E Candes（加州理工大学）加州理工大学） D.Donoho (斯坦福大学斯坦福大学) （ Ridgelet和Curvelet的创始人） 一种新的采样方法一种新的采样方法 以不确定准则为基础以不确定

5、准则为基础Romberg (佐治亚理工大学佐治亚理工大学) Tao （加州大学洛杉矶分校）加州大学洛杉矶分校）CS提出者提出者用更一般的测量值代替信号样本值用更一般的测量值代替信号样本值压缩感知或压缩采样压缩感知或压缩采样直接获取压缩后的信号；直接获取压缩后的信号；压缩压缩采样采样传输传输/存储存储NxMy接收接收 重建重建y二二. . 压缩感知理论压缩感知理论2.1 压缩感知问题描述压缩感知问题描述假假设设 x 是是一一离离散散时时间间信信号号：NxR，这这样样压压缩缩感感知知问问题题简简化化为为是是否否存存在在一一组组测测量量信信号号MyR能能完完全全恢恢复复出出 x ，其其中中 MN。设

6、设 y 的的每每个个分分量量ky 是是x与与一一组组测测量量矢矢量量,1NkRkM 的的内内积积，即即：,kkyx，1kM ，测测量量矩矩阵阵 的的行行向向量量为为k， 的的大大小小为为MN，则则测测量量信信号号y 可可以以写写为为 yx （2.1.1） 问问题题为为： 是是否否存存在在一一种种测测量量， 能能使使原原始始信信号号NxR由由测测量量信信号号MyR恢恢复复，这这里里MN。可可以以看看出出，式式（2 2. .1 1. .1 1）是是一一个个欠欠定定方方程程，存存在在无无穷穷多多组组解解。要要想想唯唯一一恢恢复复 x ，信信号号 x 和和矩矩阵阵 还还需需要要满满足足什什么么条条件件

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

8、小变化导致解很大）解连续地依赖于数据（观测矩阵或数据微小变化导致解很大变动）变动）病态问题病态问题 如果良态问题的三个条件任意一个不能满足，如果良态问题的三个条件任意一个不能满足，就称问题是病态的（就称问题是病态的（ill-posed problem） 良态与病态问题：良态与病态问题：1212400201200800401200 xxxx12100200 xx 1212401201200800401200 xxxx124000079800 xx病态问题举例病态问题举例系数矩阵系数矩阵A或者观测项或者观测项(常数项常数项)y的微小变化引起解的的微小变化引起解的巨大变化巨大变化,该问题为病态问题该

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

10、束转换为无约束问题约束转换为无约束问题问题 2. 如何设计测量矩阵，让其作用于信号后如何设计测量矩阵，让其作用于信号后 能保持信号的所有信息不丢失？能保持信号的所有信息不丢失？ （对应于香农采样定理中对采样率的要求）（对应于香农采样定理中对采样率的要求）3. 如何从测量中重建原信号？如何从测量中重建原信号？ （对应依据香农采样定理采样后内插实现重建）（对应依据香农采样定理采样后内插实现重建）1. 信号应满足什么要求，方可重建？信号应满足什么要求，方可重建？ （对应香农采样定理中对信号的带宽要求）（对应香农采样定理中对信号的带宽要求） CS关注的问题关注的问题 信号表示信号表示将信号表示为一组正

11、交基的线性组合将信号表示为一组正交基的线性组合 如果合理选择基底，处理系数序列比直接处理信号简单；如果合理选择基底，处理系数序列比直接处理信号简单； 如果系数序列如果系数序列 具有稀疏结构，可以从实质上降低信号具有稀疏结构，可以从实质上降低信号处理的成本，提高压缩效率。处理的成本，提高压缩效率。 二二. . 压缩采样理论压缩采样理论2.2 信号的稀疏与可压缩性信号的稀疏与可压缩性信号的稀疏（信号的稀疏（Sparsity）与可压缩性）与可压缩性( (Compressibility) )设设,1iiN 为为一组标准正交基，由这组基张成的空间为一组标准正交基，由这组基张成的空间为NR，设信号设信号N

12、xR，1Niiix，或用矩阵表示，或用矩阵表示x ， （， （的列为的列为i，是是元素为元素为i的列的列向向量） 。量） 。 x ， 其中其中,iix 如果矢量如果矢量的大多数元素都为的大多数元素都为 0，称，称 x 为为域稀疏的。将其不为域稀疏的。将其不为零的个数记为零的个数记为 S，0S，称，称 x 为为 S-稀疏。稀疏。如果如果矢量矢量的元素按幅值的元素按幅值大小排列，其幅度衰减很快，大小排列，其幅度衰减很快，具有幂次速度（具有幂次速度（Power law）衰减趋势。）衰减趋势。则称信号则称信号 x 为为域可压缩的域可压缩的(Compressible)。 光滑信号光滑信号其其Fourie

13、r变换变换,Wavelet,Wavelet变换系数呈现幂次衰减变换系数呈现幂次衰减趋势趋势其全变差（其全变差（Total Variation）呈现幂次衰减趋势）呈现幂次衰减趋势有界变差函数有界变差函数 给定一个定义于有界开集给定一个定义于有界开集上的可微函数上的可微函数 f，其全变，其全变差（差（the total variation） 为为对于图像对于图像x而言，其而言，其TV范数为范数为Cameraman 原图4层小波分解傅里叶幅频MRI图像图像4层小波分解傅里叶幅频原图原图垂直垂直水平水平全变差全变差根据信号根据信号 x x 的先验知识的先验知识，可以设计规整可以设计规整化项为化项为R2

14、空间，一维子空间用空间，一维子空间用lp范数进行约束的解范数进行约束的解2.3.1不确定原理（测不准原理不确定原理（测不准原理 Uncertainty Principle, UP）物理学中经典的测不准原理物理学中经典的测不准原理两个共轭的物理量，如微观粒子的位置和动量，不能同时两个共轭的物理量，如微观粒子的位置和动量，不能同时测准，测准，其中一个量越确定，另一个量的不确定程度就越大其中一个量越确定，另一个量的不确定程度就越大2.3 测量测量离散时间不确定准则离散时间不确定准则（Discrete Time Uncertainty Principle）令令( )x t是是长长度度为为N 的的离离散

15、散序序列列，0 1 , ,tN， 其其离离散散F Fo ou ur ri ie er r 变变换换为为 x，0 1 , ,N，tN ，N分分别别为为 ( )x t 和和 x中中不不为为零零元元素素的的个个数数，则则 2ttN NNNNN 或或者者将将记记:supTp x，:sup p x；TN ； 2TN 注：集的势：集合元素的个数注：集的势：集合元素的个数05010015000.10.20.30.40.50.60.70.80.9105010015000.10.20.30.40.50.60.70.80.91 10110,tm NmNx t其他 其其F Fo ou ur ri ie er r变变

16、换换 x与与x完完全全一一样样。 xx ； 此此时时2tNNN， 或或者者说说2TN 如如果果信信号号的的长长度度N为为质质数数， 排排除除了了上上述述Dirac Comb的的情情况况， 则则离离散散不不确确定定准准则则为为 tNNN x x t2.3.2 部分部分Fourier变换已知的信号重建与变换已知的信号重建与 Robust Uncertainty PrinciplesCS提出的最初研究：提出的最初研究：2004年，年，Emmanuel Candes, Justin Romberg和和Terence Tao 对以下问题进行了研究对以下问题进行了研究离离散散时时间间信信号号NxC， 其其

17、离离散散 Fourier 变变换换 :NNFxx CC，如如果果已已知知 x 的的 N 点点 Fourier 系系数数 ,Nx kkZ，可可以以通通过过 Fourier反反变变换换完完全全恢恢复复出出x。 问问题题： 如如果果只只是是已已知知部部分分的的 Fourier 系系数数 ,x kk ， 其其中中为为NZ 的的子子集集，NZ ，N ，是是否否可可以以恢恢复复出出原原信信号号？ 注注：集集的的势势：集集合合元元素素的的个个数数 MRI图像图像Fourier 采样，采样，22线线Fourier幅度幅度定定理理 2.1：假假设设信信号号x的的长长度度 N，且且 N 为为质质数数，x的的支支撑

18、撑集集为为T ，T 为为0 11, ,N 的的子子集集，若若令令其其傅傅里里叶叶变变换换 x 的的支支撑撑集集也也为为0 11, ,N 的的子子集集，如如果果 满满足足： 12T 则则x可可以以从从和和 x唯唯一一恢恢复复。反反之之，当当N 时时，存存在在两两个个不不同同的的信信号号1x 和和2x ，1T和和2112T ，并并且且12xx。 定理定理 2.2：NxC是离散信号，其支撑集为未知集是离散信号，其支撑集为未知集NTZ，在所有，在所有M 的的集合中，随机选择一个集合中，随机选择一个频率频率集合集合，对于给定的精确度参数，对于给定的精确度参数 m，如果，如果 1mTCN(log)， 其中

19、常数其中常数0mC ，能以至少，能以至少1mO N()的概率，从求解下式的概率，从求解下式 10min . . Nng ns tg kx kfor all k 得到的解是唯一的，且等于得到的解是唯一的，且等于x。 对于对于,20,24NNm ，有，有1231mCm M=logN.S以往的：以往的：2TN (1)(1) 如果如果 N N 为质数，则有为质数，则有TN （2） 有有NZ的两个子集的两个子集T和和， 讨论， 讨论T 应为多大才可能构造出一个信应为多大才可能构造出一个信号使得其时域和频域的支撑分别为号使得其时域和频域的支撑分别为T和和。 由于由于 Dirac Comb 代表的是特例，当

20、其幅值不为代表的是特例，当其幅值不为 1 时，则时，则 x在在 N 点均点均不为不为 0；对多数信号而言，；对多数信号而言，(2)比（比（1）更接近实际情况；如果随机选择一）更接近实际情况；如果随机选择一对对( ,)T ，如果，如果 1 logNTN （RUPRUP） （3 3） 定理与定理与UP的关系，以及的关系，以及RUP （Robust Uncertainty Principle）是预先确定的数， 则能以超过是预先确定的数， 则能以超过1()O N的概率找到的概率找到一个信号其时域和频域的支撑分别为一个信号其时域和频域的支撑分别为T 和和。 2.3.3 随机采样与重建随机采样与重建定义定

21、义2.1 2.1 互相干互相干互定理定理2.32.3几点说明几点说明：2. 信号表示越稀疏信号表示越稀疏、两组基之间的互相干性越小，所需两组基之间的互相干性越小，所需 要的样本数就越少要的样本数就越少3. 常用的测量矩阵有高斯和伯努利分布，因为其与常用的测量矩阵有高斯和伯努利分布，因为其与 大多数的稀疏表示基相干性小。大多数的稀疏表示基相干性小。测量结果测量结果稀疏信号稀疏信号x x随机投影随机投影（测量）矩阵（测量）矩阵压缩采样的情况压缩采样的情况1: 信号本身稀疏信号本身稀疏信号是时域稀疏的，频域测量结果含有信号的所有信息信号是时域稀疏的，频域测量结果含有信号的所有信息；信号信号测量测量0

22、1020304050607080901000123456789signal x05101520253035404550-1-0.8-0.6-0.4-0.200.20.40.60.8measurement result y原信号原信号xx*xM=50；S=19；N=100重建信号重建信号x时域信号时域信号频域频域1-维信号维信号信号是频域稀疏的，时域测量结果信号是频域稀疏的，时域测量结果；压缩采样的情况压缩采样的情况2信号可以用一组基稀疏表示信号可以用一组基稀疏表示2-维图像信号维图像信号2.3.4 一致不确定准则一致不确定准则（Uniform Uncertainty Principle, UU

23、P）2222221322MMxxxNN 假设假设为为 FourierFourier 变换，变换，为为随机随机抽取抽取行行，上上式说明，式说明，2lx至多为至多为232lMxN由于由于22nlZlxx， 可以看到， 时域稀疏的信号， 可以看到， 时域稀疏的信号x将将在频域内平铺，而不是集中在在频域内平铺，而不是集中在内。除非内。除非 M 选得接近选得接近 N，即测，即测量点数量点数要足够要足够多。多。 对对 GaussianGaussian 和和 Binary Binary 矩阵，是以矩阵，是以log N，而傅立叶矩阵，而傅立叶矩阵以以6log N满足满足 UUPUUP； 严格重建准则（严格重建

24、准则（Exact Reconstruction Principle, ERP）称测量矩阵称测量矩阵以过采样因子以过采样因子服从服从 ERPERP，如果对足够小的，如果对足够小的 a0 和固定和固定的正参数的正参数0，对于每个满足，对于每个满足MTa 的 T，定义在定义在 T 上的每个符上的每个符号向量号向量 1t，以，以1()aO N的概率存在具有下述性质的向量的概率存在具有下述性质的向量NPR， （， （i） P tt 对所有对所有tT (ii) P 是是行向量的线性组合行向量的线性组合 （iiiiii） 12P t ，对所有，对所有01:,CtTNT 定义定义 2.2：可压缩信号：可压缩信

25、号：设设,1iiN 为为一组标准正交基，由这组基张一组标准正交基，由这组基张成的空间为成的空间为NR ，设信号设信号NxR，1Niiix，将这些系数的绝对值按降序重新，将这些系数的绝对值按降序重新排列排列 12N 对于对于0p , 如果对于每个如果对于每个1nN，有，有 1pnR n 则称则称属于半径为属于半径为 R 弱弱-lp 球球，或者将，或者将 x 记为记为 pxwlR，换句话说，换句话说，p 控控制衰减的速度，其值越小，则衰减越快。制衰减的速度，其值越小，则衰减越快。 可压缩信号（近似稀疏信号）的重建可压缩信号（近似稀疏信号）的重建定理定理 1 1.4.4： 令令分别以分别以1满足满足

26、 UUPUUP，以，以2满足满足 ERPERP，令，令12max, ，假，假设设M，如果信号，如果信号NxR，且对，且对01p，有，有 1pnR n，或者或者1p 时，时，1xR，令，令112rp，则对任意足够小的，则对任意足够小的a，P1问题问题的的解解*x至少以概率至少以概率1()aO N满足满足 2rp aMxxCR*, 对对 GaussianGaussian 和和 Binary Binary 矩阵， 是以矩阵， 是以logN满足满足 UUPUUP 和和 ERPERP；而而FourierFourier矩阵以矩阵以6log N满足满足UUPUUP， 以， 以log N满足满足ERPERP，

27、因此，定理因此，定理 2 2.4.4 对对 GuassianGuassian 和和 BinaryBinary 矩阵而言矩阵而言 2rp aMxxCRN*,log 1min,.styx （P1） 定理定理2.42.42 2. .3.53.5 等距常数等距常数 Isometry ConstantS、约束约束等距等距性质性质（Restricted Isometry Property, RIP） 、） 、S,S-约束约束正交常数正交常数,S S 定义定义2.3： 对每个整数： 对每个整数1 2, ,S ， 定义矩阵， 定义矩阵的的约束约束等距常数等距常数S为对于所有为对于所有S 稀疏的矢量稀疏的矢量x

28、，式（，式（2.7.1）成立）成立的最小常数，的最小常数， 22222211STSxxx （2.7.1） 如果如果S不接近于，称矩阵不接近于，称矩阵满足满足 S S-阶的阶的 RIPRIP。 或者抽取矩阵或者抽取矩阵的列向量构成矩阵的列向量构成矩阵T ，1,TN是是MT维矩阵，维矩阵，对于每个整数对于每个整数S，定义，定义矩阵矩阵的的约束约束等距常数等距常数S为满足下式的最小的常数：为满足下式的最小的常数： 22222211STSccc （2.7.2） 保证信号不在测量的零空间，信号的范数近似保持定义定义 2.32.3定义定义 2 2. .4 4 对于所有不相交的对于所有不相交的,1,T TN

29、，集合的势，集合的势 TS和和TS ，对于对于SSN， S,S-约束约束正交常数正交常数,S S为使为使 ,TTS Sccc c 最小的数。几何意义是由最小的数。几何意义是由T 和和T 张成的列矢量的两个子空间最小张成的列矢量的两个子空间最小夹角的余弦。其值越小，说明两个子空间接近正交。夹角的余弦。其值越小，说明两个子空间接近正交。 S和和,S S度量了矢量度量了矢量 njj JvR接近于正交基的程度。当接近于正交基的程度。当满足满足S S- -阶阶 RIPRIP， 则说明， 则说明近似保持了近似保持了 S S- -稀疏的信号的欧几里得距离。 也说明稀疏的信号的欧几里得距离。 也说明了了 S

30、S- -稀疏信号不在稀疏信号不在的零空间。这对唯一性的保证很重要的零空间。这对唯一性的保证很重要。关于关于 RIP条件的另一种等价说法是矩阵中所有可能的条件的另一种等价说法是矩阵中所有可能的 S S 个列向量近似正交。个列向量近似正交。 定理定理2.52.5定理定理2.62.6定理定理 2.7 假设假设 x 是一个是一个 S-稀疏的信号稀疏的信号且且231SS ，或者，或者，221,SSS ，则，则 1min,. .xstyx 的解为的解为x 定理定理 2 2. .8 8（无噪声恢复）（无噪声恢复） 假设假设221s ，则，则 1min,. .xstyx 的解的解*x 服从服从*011sxxC

31、xx 和和 1*2012sxxC Sxx 0C 为为常数，常数，Sx 是保留是保留 x中的中的 S S 个最大元素，其余元素都置个最大元素，其余元素都置零的矢量。如果零的矢量。如果 x是是 S S- -稀疏的，则可完全恢复。稀疏的，则可完全恢复。 2.3.6 鲁棒测量鲁棒测量对对于于实实际际应应用用，C CS S 应应该该既既能能处处理理稀稀疏疏信信号号，也也能能对对可可压压缩缩信信 号号 进进 行行 处处 理理 ， 可可 压压缩缩 信信 号号 也也 可可 视视 为为 稀稀 疏疏信信 号号 加加 入入 噪噪 声声 的的 结结果果；另另外外，在在测测量量中中也也不不可可避避免免的的引引入入噪噪声

32、声，对对于于这这两两种种情情况况，统统一一建建模模为为： yzAz 定理定理 1.9：假设：假设221s，则，则 12min,. .llastAay 的解的解*x满足满足 *0112sCaaCS C0, C1为常数，为常数，s是是矢量矢量的的 S 个大分量置保留，其余为个大分量置保留，其余为 0 结果。结果。 定理定理2.92.9测量测量A的零空间的零空间如果想从测量中重建所有的稀疏信号如果想从测量中重建所有的稀疏信号x，则对任意一对不，则对任意一对不同的信号同的信号x和和x ， 必然有必然有Ax与与Ax。如果来观测。如果来观测Ax=Ax，则得到，则得到x-x是是2K稀疏的，稀疏的， 因此，因

33、此，A能唯能唯一表示所有一表示所有 ，则，则 中不能含有中不能含有 的向量。有许多的向量。有许多方式可以表征这种性质，其中之一为方式可以表征这种性质，其中之一为A的的Spark定义定义Spark：一给定矩阵：一给定矩阵A的的Spark是其最少的线性相关列是其最少的线性相关列的个数。的个数。 2.3.7 最小化问题的唯一解最小化问题的唯一解P0 问题的唯一解问题的唯一解( )/ 2kspark AP1 问题的唯一解问题的唯一解101(1( ) )2xA称称A有有则则A具有具有k阶零空间性质阶零空间性质( )0hN A1112hhk MRI图像Fourier 采样，22线令能量最小 ，未采样的Fo

34、urier系数置0CS重建，令图像的TV范数最小 利用计算机解决实际问题，通常要按以下步骤进行：利用计算机解决实际问题，通常要按以下步骤进行： （1）建立数学模型，即把实际问题抽象为一个数学）建立数学模型，即把实际问题抽象为一个数学问题，可以是一个方程组问题，可以是一个方程组 、一个函数、一个微分方程、一个函数、一个微分方程等。等。 （2）选择数值方法，要考虑所能达到的精度，计）选择数值方法，要考虑所能达到的精度，计算量，方法对数据微小扰动的灵敏度。算量，方法对数据微小扰动的灵敏度。 （3）编写程序，上机计算。）编写程序，上机计算。第二部分第二部分 CSCS中的信号重建中的信号重建两类主要方法

35、：两类主要方法：一、贪婪搜索一、贪婪搜索 （Matched Pursuit, 匹配追踪）匹配追踪）二、基追踪二、基追踪 （Basis Pursuit， 基追踪）基追踪）称为基追踪问题，（称为基追踪问题，（Basis Pursuit，BP）匹配追踪（匹配追踪（Matched Pursuit，MP）一、匹配追踪（一、匹配追踪（Matched Pursuit，简称，简称MPMP）MP算法的步骤算法的步骤1. 初始化初始化稀疏稀疏矢量矢量x为为0，留数，留数r0=y，循环索引，循环索引 t=1； 2. 确定索引确定索引1argmax,ttr, %让矩阵让矩阵的每个列的每个列向量向量（或称为原子）与（或

36、称为原子）与rt-1作内积，找到是的该内积最大的作内积，找到是的该内积最大的列向量的序号给列向量的序号给t； 3. 更新更新系数：系数： 1()(),ttttxxr， 4更新留数更新留数 11,tttttrrr， 5. 更新更新 t=t+1； 6如果如果 tS, 则停止迭代，否则则停止迭代，否则返回步骤返回步骤 2 正交匹配追踪（正交匹配追踪（Orthogonal Orthogonal Matched Pursuit，简称，简称OMPOMP）OMP算法步骤算法步骤t=t+1;5：如果：如果 tS, 则停止迭代，否则重复步骤则停止迭代，否则重复步骤1体现正体现正交思想交思想22minxxyx m

37、in( )minTxxxf xyxyx( )0f xx由多元函数的微分学知，上式的解一定是驻点由多元函数的微分学知，上式的解一定是驻点( )20Tf xyxx TTxy 1TTxy 线性规划问题的标准形式线性规划问题的标准形式 s.t.其中其中 为为MN阶阶矩阵矩阵 min A =b0Tc xxx11121N21222NM1M2MNaa.aaa.aA=.aa.a12n=(c ,c ,c )Tc12N=( ,)Txx xx12Nb=(b ,b ,b )T二、基追踪问题（二、基追踪问题（BPBP） 约束条件以及目标约束条件以及目标函数都是决策变量函数都是决策变量的线性函数的规划的线性函数的规划问题

38、称为问题称为线性规划线性规划(Linear Programming),A by1;1c ,xuvuxv为 中的正元素,为负元素的绝对值uvya 1min as.t. 线性规划问题解的概念：线性规划问题解的概念： (1) (1) 可行解可行解。满足约束条件的解。满足约束条件的解可行解集称为线性规划问题的可行域。可行解集称为线性规划问题的可行域。 (2) (2) 最优解最优解。使目标函数达到最优值的可行解称为最优解，。使目标函数达到最优值的可行解称为最优解，最优解常用最优解常用 表示。表示。 (3) (3) 基基。若是中。若是中M MM M阶非奇异矩阵，即阶非奇异矩阵，即| |0|0，则称是线性规

39、，则称是线性规划问题的一个基。划问题的一个基。 min Tc xA =b0 xx*x12N=( ,)Txx xxD= / A =b ,0 xxx s.t.基向量，基变量基向量，基变量 若是线性规划问题的一个基，那么一定是若是线性规划问题的一个基，那么一定是由由M M个线性无关的列向量组成，不失一般性，可设个线性无关的列向量组成，不失一般性，可设 称称 为为基向量基向量，与基向量相对应的变量称为与基向量相对应的变量称为基变量基变量。 基的个数基的个数 一个线性规划的基通常不是唯一的，但是一个线性规划的基通常不是唯一的，但是基的个数基的个数也不也不会超过会超过 个。一旦线性规划的基确定了，那么相应

40、的基向量、基变量个。一旦线性规划的基确定了，那么相应的基向量、基变量和非基变量也就确定了。和非基变量也就确定了。11121M21222M12MM1M2MMaa.aaa.aB=(P,P ,P ).aa.aMNCj1j2jMjp =(a ,a ,a), (j=1,2,M)jPjx , (j=1,2,M)( (4) 4) 基本解基本解。设。设B B是线性规划的一个基，若令是线性规划的一个基，若令n-mn-m个非基变量等于个非基变量等于0 0，则，则所得的方程组所得的方程组=b=b的解称为线性规划问题的一个基本解（简称基解）。的解称为线性规划问题的一个基本解（简称基解）。 有一个基就可以求得一个基本解

41、。有一个基就可以求得一个基本解。 由基的有限性可知，基本解的个数也不会超过由基的有限性可知，基本解的个数也不会超过 个。个。 由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5) (5) 基本可行解基本可行解。满足非负条件的基本解称为基本可行解。满足非负条件的基本解称为基本可行解 （简称基可行解）。（简称基可行解）。与基本可行解对应的基称为与基本可行解对应的基称为可行基可行基。 基本可行解的非零向量的个数小于等于基本可行解的非零向量的个数小于等于m m，并且都是非负的。，并且都是非负的。 由于基本可行解的数目一般少于基本

42、解的数目，因此可行基由于基本可行解的数目一般少于基本解的数目，因此可行基 的数目也要少于基的数目。的数目也要少于基的数目。 当基本可行解中有一个或多个基变量是取零值时，称此解为当基本可行解中有一个或多个基变量是取零值时，称此解为 退化的基本可行解退化的基本可行解。MNC可行解可行解基本解基本解求解线性规划：求解线性规划：图解法图解法单纯形法单纯形法内点算法内点算法70单纯形法的一般步骤如下：单纯形法的一般步骤如下：（1 1）寻找一个）寻找一个初始的基本可行解初始的基本可行解。（2 2）检查现行的基本可行解是否）检查现行的基本可行解是否最优最优，如果为最优，如果为最优，则停止迭代，已找到最优解，

43、否则转一步。则停止迭代，已找到最优解，否则转一步。（3 3）移至目标函数值有所改善的）移至目标函数值有所改善的另一个基本可行解另一个基本可行解，然后转回到步骤（然后转回到步骤（2 2）。）。 其其基本思路基本思路是从一个初始的基本可行解出发，是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。寻找一条达到最优基本可行解的最佳途径。 19471947年，年，DantzigDantzig提出的单纯形法把寻优提出的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）的目标集中在所有基本可行解（即可行域顶点）中。中。 单纯形法单纯形法Lasso问题问题yx 1min xs.t.BP

44、DN（Basis Pursuit Denoising）BP（Basis Pursuit ）1min xs.t.22yx(1) 约束问约束问题题(2) 约束约束问题问题问题问题(2)的解要么是的解要么是x=0, 要么是问题要么是问题(3)的解的解,因此说因此说BPDN问题与问题与LASSO等价等价(3)无约束无约束问题问题3.13.1无约束最优化方法无约束最优化方法min( ),nf xxR 无约束问题无约束问题定义定义：设函数：设函数 f(x) 存在一阶偏导数，存在一阶偏导数，xRn ，向量，向量 )(xf=Tnxfxfxf ,21为为f(x)在点在点x处的梯度。处的梯度。定义定义 设函数设函

45、数 存在二阶偏导数，存在二阶偏导数，xR ，则称矩阵，则称矩阵 )(xfn 2222122222212212212212nnnnnxfxxfxxfxxfxfxxfxxfxxfxf为为 在点在点x处的处的Hesse矩阵。矩阵。 )(xf)(2xf =三、三、BPDNBPDN 问题问题定理定理: (一阶必要条件一阶必要条件） 凸集凸集和和凸函数凸函数在非线性规划的理论中具有重要作用，下面在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。给出凸集和凸函数的一些基本知识。 设设 ，若对，若对D中任意两点中任意两点 ，连接，连接 的线段仍属于的线段仍属于D；换言之，对；换言之，对 ,

46、 则称则称D为为凸集凸集。 称为称为 的的凸组合凸组合。NDR(1)(2),xxD(1)(2)1xxD(1)(2),xx(1)(2),xx0,1(1)(2)1xx(1)(2),xx定义定义: 凸集凸集对凸的一元函数对凸的一元函数 的几的几何意义为：在曲线上任取何意义为：在曲线上任取两点两点P1(x1, ), P2(x2, )弦弦 位于位于弧弧 之上（见图）。之上（见图）。)(xf)(1xf(x2)f21PP21PPx x1x x2x x(x, y)p p1p p2)(xf 设设D为为RN 中非空凸集，若对中非空凸集，若对 , 恒有恒有则称则称f(x) 为为D上的上的凸函数凸函数；进一步，若；进

47、一步，若 时，上式时，上式仅仅0)，修改，修改 为为x .01miig x x 求解问题求解问题(5)式就变为求解无约束问题式就变为求解无约束问题(8)式式 miigMfMp1,xxx 7 miigMfMp12, 0min,xxx 8 称函数称函数 为惩罚函数（或罚函数），其中为惩罚函数（或罚函数），其中第二项第二项 为惩罚项。称为惩罚项。称M为罚因为罚因子。子。 惩罚函数只对不满足约束条件的点实行惩罚。当惩罚函数只对不满足约束条件的点实行惩罚。当 时，满足各个时，满足各个 ，故罚项等于，故罚项等于0，不受惩罚；当不受惩罚；当 时，必有时，必有 ，故罚项，故罚项0，对极小化罚函数的问题，就要受

48、惩罚。，对极小化罚函数的问题，就要受惩罚。x 0 xigx 0 xigMp, x miigM12, 0minx 在实际计算中，罚因子在实际计算中，罚因子M的值选得过小或过大都不好。如的值选得过小或过大都不好。如果选得过小，则罚函数的极小点远离约束问题的最优解，果选得过小，则罚函数的极小点远离约束问题的最优解，计算效率很差；如果计算效率很差；如果M过大，则给罚函数的极小化增加计过大，则给罚函数的极小化增加计算上的困难。因此，一般策略是取一个趋向无穷大的严格算上的困难。因此，一般策略是取一个趋向无穷大的严格递增正数列递增正数列 ，从某个，从某个 开始，对每个开始，对每个 求解：求解：kM1MkM

49、ljjmiikkhgMfMp1212, 0min,minxxxx 11当当 趋向于正无穷大时，点列趋向于正无穷大时，点列 就从可行域外部趋于原就从可行域外部趋于原问题的极小点，问题的极小点，“外点法外点法”正是因此而得名正是因此而得名kM kx 第第1步：给定初始点步：给定初始点 ，初始罚因子，初始罚因子 （例如（例如 ），），放大系数放大系数 （如取（如取 或或10），允许误差），允许误差 。令令 。 第第2步：求解罚函数步：求解罚函数 的无约束极小化问题。的无约束极小化问题。 以以 为初始点，选择适当的方法求为初始点，选择适当的方法求解解 ，得其极小点，得其极小点 。 第第3步：判断精度。

50、步：判断精度。 在在 点，若罚项点，若罚项 ，则停止计算，得到原问题的，则停止计算，得到原问题的近似极小点近似极小点 ；否则令；否则令 ，置，置 ，返回第返回第2步。步。 0 x1M11M1501:kkMp, x1kxkMp,minx kx kx kx1:kkkkMM1外点法外点法 考虑非线性规划考虑非线性规划 s.t 记记 为可行域内部。即为可行域内部。即 是可行域是可行域 中所有严格内点中所有严格内点（即不包括可行域边界上的点）的集合。（即不包括可行域边界上的点）的集合。 ；xfmin migi, 2 , 1, 0 x migi, 2 , 1, 01xx 13 1213.2.2 内点法内点