文摘
我们研究的非单调自适应Barzilai-Borwein梯度算法范数最小化问题引起的压缩传感。在每个迭代中,生成的搜索方向享有财产,可以很容易地得到了最小化一个本地邻近的二次模型,同时良好的结构规范。在一些合适的条件下,可以建立了其全局收敛性结果。数值结果表明,该方法与现有承诺和竞争算法NBBL1和转折。
1。介绍
近年来,算法寻找稀疏欠定方程的线性系统解决方案集中调查了在信号处理和压缩传感。压缩感知(CS)的基本原则是,一个稀疏信号从欠定的线性系统可以恢复吗,在那里(通常是)。通过定义规范()一个向量的非零组件的数量,一个自然的方式来重建从系统是解决以下问题: 通过一定的重建技术。然而,规范问题是组合,一般难以计算。一个基本的解码模型CS替换规范的被定义为规范。由此产生的适应(1)是所谓的基础上追求(BP)问题(1] 结果表明,在一些合理的条件下,问题(2)可以产生所需的解决方案有高概率2]。当包含了一些噪音在大多数实际应用中,约束(2)应该放松惩罚最小二乘问题: 在这里,有关约束的拉格朗日乘子(2)。
它遵循从现有的一些结果,如果一个信号是稀疏的或者近似稀疏一些正交基,然后准确恢复时可以获得是一个随机矩阵投影(3]。相当多的算法已经提出和解决上述的研究在计算机科学中遇到的问题。最近,一些一阶方法是受欢迎的解决(3),比如投影最速下降法(4)和梯度投影算法(GPSR)提出的Figueiredo et al。5]。此外,基于平滑技术研究[6),提出了一种快速而准确的一阶算法称为内斯塔在[7),等等。由一个算子分裂技术,海尔等人得到迭代收缩算法(FPC)[/阈值定点延续8]。一个最广泛的研究了一阶方法是迭代收缩/阈值(IST)方法(9- - - - - -11),这是专为小波图像反褶积。转折(12,13]和FISTA [14)加速的性能是有几乎相同的复杂性,但是有更好的收敛特性。另一个密切相关的方法是稀疏重建算法SpaRSA [15),以减少非光滑凸问题可分离结构。在[16),作者提出了非光滑滤方法规范的问题。SPGL1 [17)解决了最小二乘问题谱范数约束的梯度投影法与高效的欧几里得投影标准球。在[18),云和(音)研究了一块坐标梯度下降(CGD)方法求解(3)。最近,交替方向法(ADM)已收到关注解决全变差正则化图像恢复的问题,也能解决规范CS(正则化问题19,20.]。
最近,肖等人提出一个Barzilai-Borwein梯度算法(21为解决正规化的非光滑最小化问题(NBBL1) [22),他们近似本地一个凸二次模型在每个迭代中,黑森被倍数的谱系数的单位矩阵。出于他们,我们提出一个非单调适应性Barzilai-Borwein梯度算法压缩传感范数最小化,这是基于一个新拟牛顿方程(23)和一种新的自适应谱系数。在合理的假设下,建立可收敛结果。数值实验表明,该方法有效的恢复是一个稀疏信号压缩传感和优于NBBL1产生。
一个完整的描述在下一节提出的算法。与此同时,我们在一些适当的条件下建立其全局收敛性。节3据报道,一些数值结果说明了该方法的效率。最后,我们有一个结论部分。
2。算法和收敛结果
在本节中,我们构造一个迭代算法来解决规范正则化问题起源于复苏压缩传感的备用方案。说明我们的方法的步骤之前,我们先给一个简短的描述下面的无约束优化的初步结果: 在哪里是一个连续可微的函数。
在[23),魏等人提出了一种新的拟牛顿方程,然后导出一个新的共轭性条件通过使用这个新拟牛顿方程。使用目标函数的泰勒公式, 在哪里(职责。)表示函数值(分别地。海赛矩阵)表示在。因此,用, 因此, 考虑作为一种新的近似的这样 在哪里,,,。这表明以下新拟牛顿方程: 在[24),李等人作出修改在(9)如下: 和人民币和魏25)做一些进一步的研究。观察到这个新拟牛顿方程不仅梯度值信息,还包含函数值信息目前和前一步。一般来说,这样的将由更新一些典型的和受欢迎的公式如高炉煤气、DFP, SR1。此外,让近似黑森是一个对角矩阵与积极的组件;也就是说,用一个单位矩阵和。然后,拟牛顿条件(9)具有以下形式: 两边同时乘以,接下去 ,两边同时乘以,它给 在哪里被定义为(10)。如果持有,那么矩阵是正定的,确保了搜索方向在当前点是血统。
现在,我们集中我们的注意力范数最小化问题(3)。该算法可以被描述为迭代形式 在哪里是一个stepsize和是一个搜索方向定义为最小化的二次近似模型。自项不是可微的,因此,在当前,目标函数近似的二阶近似, 在哪里和是一个小的正数。这个词在可以被看作是一个近似的泰勒展开的有一个小,案件减少了等价形式。最小化(15)的收益率 在哪里,,表示th组成部分,,,分别。良好的结构(16)承认明确的解决方案 因此,在当前点的搜索方向
在本文中,我们采用以下适应性Barzilai-Borwein一步(18): 在哪里和定义在(12)和(13),分别。
根据以上推导,我们现在描述的非单调自适应Barzilai-Borwein梯度算法(缩写为NABBL1)(参见算法1)。
|
||||||||||||||||||||
备注1。我们已经表明,如果,然后生成的方向是血统。然而,在这种情况下,条件可能无法得到满足和遗传血统属性是没有保证的。应对这一缺陷,我们应该保持序列一致有界;也就是说,足够小和足够大,是被迫的
这种方法可以确保从零是有界的,随后确保吗在每个迭代血统。
我们准备给我们的主要NABBL1算法的全局收敛性结果。的理想的收敛性是直接从定理3.322];我们国家的完整性。
定理2。让序列和由算法生成的1。然后,存在一个子序列这样
3所示。实验结果
在本节中,我们描述了一些实验来说明算法的良好性能NABBL1稀疏信号重建。这些实验都是在Matlab R2010a进行测试。相对误差是用来测量重建信号的质量定义为 在哪里表示和重建信号表示原始信号。
在我们的实验中,我们考虑一个典型的压缩传感的场景,我们的目标是重建一个稀疏信号长度观察。随机是高斯矩阵,其元素生成的形状。正态分布(randn在Matlab中)。在真实的应用程序中,测量通常是被噪声污染;也就是说,,在那里是高斯噪声分布。
我们测试一个体积小信号,;最初的包含随机非零元素。该算法在零点开始,终止时连续两个点的相对变化是足够小;也就是说, 在这个实验中,我们用,,,。线搜索,我们选择,,,。原始信号、有限的测量和重构信号,噪声水平给出了图1。
(一)
(b)
(c)
比较(a)和(c)在图1,我们清楚地看到,最初稀疏信号几乎完全恢复。我们看到,所有的蓝色山峰环绕的红圈,这说明原始信号几乎完全。总之,这个简单的实验表明,我们的算法执行的很好和提供了一个有效的方法来恢复大稀疏非负信号。
我们选择四种不同信号的噪音水平与算法相比NBBL1 [22和扭13在我们的下一个实验。为了测试算法的速度更公平,我们平均五个结果表的列表1。数值结果列在表中1在几秒钟内,我们报告CPU时间(时间)需要对整个重建过程和相对误差(RelErr)。从表1,我们可以看到算法NABBL1比算法快NBBL1和扭曲,和算法的迭代次数NABBL1小于算法NBBL1和扭曲的不同的信号。
从图2,NABBL1通常减少相对误差比NBBL1和扭转整个迭代过程。我们得出这样的结论:NABBL1提供了一个有效的方法来解决从压缩传感和正规化的非光滑问题是与或执行比NBBL1和扭曲竞争。
(一)
(b)
4所示。结论
在本文中,我们提出了一个非单调适应性Barzilai-Borwein算法(NABBL1)求解正则化最小二乘问题起源于备用方案复苏压缩传感。在每个迭代中,生成的搜索方向享有财产,可以很容易地得到了最小化一个本地邻近的二次模型,同时良好的结构规范。数值结果表明,该方法与现有承诺和竞争算法NBBL1和两步是(扭曲)。我们未来的主题是延长NABBL1方法求解矩阵跟踪范数极小化问题在压缩传感或一些极小化问题在计算机断层扫描重建26,27]。
利益冲突
作者宣称没有利益冲突有关的出版。