動機
能量模型要用於計算,還須有可靠的求解方法。不可微懲罰不能單靠寫一條普通駐點方程處理;圖像看似不再變化,也沒有說明距模型最優值多遠。我們需要尊重非光滑結構的更新、合理步長,以及可量度剩餘最優化誤差的證書。
有限圖全變分的對偶變量每條邊只有一個,限制在有界區間內,投影只需截斷;差分及其轉置則是局部運算。因此可用初等有限維分析完整證明算法。以下分開證明目標值下降、迭代點收斂與速率,並明說何種量沒有由同一速率自動控制。精確算術結論不代替浮點或近似線性求解的誤差分析,也不證明成像模型符合某張真實照片。
定義
定義 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
選擇步長
若 且 ,則 ,所以任何正的 都安全。若所用的 超過真實的 ,它便不是下界,所得步長也沒有保證。