文档章节

浅谈凸优化问题中的Bregman迭代算法

abcijkxyz
 abcijkxyz
发布于 2016/11/22 16:46
字数 2004
阅读 7
收藏 0
点赞 0
评论 0

        对于搞图像处理的人而言,不懂变分法,基本上,就没法读懂图像处理的一些经典文献。当然,这已经是10年之前的事情了。

         现在,如果不懂得Bregman迭代算法,也就没法读懂最近几年以来发表的图像处理的前沿论文了。国内的参考文献,基本上都是直接引用Bregman迭代算法本身,而对于其原理基本上找不到较为详细的论述。本文简要叙述当前流行的Bregman迭代算法的一些原理。


    

1. 简介

         近年来,由于压缩感知的引入,L1正则化优化问题引起人们广泛的关注。压缩感知,允许通过少量的数据就可以重建图像信号。L1正则化问题是凸优化中的经典课题,用传统的方法难以求解。我们先从经典的图像复原问题引入:

        在图像复原中,一种通用的模型可以描述如下:    

   

         我们目标是从观测到的图像f,寻找未知的真实图像u,u是n维向量空间中的元素,f是m维向量空间中的元素。f 在压缩感知的术语叫做测量信号。 是高斯白噪声其方差为sigma^2。A是线性算子,例如反卷积问题中的卷积算子,压缩感知中则是子采样测量算子。

        

          上述方程中,我们仅仅知道f,其它变量都不知道的。而且这种问题通常情况都是病态的,通过引入正则项可以使之成为良态的。正则化方法假定对未知的参数u引入一个先验的假设,例如稀疏性,平滑性。正则化问题的常见方法Tikhonov方法,它通过求解下面的优化问题:

                                                                                                    

        其中mu是一个大于零的标量,事先设定的常数,用于权衡观测图像f和正则项之间的平衡。双绝对值符号是L2范数。

    

        下面,为了引入Bregman迭代算法,需要对两个重要的概念进行描述。

2.  Bregman距离

            


            注意这个定义,它是对泛函J在u点的subgradient的定义,p点是其对偶空间的中的某一点。subgradient可以翻译为次梯度,子梯度,弱梯度等。等式左边最右边一项是内积运算。如果泛函J是简单的一元函数,则就是两个实数相乘。次梯度有什么好处呢?对于一般的导数定义,例如y=|x|在0点是不可导的,但是对于次梯度,它是存在的。

             

                上面的这个定义就是Bregman距离的定义。对于凸函数两个点u,v之间的Bregman距离,等于其函数值之差,再减去其次梯度点p与自变量之差的内积。要注意的是这个距离不满足对称性,这和一般的泛函分析中距离定义是不一样的。

   

3.  Bregman迭代算法 

        Bregman迭代算法可以高效的求解下面的泛函的最小 

                                   

       


       上式中的第一项J,定义为从X到R的泛函,其定义域X是凸集也是闭集。第二项H,定义为从X到R的非负可微泛函,f是已知量,并且通常是一个观测图像的数据,所以f是矩阵或者向量。上述泛函会根据具体问题的不同具有不同的具体表达式。例如,对于简介中的图像复原啊问题,J(u)就是平滑先验约束,是正则化项;而H则是数据项。



 

     Bregman迭代算法首先是初始化相关的参数为零,再迭代公式u,其左边一项是泛函J的Bregman距离。再来看p点的迭代公式,其最右边一项是泛函H的梯度。

     其迭代一次产生的输出是公式3.2,经过多次的迭代,就能够收敛到真实的最优解。这个证明过程可以参考后面的文献。

     对于具体的问题,泛函3.1定义的具体形式是不同的。例如对于压缩感知使用的基追踪算法,J是L1范数。而对于图像去噪问题,可能就是u的梯度L1范数,同时A也变成了恒等算子了。


4. 线性Bregman迭代算法

    

          Bregman 迭代算法的每一步迭代都要求解泛函4.1的最小值,这一步的计算代价是很高的。线性Bregman迭代的思路是对泛函4.1的第二项进行线性展开,根据矩阵函数的泰勒公式,泛函4.1的第二项可以展开为上面4.2的形式。




         注意,上述公式4.2省略了泰勒公式中二次项。把二次项加上,带入前面基本的Bregman迭代算法公式的第一步,我们得到公式4.3。如果我们计算4.3和4.4中间那个表达式,比较其相同项,很容易得到公式4.4.




         如果我们考虑基追踪算法,则H等于 ||Au - f||^2 /2, 将H的导数带入公式4.4,我们得到公式4.5, 公式4.6是基本Bregman迭代算法的第二步,注意上述4.6公式中u的上标是错的,应该改为 k+1 ,这样才可能得到公式4.7,公式4.8,4.9, 4.10, 4.11都是显而易见的。


          下面我们把4.11和前面定义的Bregman距离带入到4.5里面去,具体如下:



      在上面的推导中,u_k是常量,C是与u_k有关的一个常量,将上式对u求导,由于有绝对值项,所以要分开讨论,得到上面这个分段表达式。进一步整理得到:



             这里,我们定义了一个shrink操作,这个收缩算子很重要,在后面所有的Bregman算法中都有这个操作。根据这个操作,我们导出下面的表达式,并最终把线性Bregman迭代算法总结如下:



5.  Split Bregman 算法

         Split Bregman 算法是另一种高效的算法。我们已经知道,Bregman迭代算法用于求解下面的凸优化问题:

                      


     我们可以把上面的表达式变换为下面的等价形式:




     这一步,看似是多此一举,但是Bregman经过推导,得出了一种高效的迭代算法,分裂Bregman迭代。

     上面的5.2是一个等式约束优化问题,把它转化为无约束优化问题如下:



        上面这个公式中,优化变量多了一个d。做如下的变量替换:


 如果我们对5.5,应用最前面提到Bregman 迭代算法,很容易写出下面的迭代序列:


    式5.9是根据5-6按照Bregman距离展开的结果。式5.7,5.7后面一项是对5-5分别对u,d求其偏导数得到。如果我们对5.7迭代展开,于是得到:


 同理,对于5.8,有

                   

 

注意到式5.11和5.12有一个公共的SIGMA求和项,把它重新定义如下:



    把5.14,5.15带入5.9,具体如下:


          在对5.16的化简中,要注意的是u,d为变量,其它看做常量。

          到此,我们可以给出Split Bregman迭代算法的通用优化步骤:




          对u的迭代,把u看做自变量,其它所有变量看做常数,对d的迭代则是d为自变量,其它变量都是常数。 之所以说是通用迭代优化过程,是因为对于具体的问题,其迭代的具体表达式不同。例如,对于基于各向异性TV的去噪模型,各向同性TV去噪模型,其迭代的具体表达式是不同的。


最后列出本文的参考文献如下:


http://download.csdn.net/detail/celerychen2009/5552551



     

本文转载自:http://www.cnblogs.com/celerychen/archive/2013/06/08/3588196.html

共有 人打赏支持
abcijkxyz
粉丝 60
博文 6196
码字总数 1876
作品 0
深圳
项目经理
从基础知识到实际应用,一文了解「机器学习非凸优化技术」

  选自arXiv   机器之心编译      优化技术在科技领域应用广泛,小到航班表,大到医疗、物理、人工智能的发展,皆可看到其身影,机器学习当然也不例外,且在实践中经历了一个从凸优化...

机器之心
2017/12/30
0
0
关于凸优化

本文结构: 凸优化有什么用? 什么是凸优化? 凸优化有什么用? 鉴于本文中公式比较多,先把凸优化的意义写出来吧,就会对它更有兴趣。 我们知道在机器学习中,要做的核心工作之一就是根据实...

aliceyangxi1987
2017/06/09
0
0
机器学习中牛顿法凸优化的通俗解释

之前,我发过一篇文章,通俗地解释了梯度下降算法的数学原理和推导过程,推荐一看。链接如下: 简单的梯度下降算法,你真的懂了吗? 我们知道,梯度下降算法是利用梯度进行一阶优化,而今天我...

红色石头Will
06/27
0
0
UC Berkeley刘畅流博士:人机交互中的机器人行为设计

  很荣幸回到伯克利和大家分享我在机器人、控制、人机交互方面的研究,以及我们如何设计机器行为,来让它们在日常的工作居家和娱乐中更好地服务、协助人类,与我们合作。   人机交互(H...

中国机器人
04/03
0
0
新颖训练方法——用迭代投影算法训练神经网络

首发地址:https://yq.aliyun.com/articles/72738 作者介绍:Jesse Clark 研究相位恢复的物理学家、数据科学家,有着丰富的建设网站与设计手机应用的经验,在创业公司有着丰富的经验,对创业...

uncle_ll
2017/07/12
0
0
数据+进化算法 等于数据驱动的进化优化?

  【IT168 资讯】数据驱动的进化优化是什么,仅仅就是数据 + 优化算法吗?数据驱动的进化优化适用于哪些应用场景?传统的数学优化方法是否迎来了新一轮的挑战。本文将为您深入浅出的解答以上...

网络大数据
05/16
0
0
AAAI 2018 | 南京大学提出用于聚类的最优间隔分布机

  选自南京大学   作者:张腾、周志华   机器之心编译   参与:刘晓坤、黄小天      在这篇题为《OptimalMarginDistributionClustering》的论文中,南京大学周志华教授、张腾博士...

机器之心
01/09
0
0
数据驱动设计:从学习特征到学习算法

  编者按:人工智能许多问题的本质是搜索一个函数的最优解,那么如何确定一个最佳的搜索策略就成为了研究者们想要解决的问题。本文中,微软亚洲研究院视觉计算组研究员辛博和David Wipf向我...

微软亚洲研究院
02/27
0
0
学界 | 通用智能化:BAIR简述人类-机器人协作新技术

  选自BAIR Blog   作者:Changliu Liu、Masayoshi Tomizuka   机器之心编译   参与:李诗萌、李泽南      在学者的眼中,未来的工业自动化很大程度上需要人类与机器人进行高效率...

机器之心
2017/12/20
0
0
机器学习-12:MachineLN之优化算法

我想说: 其实很多时候应该审视一下自己,知道自己的不足和长处,然后静下来去做一些事情,只有真正静下来才能深下去,只有深下去了才能有所突破,不要被别人的脚步带跑,无论什么时候专而精...

MachineLP
01/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Weblogic问题解决记录

问题:点击登录,页面刷新但是不进去管理界面。解决:删除cookies再登录。

wffger
19分钟前
0
0
RxJava2的错误处理方案

最近使用retrofit2 + rxKotlin2写接口访问,想尽量平铺代码,于是就想到当借口返回的状态码为「不成功」时(比如:code != 200),就连同网络错误一起,统一在onError方法中处理。想法总是好的...

猴亮屏
26分钟前
0
0
程序的调试信息

调试二进制程序时,经常要借助GDB工具,跟踪程序的执行流程,获取程序执行时变量的值,以发现问题所在。GDB能得到这些信息,是因为编译程序时,编译器保存了相应的信息。Linux下的可执行程序...

qlee
49分钟前
0
0
应用级缓存

缓存命中率 从缓存中读取数据的次数与总读取次数的比例,命中率越高越好 java缓存类型 堆缓存 guavaCache Ehcache3.x 没有序列化和反序列化 堆外缓存ehcache3.x 磁盘缓存 存储在磁盘上 分布式...

writeademo
今天
0
0
python爬虫日志(3)find(),find_all()函数

1.一般来说,为了找到BeautifulSoup对象内任何第一个标签入口,使用find()方法。 以上代码是一个生态金字塔的简单展示,为了找到第一生产者,第一消费者或第二消费者,可以使用Beautiful Sou...

茫羽行
今天
0
0
java:thread:顺序执行多条线程

实现方案: 1.调用线程的join方法:阻塞主线程 2.线程池 package com.java.thread.test;public class MyThread01 implements Runnable {@Overridepublic void run() {Syste...

人觉非常君
今天
0
0
ElasticSearch 重写IK分词器源码设置mysql热词更新词库

常用热词词库的配置方式 1.采用IK 内置词库 优点:部署方便,不用额外指定其他词库位置 缺点:分词单一化,不能指定想分词的词条 2.IK 外置静态词库 优点:部署相对方便,可以通过编辑指定文...

键走偏锋
今天
19
0
Git 2.18版本发布:支持Git协议v2,提升性能

Git 2.18版本发布:支持Git协议v2,提升性能Git 2.18版本发布:支持Git协议v2,提升性能 新版本协议的主要驱动力是使 Git 服务端能够对各种 ref(分支与 tag)进行过滤操作。 这就意味着,G...

linux-tao
今天
0
0
python浏览器自动化测试库【2018/7/22-更新】

64位py2.7版本 更新 document_GetResources 枚举页面资源 document_GetresourceText 获取指定url的内容 包括页面图片 下载地址下载地址 密码:upr47x...

开飞色
今天
42
0
关于DCL双重锁失效及解决方案

关于DCL双重锁失效及解决方案 Double Check Lock (DCL)实现单例 DCL 方式实现单例的优点是既能够在需要时才初始化单例,又能够保证线程安全,且单例对象初始化后调用getInstance方法不进行...

DannyCoder
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部