信号処理?画像処理における凸最适化
?
21 likes?11,873 views
日本オペレーションズ?リサーチ学会「最適化の基盤とフロンティア」研究部会（http://dopal.cs.uec.ac.jp/okamotoy/woo/ 第4回 2015/11/28）の講演スライド（微修正版）
![近接写像の計算
26
Case 1: 凸集合の指示関数 => 凸射影
Case 2: 混合 L1,2ノルム =>グループソフト閾値処理
* => [0, 255]に値を押しこむ
: の所属するグループのインデックス集合](https://image.slidesharecdn.com/wooconvex-160422054145/85/-25-320.jpg)
![収束定理の証明のラフスケッチ (続き)
15
ゼロベクトルを同一ベクトルの差で表現 ＆ diag(γ1, γ2) でスケーリング
元の表記に戻しつつ整理する (左辺の だけ消す)
右辺にかかっている写像の逆はリゾルベントなので
めでたく主-双対解のペアがアルゴリズム1ステップの不動点となる
結局、この1ステップが (x, y) の直積空間において非拡大写像となる
※ ただし、直積空間の計量が前述した正定値行列で歪められている
詳しくは [Condat 2013, JOTA] [Ono+ 2015, IEEE TSP] あたりを参照](https://image.slidesharecdn.com/wooconvex-160422054145/85/-35-320.jpg)
![テクスチャ分離
テクスチャは局所的に繰り返しの構造を持つ
→どの局所ブロックも適切な回転を施すと低ランクとなる
TextureTexture
[Schaeffer+ 2013,
SIAM J. Imag. Sci.]
[Ono+ 2014, IEEE TIP]
Image
指針：
ブロックごとの核ノルムの総和＋異なる方向に繰り返す
テクスチャを分離しながら特徴付ける (最適化はADMM)
38](https://image.slidesharecdn.com/wooconvex-160422054145/85/-37-320.jpg)
![輝度-色差分離型全変動
輝度の変動＝輝度方向の雑音、エッジ?テクスチャ
色差の変動＝色ムラ、細い色変化
→性質が異なるので分けて評価できるようにすべき
[Bresson+ 2008,
Inv. Probl Imag.]
[Ono+, CVPR2014]
指針：
混合L1,2ノルムに線形色変換を合成し、変換後の色空間
で輝度/色差全変動を定義 (最適化は主-双対近接分離法)
39
応用例：画像強調
原画像](https://image.slidesharecdn.com/wooconvex-160422054145/85/-38-320.jpg)
信号処理?画像処理における凸最适化
- 2. 広がる凸最適化応用 3 凸最適化 （非可微分?制約付き） 画像復元 生体信号処理 医用画像処理 圧縮センシング 機械学習 無線通信 衛星/天体画像処理 リモートセンシング コンピュータ ビジョン
- 4. なぜ凸最適化が使われるのか 5 ◆局所最適解＝大域的最適解 ? 最適解を効率的に計算可能 ? 初期値に非依存 ? 問題設計の良し悪しの判定が比較的容易 ◆近接分離最適化 (proximal splitting) ? 所望の信号に対する先験的性質の活用 ? スパース、低ランク、etc… ? 制約条件の取り扱いが比較的容易 ? 信号値のレンジ?部分空間?ノルム球等 ? 次元の大きい問題 (N > 10^4~6)でもOK ? 勾配降下 and/or 近接写像が基本的な手続き ? ヘシアン等の二次以上の情報は不使用 (基本的に O(N^2) 以上はキツい)
- 8. 近接勾配法とは 9 ◆対象とする凸最適化問題 微分可能 (勾配はβ-リプシッツ連続) 近接写像が効率的に計算可能 ◆近接勾配法 (proximal gradient, forward-backward splitting,…) 近接写像の定義 (これ自体が最適化問題を内包) POINT: いくつかの応用上有用な微分できない凸関数に 対して、近接写像の効率的な計算方法が既知 (e.g, L1ノルム)
- 9. スパース信号復元問題 10 ◆観測モデル ◆最適化問題：L1ノルム最小化に基づくスパース信号復元 観測ベクトル 観測過程を 記述する行列 加法性雑音 推定したい信号 仮定：スパース (ほとんどの要素が0/ほぼ0) データ項 スパース項（L1ノルム） ? 目的関数が微分不可能（通常の勾配法では無理） ? L1ノルムの近接写像は簡単に計算可能（後述） →近接勾配法が使える
- 10. 近接勾配法によるスパース信号復元 11 ◆近接勾配法に基づくアルゴリズム (通称 ISTA) L1ノルムの近接写像 prox＝ソフト閾値処理 SoftThresh 要素ごとに絶対値を削る処理＝O(N) で計算可能 ※近接勾配法の一般形式
- 11. 近接勾配法の収束定理 12 ◆アルゴリズムと収束定理 ◆証明のラフスケッチ 劣微分 prox の正体 (一般呼称はレゾルベント） prox の定義に含まれる目的関数を 劣微分すれば容易に確かめられる 目的関数の劣微分が 0 を含む という条件を書き換えていく ? 近接勾配法の１ステップを 施しても動かないベクトルが 最適解という特徴付けを得る
- 12. 近接勾配法の理論的背景 (続き) 13 ◆証明のラフスケッチ (続き) とすると、最適解の集合＝写像 T の不動点集合 ここで、T が非拡大, i.e., であれば、Krasnosel’ski??–Mann Iteration の収束定理 に帰着可能→実際に非拡大になる (割愛) ※ proxγg と I-γ?f は f, g が凸であれば非拡大 (γ は?fのリプシッツ定数の逆数の二倍以下) 非拡大写像同士の合成写像も非拡大 → も非拡大 ← 近接勾配法の1ステップ 非拡大写像 T が 、点列 が を満たすと仮定する．このとき、 で生成され る点列 は の一点に (弱) 収束する．
- 13. 础顿惭惭による画像復元
- 14. 画像復元問題 15 例：ぼけ除去 (deblurring) +*Blur= ：ぼけ作用素 観測データ ◆観測モデル 劣化を表す行列 未知の画像 (式の上ではベクトルとして扱う) センサノイズ等
- 15. 凸最適化問題として定式化 16 全変動 (画像は滑らか) データ項 ◆最適化問題 (全変動最小化に基づく画像復元) 画素値の取りうる幅 (box constraint) ? D は隣り合う画素 (縦と横) との差分計算 ? ||?||1,2 は混合 L1,2 ノルム (サブベクトルごと にL2ノルムを計算した後にその総和をとる) ◆ひとつめの例 (スパース信号復元) よりも複雑な問題 ? 微分できない関数と行列の合成 (全変動) ? 制約条件の存在 → 近接勾配法では解けないのでより広いクラスの問題 を解ける ADMM を用いる ※観測モデル：
- 16. ◆対象とする凸最適化問題 ADMMとは 二次関数 近接写像 15 ※ d は双対変数に相当 ◆ADMM (Alternating Direction Method of Multipliers) 近接写像が効率的に計算可能二次関数 フルカラムランク行列
- 18. 式変形 (1/4) 19 指示関数 (indicator function) を導入 → 制約条件を目的関数表現
- 19. 式変形 (2/4) 20 ? 二次関数以外の項の変数を分離する ? つじつま合わせは线形制约
- 23. 各ステップの計算 (1/3) 24 に注意すると Gがフルカラムランク => 逆行列計算 ? BCCB構造→2DFFTによる高速計算 O(NlogN) ? それ以外の場合→共役勾配法等を用いる
- 24. 計算 (2/3) 25 に注意すると prox の計算を ごとに分离できる
- 25. 近接写像の計算 26 Case 1: 凸集合の指示関数 => 凸射影 Case 2: 混合 L1,2ノルム =>グループソフト閾値処理 * => [0, 255]に値を押しこむ : の所属するグループのインデックス集合
- 26. 計算 (3/3) 27
- 28. ADMMの収束定理 29 ◆最適化問題 ◆アルゴリズム ◆収束定理 ? f, g が凸関数、ρ>0 ? G がフルカラムランク ? Lagrangian の鞍点が存在 ADMMの収束も非拡大写像の不動点的解釈が可能 (割愛)
- 30. 础顿惭惭による画像復元では… 31 ◆最適化問題 (全変動最小化に基づく画像復元) ※観測モデル： ◆ADMMで解く際に出てくる subproblem Φ の構造によっては共役勾配法等を用いる必要がある → 内部ループによる計算時間増大?収束の不安定化 Q: 逆行列計算そのものを避けられるアルゴリズムは？ A: 主-双対近接分離法
- 31. ◆対象とする最適化問題 主-双対近接分離法とは 15 ※ y は双対変数 ◆主-双対近接分離法 (primal-dual splitting) 微分可能 (勾配はβ-リプシッツ連続) 近接写像が効率的に計算可能近接写像が効率的に計算可能 h の凸共役の近接写像→ h の近接写像を用いて表現可能 Moreau’s Identity POINT：f の勾配、g, h の近接写像、 の計算のみ
- 33. ◆最適化問題 主-双対近接分離法の収束定理 15 ◆アルゴリズム ◆収束定理 ? f, g, h が凸関数 ( f は微分可能) ? ?f が β-リプシッツ連続 ? ? ※ ri は相対的内点
- 34. 主問題 (対象の最適化問題) 収束定理の証明のラフスケッチ 15 双対問題 主問題?双対問題の最適解の集合をそれぞれ Sp, Sd とし、両方の目的関数 を劣微分して整理すると、以下の特徴付けを得る (1) の右辺を区分行列的に表現 ＆ 左辺のゼロベクトルに正定値行列をかける
- 35. 収束定理の証明のラフスケッチ (続き) 15 ゼロベクトルを同一ベクトルの差で表現 ＆ diag(γ1, γ2) でスケーリング 元の表記に戻しつつ整理する (左辺の だけ消す) 右辺にかかっている写像の逆はリゾルベントなので めでたく主-双対解のペアがアルゴリズム1ステップの不動点となる 結局、この1ステップが (x, y) の直積空間において非拡大写像となる ※ ただし、直積空間の計量が前述した正定値行列で歪められている 詳しくは [Condat 2013, JOTA] [Ono+ 2015, IEEE TSP] あたりを参照
- 36. 最后に画像処理応用を少し宣伝
- 37. テクスチャ分離 テクスチャは局所的に繰り返しの構造を持つ →どの局所ブロックも適切な回転を施すと低ランクとなる TextureTexture [Schaeffer+ 2013, SIAM J. Imag. Sci.] [Ono+ 2014, IEEE TIP] Image 指針： ブロックごとの核ノルムの総和＋異なる方向に繰り返す テクスチャを分離しながら特徴付ける (最適化はADMM) 38
- 38. 輝度-色差分離型全変動 輝度の変動＝輝度方向の雑音、エッジ?テクスチャ 色差の変動＝色ムラ、細い色変化 →性質が異なるので分けて評価できるようにすべき [Bresson+ 2008, Inv. Probl Imag.] [Ono+, CVPR2014] 指針： 混合L1,2ノルムに線形色変換を合成し、変換後の色空間 で輝度/色差全変動を定義 (最適化は主-双対近接分離法) 39 応用例：画像強調 原画像
- 39. まとめ 40 ◆今回紹介した近接分離系の凸最適化アルゴリズム ? 近接勾配法 (proximal gradient, forward-backward splitting) 特徴：適用範囲は狭めだが大幅な加速が可能 (文献参照) ? ADMM (Alternating Direction Method of Multipliers) 特徴：適用範囲が広く収束もそれなりに速い ? 主-双対近接分離法 (primal-dual splitting) 特徴：適用範囲が広く逆行列計算を回避できるが収束は遅め (計量のせい) ? 近接写像と勾配降下を基本骨子とするアルゴリズム → L1ノルムなどの応用上有用な非可微分凸関数を扱える → 画像などの高次元変数でも現実的な計算量を担保 → 制約条件の扱いも比較的自由 ? 全て Krasnosel’ski??–Mann Iteration に帰着可能 → 非拡大写像の不動点的解釈に基づく統一的な収束原理 POINT
- 40. 参考文献 (1/4) 41 ◆近接勾配法 (proximal gradient, forward-backward splitting) 1. G. B. Passty, “Ergodic convergence to a zero of the sum of monotone operators in Hilbert space,” J. Math. Anal. Appl., 1979. (原著) 2. G. Chen & R. T. Rockafellar, “Convergence rates in forward–backward splitting,” SIAM J. Optim., 1997. (収束レート解析) 3. P. L. Combettes & V. R. Wajs, ”Signal recovery by proximal forward–backward splitting,” SIAM Multiscale Model. Simul., 2005. (更なる理論的整備) 4. A. Beck & M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM J. Imag. Sci., 2009. (通称 FISTA, Nesterov の optimal gradient を融合) 5. M. Yamagishi & I. Yamada, “Over-relaxation of the fast iterative shrinkage- thresholding algorithm with variable stepsize,” Inverse Probl., 2011. (FISTA のス テップサイズ拡張) 6. I. Daubechies et al., “An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,” Comm. Pure Appl. Math., 2004. (スパース復 元応用) 7. J. Duchi & Y. Singer, “Efficient online and batch learning using forward- backward splitting,” J Mach. Learn. Res., 2009. (機械学習応用)
- 41. 参考文献 (2/4) 42 ◆ADMM (Alternating Direction Method of Multipliers) 1. D. Gabay & B. Mercier, “A dual algorithm for the solution of nonlinear variational problems via finite elements approximations,” Comput. Math. Appl., 1976. (原著) 2. J. Eckstein & D. P. Bertsekas, “On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators,” Math. Program., 1992. (Dougal-Rachford splittingに基づく導出と理論的整備) 3. B. He & X. Yuan “On the O(1/n) Convergence Rate of the Douglas–Rachford Alternating Direction Method,” SIAM J. Numer. Anal., 2012. (収束レート) 4. S. Boyd et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., 2011. (分散最適化?機械学習適用とレビュー) 5. J. Eckstein & W. Yao, “Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives,” Pac. J. Optim., (to appear & available online). (非拡大写像の不動点的解釈) 6. M. Afonso et al. “An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems,” IEEE Trans. Image Process., 2011. (画像復元応用) 7. S. Ono et al., “Cartoon-texture image decomposition using blockwise low-rank texture characterization,” IEEE Trans. Image Process., 2014. (画像分離応用)
- 42. 参考文献 (3/4) 43 ◆主-双対近接分離法 (primal-dual splitting) 1. A. Chambolle & T. Pock, “A first-order primal-dual algorithm for convex problems with applications to imaging,” J. Math. Imag. Vis., 2011. (原著、少し限 定的な形) 2. L. Condat, “A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms,” J. Optim. Theory Appl., 2013. (原著、今回紹介した形) 3. R. Bo? & E. Csetnek, “On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems,” Optimization, 2015. (収束レート) 4. S. Ono and I. Yamada, “Decorrelated vectorial total variation,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), 2014. (カラー画像復元応用) 5. S. Ono, M. Yamagishi, and I. Yamada, “A sparse system identification by using adaptively-weighted total variation via a primal-dual splitting approach,” in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2013. (適応信号処理 応用) 6. S. Ono and I. Yamada, “Hierarchical convex optimization with primal-dual splitting,” IEEE Trans. Signal Process., 2015. (主-双対解集合から所望の解を選出す る階層型凸最適化の提案)
- 43. 参考文献 (4/4) 44 ◆その他、関係する and/or 役立つと思われる文献?書籍 1. J. J. Moreau, “Fonctions convexes duales et points proximaux dans un espace Hilbertien,” (in French) C. R. Acad. Sci. Paris Ser. AMath., 1962. (近接写像初出) 2. H. H. Bauschke & P. L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces. Springer, 2011. (凸解析と単調写像理論について体系的 にまとめた良書、議論は基本的に無限次元ヒルベルト空間で展開) 3. P. L. Combettes & J.-C. Pesquet, “Proximal splitting methods in signal processing,” in Fixed-Point Algorithm for Inverse Problems in Science and Engineering, Springer-Verlag, 2011. (近接分離系の手法のレビュー、近接写像が効 率的に計算可能な凸関数のリスト) 4. I. Yamada et al., “Minimizing the Moreau envelope of nonsmooth convex functions over the fixed point set of certain quasi-nonexpansive mappings,” in Fixed-Point Algorithm for Inverse Problems in Science and Engineering, Springer- Verlag, 2011. (いくつかの近接分離系の手法を非拡大写像の不動点的視点から解説) 5. S. Ono & I. Yamada, “Signal recovery with certain involved convex data-fidelity constraints,” IEEE Trans. Signal Process., 2015. (近接分離系の手法では扱えないデー タ忠実性制約が課された信号復元問題を解く最適化アルゴリズムの提案)