首页
学习
活动
专区
工具
TVP
发布

判断算法收敛的利器:压缩映射原理

导读:图像重建/信号重建的一个通常思路是,用各种各样的正则化去构建一个代价函数,然后再用迭代方法去优化这个代价函数。如何判断一个迭代算法的收敛性是我们经常遇到的理论问题,本文用泛函分析里面压缩映射(contracting mapping)原理给出一个对收敛性的框架性的解释和工具性的指导:

故事的起源是,我上学期读了我老板的关于CT重建里面流行的SART算法收敛性的论文,花了一段时间读懂之后,我自己推了一个naïve的证明同样可以说明这个算法收敛,并且我很骄傲的说,我的证明高中生也可明白。而老板跟我说,这个方法看起来跟压缩映射很像,我当时就简单了解了一下,最近看泛函里面讲到压缩映射才恍然觉得压缩映射真是解释收敛性的利器,虽然目前来说我感觉它可能是用来对付线性问题比较有效。

压缩映射原理:

这里的概念很多,但其实也只是概念而已。X是一个集合/空间,空间上定义一个距离d。定义了距离的空间叫距离空间。在欧式空间里面,距离是坐标平方相加开根号,这里其实把距离的定义放宽了,距离可以有很多种定义形式。空间不一定都是有限维向量空间,也可以是函数空间,函数空间里面两个函数的距离可以被定义成相差取绝对值再积分。完备不用担心,工程遇到的空间基本都是完备的。

证明的思路是(1):先找到不动点 (2)再证明唯一性

(1) 如何找到不动点呢?用图里面的迭代

只要证明x_n是收敛的,映射T是连续的就好啦。那如何证明x_n收敛的呢?下图给出了,由于theta小于1这个条件,在x_n序列里面x_n和x_(n+1)的距离随n增大越来越小了,再根据这个证明x_n是柯西列,就可说明收敛。

简单来说就是,由于theta小于1所以x_n序列是收敛的。

映射T是连续的,也可以由theta小于1得到。

所以这个不动点就找到啦。

(2) 唯一性的思路是,先假设还有一个不动点而最后指出这个假设的不动点和原来的不动点是一样的,就可以说明唯一

不知道大家现在有没有看出压缩映射和迭代收敛有什么联系?其实通常的迭代算法正是给出了映射T,而这个迭代算式如果可以收敛的话也将收敛到映射T的不动点!大家只要验证压缩映射的条件是否成立就行了。如果想详细了解可以看这个视频:

https://www.youtube.com/watch?v=ZD3oLMnzYFQ&list=PLvg2RutqSPrJSTZfA8Y_mK70GC5yvP1t8&index=12

结尾想说,笔者尽自己最大所能将内容做澄清,读者由于缺乏可能的背景而难以仅仅通过一篇公众号文章就对这个话题有很深的了解,我们的目的是埋下一颗种子,这个种子在将来或许能给你一个模糊的暗示,那时再认真调研也不晚。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180501G0FRS300?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券