动机
能量模型要用于计算,还必须有可靠的求解方法。不可微的惩罚项不能只靠写出一条普通的驻点方程来处理;图像看起来不再变化,也没有说明它离模型最优值有多远。我们需要一种尊重非光滑结构的更新、有依据的步长,以及能够度量剩余优化误差的证书。
有限图全变分的对偶变量每条边只有一个,并限制在有界区间内,投影只需截断;差分及其转置则是局部运算。因此可以用初等的有限维分析完整证明算法。下面分别证明目标值下降、迭代点收敛与速率,并明确指出哪些量没有被同一速率自动控制。精确算术下的结论不能代替浮点运算或近似线性求解的误差分析,也不能证明成像模型符合某张真实照片。
定义
定义 6.1.1
(图全变分能量及其盒形约束对偶)
设 为有向关联矩阵,数据为 ,。定义
对 ,令
强制性与严格凸性保证 有唯一极小点。
由 ,得到鞍点表达式 。固定 ,对 配方求最小值,便得到 。所以每个可行的 都给出原始最小值的一个下界,而最大化对偶值等价于在盒形集合内最小化 ;这一步并未假设最大与最小可以随意交换。
梯度为 ,可取 Lipschitz 常数 。若 ,选 ,从可行初值出发迭代
投影就是把每个坐标截断到 。式中的加号来自梯度本身的负号,这仍是下降而不是上升。没有边时直接取 。若无权图的最大度为 ,则 ,因此 是可以计算的安全步长。更精细的范数估计也许允许更大的步长,但随手挑选的方便数值并不受下面证明的收敛保证。
实现时可以直接循环:由边变量恢复顶点图像,计算它的差分,更新边变量并截断,再用新的边变量恢复图像并计算证书。配对顺序很重要:新对偶与旧图像配对时,一般间隙公式仍然成立,但简化公式中的平方项未必为零。停止条件应依据可行间隙;若要求图像范数误差不超过某个容差,就令间隙不超过该容差平方的一半。达到最大迭代次数仍未满足容差时,应报告证书尚未完成,而不能直接称为收敛。
每个边上的数值都必须连同定义它的方向一起解读。若把一条边反向,差分与该对偶分量同时变号,累积到顶点上的贡献才保持不变。转置不是另一个凭直觉选出的平滑算子,而是由内积严格确定的伴随算子。同一个顶点向量可能由多个不同的边数组累积得到,这正是对偶解未必唯一的原因,并不说明程序一定出错。
初值不必为零,但必须可行,否则初始的对偶值未必是有效下界。若以其他程序给出的边估计作为起点,应先投影再计算证书。恢复图像时必须使用当前全部边值,不能只更新部分像素却仍把公式当作完整的同步步。这里证明的是固定步长、同步投影的方法;改为异步更新或任意的外推加速,就必须另行检验收敛条件。
定理 / 命题
定理 6.1.2
(迭代收敛及对偶目标速率)
若 、、,则整个序列收敛到 在盒形集合上的某个极小点 ,而 收敛到唯一的全变分解 。对任意对偶极小点 及 ,
对偶极小点本身未必唯一。
定理 6.1.3
(可计算间隙及图像误差界)
对任意图像 与可行对偶 ,非负的原始—对偶间隙为
它保证 。取 时平方项消失;沿投影迭代,间隙趋于零,因此可以作为停止证书。
这里的范数界控制的是到所选模型极小点的优化误差,而不是到未知真实图像的复原误差。对偶目标的速率也不直接等于原始—对偶间隙的速率。后者会趋于零,但若要得到同样的定量速率,还须另作论证。
能量容差与图像容差也不同:间隙直接限制能量超出最优值的部分,图像距离则要经过平方根换算。精确方法最终能满足每个严格正的容差,但仅凭对偶目标速率,不能推出这个可计算间隙的统一迭代次数上界。报告中应保留达到的间隙、可行性误差及迭代次数,让读者判断实际完成程度。
概念视角几何
极小点是数据减去一个投影
对偶问题在盒上最小化 ,所以它是在凸多面体 中寻找最接近 的点。因此 ,且
即使有很多 映到 中同一点,到闭凸集的投影仍然唯一;这正是 唯一而对偶极小点未必唯一的几何原因。投影迭代通过盒坐标计算这个投影。
证明思路
证明
(收敛及速率的投影梯度论证)
闭凸集上的投影满足 ,因为沿着从投影点指向任意可行 的线段,距离平方在起点处的单侧导数非负。令 ,利用凸性下界、梯度 Lipschitz 上界及投影不等式,得到
具体地,把 与 相加,再对 代入投影不等式。若 是极小点,左端非负,最后的系数也非负,所以到每个极小点的距离都不增加。逐步相加后距离平方逐项相消;目标单调下降,最后一步的误差不超过前 步误差的平均,于是得到目标速率。
但目标值收敛还不足以证明点收敛。在投影不等式中取比较点 ,可得
该系数严格为正,因此步差平方和有限,步差趋于零。盒形集合紧致,故存在收敛到 的子序列。梯度与投影连续,使极限满足不动点关系,即对所有可行 有 ,由凸性知它是最优点。整个序列到这个极小点的距离单调不增,而子序列的距离趋于零,所以整个序列都收敛。
在对偶最优点,梯度等于 ,其变分不等式说明 在盒内最大化 。逐边来看,它必须等于每个非零差分的符号。再加上 ,这正是原始问题的次梯度最优性条件。这样便证明了原始值与对偶值相等,而不是预先假设强对偶。把二次函数 在任意极小点 处展开,得
由极小点的变分不等式,第一项非负,结合目标速率即得图像范数速率。
证明透视
步长界、盒形集与二次结构在哪里起作用
论证分三个阶段,各自依赖不同的假设。三点不等式结合了 的凸性、Lipschitz 上界和投影不等式;条件 在这里只用来保证系数 非负,于是到每个极小点的距离都不增加,求和后逐项相消,得到 的速率。
有界且下降的目标值会收敛,但仅凭这一点推不出点收敛。取 得到的充分下降不等式使步差平方可和;盒形集合的紧致性给出聚点;梯度与投影的连续性使它成为不动点,从而是极小点。到这个特定极小点的距离单调不增,迫使整个序列收敛到它。整个过程不需要对偶极小点唯一;这一点很重要,因为只要图中含有圈, 就是奇异的。
原始方面的结论来自 在极小点处的精确二次展开:线性项由变分不等式而非负,余项恰为 。这说明每个对偶极小点都恢复出同一图像,并把目标速率以因子二转化为图像速率。
第二个定理只需要代数运算和两个不等式。
证明
(对间隙配方)
配方即可核对间隙等式;其余各边项因 而非负。原始能量的强凸性给出 ,弱对偶给出 ,两者结合即得误差界。在极限最优对处间隙为零,由连续性可知迭代间隙趋于零。
虽然盒形集合使每个迭代点有界,第一个定理中的步长条件仍不能随意去掉。
反例模式
把安全步长加倍会使迭代循环
待检验的说法:既然投影把迭代点留在紧致的盒形集合内,任何正步长都会收敛。取 、、,则 ,用 。从 出发,、,故 。接着 、,故 。迭代点在 与 之间循环,图像在 与 之间交替,间隙分别为 和 ,始终不为零。极小点是 ,对应 。截断前有 ,而截断不会增大到 的距离,所以在此例中每个 都收敛。定理的条件 位于这一范围之内; 则不在。
例题详解
例题 6.1.4
(两像素问题的一步精确解)
取 、、。算子范数的平方为二,所以 ,取 。从零出发,,恢复得 。其差分为一,且对偶分量符号匹配,故间隙为零。原始值为 ,对偶值为 。两值精确相等,就是最优性的证书,与停止时的迭代次数无关。
例题 6.1.5
(非零间隙说明优化尚未完成)
在三像素路径上取 、,使用两个前向差分, 的最大特征值为三。取 、零初值,得 与 。差分为 ,间隙为 。直接计算得 、,所以到未知极小图像的距离不超过 。实际上最优图像为 ,证书为 ,能量为二;它与第一步迭代的平方距离为 ,确实在界内。
例题 6.1.6
(用图的度给出算子范数界)
对任意向量 ,每条边满足 ,求和得 。在路径上,度的上界给出四,而三像素的精确平方范数为三。使用这个界偏于保守,但仍然合法。在大型图像网格上,同一论证可以免去计算代价高昂的最大奇异值,前提是实际的权重和边界处的度确实符合所述的无权图。
求解器还可推广到强凸的去模糊模型 ,其中 。设 、,则 ,对偶值为 。在同一盒形集合上最小化后面的二次部分,其梯度仍是 ,Hessian 为 ,所以前面的投影梯度证明以其算子范数为 照样适用。每次迭代需要一次准确的正定线性求解。只有确认 仍然正定,才可以去掉 ;去噪情形的证明并不允许对奇异矩阵求逆。
常见错误
常见错误
(截断图像,或者朝上坡走)
截断的对象是边上的对偶变量,而不是图像;改为截断图像就是在解另一个问题。更新中的符号写反,则变成在 上做上升。两种错误产生的迭代点看起来仍然合理。实现时应按实际的边界约定检验 ,再检查对偶目标是否下降、间隙是否非负;这些检查不能代替算子之间的一致性。
常见错误
(因为步差很小就停止)
步差很小可能只是因为步长选得过小,不足以证明已接近最优;可行间隙才给出模型内的数值容差。精确算术下间隙非负;浮点运算算出略为负的间隙时,应先排查舍入、配对与算子一致性,而不能解读为优于最优。
总结
有限图全变分具有盒形约束的光滑对偶,投影梯度只需要差分、伴随算子和截断。投影几何给出目标速率,紧致性、步差趋零与距离单调给出整个序列的收敛。最优的边对偶恢复唯一的图像,可计算的间隙控制优化误差。正定的二次拟合项可以把方法推广到复原问题,但证书不控制模型偏差,也不控制到未知真实图像的误差。
练习
练习 6.1.7
(把两像素例题改为 ,用 从零出发,求第一步对偶迭代、恢复的图像及间隙。)
基础
解答(3)
- 1
计算步长及第一步
此时 、。由于 ,第一步为 ,已经可行。
- 2
恢复图像
。
- 3
计算间隙
的差分为零,且 ,故间隙为零。原始值为 ,对偶值为 。
练习 6.1.8
(证明逐坐标截断给出到盒形集合 距离平方最小的点。为什么逐坐标独立截断在这里可行,对欧氏(Euclidean)单位球却不行?)
核心证明
解答(3)
- 1
把坐标分开
对盒形集合,,而约束 只涉及单个坐标,所以最小化问题分解为 个相互独立的标量问题。
- 2
求解标量问题
在 上的极小点:若 ,就是 本身;否则是较近的端点。合起来正是截断。
- 3
与球比较
∎球约束通过 把各坐标联系在一起,各自独立的区间选择未必落在球内。向量在球外时,到球上的投影是沿径向缩放。
练习 6.1.9
(某个可行对的间隙为 ,保证的欧氏图像误差界是多少?这个界是否度量到真实照片的距离?)
基础
解答(2)
- 1
应用间隙界
。
- 2
说明度量的对象
这个界度量的是到该模型精确极小点 的距离。噪声、模糊失配和正则化偏差都可能使该极小点不同于真实图像,而优化证书并不控制这些误差。
练习 6.1.10
(在 正定的去模糊推广中,证明 ,并用该特征值的已知正下界写出安全步长。)
核心
解答(2)
- 1
估计 Rayleigh 商
对任意向量 ,由于 ,有 。 是对称半正定矩阵,其范数就是这个商的最大值。
- 2
选择步长
若 且 ,则 ,所以任何正的 都是安全的。若所用的 超过真实的 ,它就不是下界,所得步长也没有保证。