最速下降法与最速下降法求解时的最值问题

最速下降法与最速下降法求解时的最值问题

基追踪算法近年来，稀疏解的问题引起了人们的广泛关注，这主要是因为它用于促进压缩感知的研究（例如，可以使用较少的提前测量值来恢复信号）。此外，稀疏解的研究还广泛应用于构建码、图像消动、解码、密码系统和其他领域（见）。令Φ是m×N(m<N)的行满秩(rank(Φ)=m)矩阵,‖x‖0是x的l0范数,即向量x的非零元素的个数.引入Φ的所有k-分量向量的值域如下因为m<N,所以对任意的y∈Rm,方程Φx=y有无穷多个解.记上述方程的所有解的集合为F(y)=Φ-1(y).令N:=N(Φ)是Φ的零空间.若x0是方程φx=y的一个解,则有F(y)=x0+N.给定y∈Rk,k<m,考虑如下问题文献中指出,求解最小l0范数是NP问题,而且它对噪音的敏感性也对(1)的求解造成了很大的困难.但尽管如此,文献仍得到了由l0范数直接求解(1)的算法:SL0.其中指出,这个问题难于求解的关键问题在于l0范数是一个不连续的函数(详见).基于此,作者用可微的期望值为零的高斯函数类来近似不连续的函数‖x‖0,然后应用最速下降法来精确求解相应的非线性Karush-Kuhn-Tucker(KKT)系统并证明了算法的收敛性.对于问题(1)的求解已经有了很多研究成果.基追踪算法(BasisPursuit,简称BP)是其中一个成功的方法().它主要是将原问题转化为求解如下l1-范数最小化问题这里,.文献[2,15,16,17,18,19,20]中指出,当向量x充分稀疏且矩阵Φ满足一定的条件时,问题(2)的解即为(1)的解.特别地,Candès,Romberg,Tao在中指出,若x是一个k-稀疏向量(即向量x最多有k个非零元素)且矩阵Φ满足3k-阶受限等间距性质(RIP性质),即存在常数δk对每个k-稀疏向量x满足则(2)可以精确的恢复信号.因为问题(2)可通过线性规划(LP)方法求解,所以由此可得(1)的解.通过应用快速LP算法,特别是内点LP方法,对于规模较大的问题也是可以求解的.但是,这种方法收敛得比较慢.在中,BP算法得到了改进,使得它的收敛速度更快而且也能更好地处理有噪音干扰的情形.另外一个成功求解(1)的方法是迭代重加权最小化范数解,这种算法比BP快.它主要基于如下想法:若(2)有一个分量全不为零的解x*,则如下加权最小二乘问题的解xw,与x*相等.但是,这里的x*是未知的.所以,采用迭代的方法求得x*.将x(n),n=1,2,…,记为第n步迭代时的解.首先由此计算得一个对角矩阵,W(n)=diag{w1,…,wn},其分量皆为正数.然后,第n+1步的解x(n+1)即为如下加权最小范数问题的唯一解,这个过程中最关键的地方就是如何由解x(n)确定新的权w(n).Daubechies等人在中找到一个特殊的函数来生成新的权(本文会在第二部分中对此做详细的阐述)而且最终得到了一个新的求x*的算法.他们同时也在文章中给出了算法收敛性及收敛速度的详细的理论分析.匹配追踪算法(MatchingPursuit,简称MP)是另一个快速算法().但由于这是一个贪婪算法,所以在恢复信号的精确度上仍需改进.中提到的重加权的算法速度也很快,但是其收敛性仍是一个需要研究的问题.除了通过l1范数最小化来求解(1),研究者们还考虑了lq(0<q<1)范数最小化问题这里,.Chartrand和Staneva在中证明了:在无干扰的情况下,相比于l1范数最小化求解,lq(0<q<1)范数最小化能用更少的测量量来精确地恢复稀疏信号,也就是说可以增强恢复系数信号的能力.之后,Saab和Yilmaz在中证明了lq(0<q<1)范数最小化问题在有噪音干扰的情况下也是稳定的,类似的结论在中也可以看到.在这些理论的基础上,文章中提出了关于lq(0<q<1)范数的IRLS算法.本文主要讨论三个算法.第一个是对文章中算法的一个改进.用1+q代替了中的ε2并发现当q靠近0时,改进后的算法能增强信号稀疏恢复的能力;第二个算法是直接由l0范数得来的,但是它可以看做是中算法在q=0时的延拓,它有比第一个算法更强的恢复稀疏信号的能力;第三个算法基于中光滑化的l0函数,通过不精确地解KKT系统的内迭代,即可得到新算法.这三种算法在形式上是类似的,只是每种算法都选择了不同形式的权.数值例子表明第三种算法在稀疏信号恢复能力上是最强的.本文的结构如下:§2-§4分别介绍三种新的算法,§5给出的数值试验结果表明了这三种算法都是快速有效的.算法2.2范数最小问题在这部分中,首先回顾文中的两个算法.文中的算法在每步迭代中都采用如下的一个特殊函数.由上一步的解x(n)生成新的权w(n),并利用此函数证明算法的收敛性.记R+为所有正数的集合,令k<N.给定一个实数ε>0及一个权向量,定义函数算法2.1(见)令w0:=(1,…,1),ε0:=1.则对n=0,1,…,定义当εn=0时终止算法即可得到稀疏解.令Dn是N×N对角矩阵,其第i个对角元素是.文中指出向量x(n+1)的明确表达形式为在算法2.1及后文中,对z∈RN,r(z)是向量z所有分量均取绝对值然后按单调不增的顺序排列后所得的向量.则r(z)1≥r(z)2≥…≥r(z)N≥0.对lq(0<q<1)范数最小化问题,同样定义函数在中有如下类似于算法2.1的算法2.2.算法2.2(见)令w0:=(1,…,1),ε0:=1.则对n=0,1,…,定义当εn=0时终止算法.注意到算法2.1是算法2.2在(q=1)的特殊情形.上述两个算法的收敛性已在文中得到证明(详见定理5.3和定理7.7).下面,来看本文中提出的对上述算法的改进算法.文的数值例子指出:由于算法2.2局部收敛,当q值较小时,其恢复稀疏解的能力会减弱.本文中提出的改进的新算法就是基于这个问题提出的.通过应用Lagrange方法,本文对算法2.1和算法2.2迭代过程中权的选取给出了一个相对自然的解释.为分析算法的收敛性,本文也构造了类似于中的特殊函数.由于此算法基于lq(0<q≤1)范数,故考虑问题(2)(或(3))的如下近似显然,当ε→0时,上述最小化问题即为(2)(或(3)).记应用Lagrange方法求解上述优化问题.引入Lagrange乘子λ∈Rm和Lagrange函数则问题(2.4)的解满足下式对上述非线性系统,自然想到用如下迭代法求解定义权为其中Dn为N×N对角矩阵,其第i个对角分量为.将(2.5)式与中相应的步骤比较,发现若用中的方式更新εn如下则新的算法与中的lq范数算法类似,其唯一的不同即为对权w的更新方式.以上利用Lagrange方法对权w的更新做了一个自然合理的解释.下面,将构造一个特殊的函数并讨论算法的收敛性.本文中,定义如下函数并将改进的算法归纳如下:算法2.3令w0:=(1,…,1),ε0:=1.则对n=0,1,…,定义当εn=0时终止算法即可得到稀疏解.发现,算法2.2和算法2.3的区别在于权w的选取.在文中,算法2.2的权选取如下:而在改进后的算法2.3中,权的选取如下:第五部分的数值结果将会表明:当q取值较小时,算法2.3比算法2.2恢复稀疏信号的成功率更高.这也验证了文中的定理,即对lq极小化问题来说,稀疏量k满足且其中A,B是正的常数.由中的引理5.1,即可以得到迭代序列的收敛性由中的定理7.7可知,矩阵Φ在满足一定的条件下,算法2.3的数值解在εn→0时收敛于稀疏解.稀疏解xn+1更新在这部分中,将介绍一个新算法,它通过直接求解问题(1)得到.考虑问题(1)的如下近似因为当ε→0且xi≠0时,,所以上述最小化问题的目标函数趋向于线性系统Φx=y的解x的非零元素个数(即为其l0范数).问题(3.1)是非线性的,因此用线性化的方式得到其迭代步骤:给定x(n)∈RN及参数εn>0,更新x(n+1)∈RN如下:即可得到如下算法.算法3.1取初始值x(0)=0及参数ε0=1.对n=0,1,2,…,定义及当εn=0时停止算法,即得到稀疏解x(n).注3.1一般情况下,算法会生成一个由不同向量组成的无穷序列{x(n)}n≥0.注3.2亦可选取其它递降的方式来更新参数εn.例如,文中选εn+1=τεn,其中0<r<1.在数值算法中,用(3.4)中的方式来更新εn,因为这种形式的更新意味着当εn=0时,可得到稀疏解.为研究算法3.1,首先欲求(3.2)的解x(n+1)的显示表达形式.为此,再次使用Lagrange方法.引入Lagrange乘子λ∈Rm和Lagrange函数由(3.3)得记Dn为N×N对角矩阵,其第i个对角分量为.则上述线性系统的解为§5的数值结果表明由算法3.1生成的序列是收敛的.特别地,当ε→0时,它收敛于稀疏解.而且,对于同样的稀疏量k,作为q=0的拓展,算法3.1比算法2.3中0<q≤1的情况恢复稀疏解的成功率更高.为负性依赖的l0范数如何求解在这部分中,引入另一个基于l0范数的新算法.不同于算法3.1中近似l0范数的方式,下文中将引用l0范数在文中提及的另一种光滑化形式.如在引言中所指,问题(1)难解的关键在于l0范数的不连续性.为克服这一缺点,文中用如下光滑的期望值为零的高斯函数类来近似‖x‖0.令因此,选用N-Fσ(x)作为‖x‖0的近似.即,其中,参数σ的值决定了函数Fσ的光滑度及近似的精确度,σ的值越小,近似越精确;σ的值越大,高斯函数越光滑.由以上分析,l0范数最小化问题已转化为:当σ较小时,求解函数Fσ(x)的最大化问题.故,考虑如下问题对于问题(4.1)的求解,有如下的两步迭代算法:生成σ的递降序列作为外迭代;内迭代则是对给定的σ求解(4.1).继续应用Lagrange方法.引入Lagrange乘子λ∈Rm和Lagrange函数则针对问题(4.1),有如下Karush-Kuhn-Tucker(KKT)系统其中,λ1=-σ2λ.在本文中,用如下的近似方法来不精确地求解内迭代.给定σ0,x(0),对n=0,1,2,…,令参数σ的更新如下其中0<ρ<1.有如下新的迭代算法.算法4.1取初始值w(0)=1及参数σ0=1.对n=0,1,2,…,定义及当参数σn的值足够小时,算法停止.在算法4.1中,Dn为N×N对角矩阵,其第i个对角分量为.参数ρ的选择是要确保序列{σn}递降,故选取ρ∈(0,1).在数值试验中,会考察ρ的选取对于稀疏解恢复的精确性和成功率的影响.注4.1当σn取值较小时,矩阵Dn的某些对角元素会变得任意大,导致(4.3)难于求解.故若在数值例子中遇此情况,用一个相对大的数值代替它,例如1×108,此时Dn中元素的值最大不会超过1×108.注4.2格式(4.3)-(4.5)类似于中的算法,其不同之处仅在于权的选取.在恢复稀疏中的应用在这部分中,将给出以上三种新算法的数值结果.向量x*的稀疏量达到多少才能将其精确恢复呢?对此问题已经有了一定的理论结果.文指出,一个向量要保证稀疏恢复的唯一性,其非零的元素个数最多不能超过一个极限值,其中m指测量矩阵A的行数.但是,实际上,大多数算法都达不到这个极限值.这部分的实验结果将给出本文的算法所需要的向量能精确恢复的稀疏度.在本文的算法中,右端项y的选取如下其中k为精确的稀疏解x*的非零个数.在第一个实验中,主要研究算法2.3.针对不同的q值,将把算法2.3与算法2.2在解的恢复能力上作比较.在第二个实验中,主要考察算法4.1本身恢复稀疏解的能力及参数ρ的取值对解恢复精确度的影响.最后,在第三个实验中,将本文中的三个算法进行对比,考察它们各自的优缺点.主要从两个方面进行比较:迭代的收敛速度及精确恢复稀疏解的能力.实验1在本实验及余下的两个实验中,选取满足N(0,)高斯独立分布的m×N维矩阵Φ来恢复k-稀疏向量x*.文献中证明了这样的矩阵在很大的概率上满足有优化边界的RIP性质.已经知道算法2.2和算法2.3的区别在于权的选取的不同.从它们的格式上可以发现随着q逐渐趋向0,算法格式上的差距越来越大.因此,在图1和图2中展示了q=0.8及q=0.2两种情形下两种算法对解的恢复情况.数值试验中,选取的两种算法的终止条件是图1表明,当q=0.8时,算法2.3在恢复稀疏解时略优于算法2.2;而在图2中,可以看到当q=0.2时,算法2.3恢复稀疏解的成功率远优于算法2.2.而就两种算法的收敛速度来看,并没有明显差异.做了很多实验发现,它们的迭代步数基本相同.实验2在本实验中,引入信噪比(SNR)来衡量算法恢复的精确度.信噪比这一衡量标准在信号等领域中已有广泛应用.其定义如下其中x*andx分别表示精确的稀疏解和算法得到的近似值.SNR值越大意味着恢复的精确度越好.将σn≤0.01作为算法的终止条件.在图3中考察算法4.1的对稀疏解的恢复能力及参数ρ的取值对解恢复精确度的影响.之前提到,对于m=400的测量矩阵,能恢复的稀疏度的极限值为k=200.图3中刻画了三个不同的稀疏度k=100,150,190在ρ取不同的值时解的SNR值的三条曲线.可以看到,对于同一个稀疏度k,随着ρ值的增加,SNR值在增大,即解的恢复越来越准确;而对于同一个ρ值,随着k值的增加,SNR值在减小,即解的恢复精度越来越差.但是,即便是k=190这种类似于极限值的情况,本文的算法在ρ值相对大时依然能恢复稀疏解.实验3在本实验中,把这三种算法加以对比.首先,在图4中对比它们的收敛速度.算法4.1的格式表明其迭代步数与参数值ρ的选取有一定关系.而且,在实验2中发现ρ的取值越大,解恢复的成功率越高.因此,这里以ρ=0.8为例来看收敛速度.算法4.1的终止条件为图4表明,这三种算法的迭代步数基本相同.在图5中,将三种算法在稀疏解恢