Deep Unrolling ~Learned ISTA (LISTA)~

Deep Unrolling ~ Learned ISTA (LISTA) ~ CTO室 長山知司

概要 • Deep Unrolling (あるいはDeep Unfolding) – 反復法による最適化アルゴリズムをループ展開し、 Deep Neural Network (DNN) のように扱う手法 • 最適化アルゴリズム：ISTA, ADMM, Primal-Dual Splitting, etc… – 通常の DNN より説明性が高い • ニューラルネットの推論 = スパースコーディングとして解釈可能 • 性能の保証が比較的容易 – 少数のパラメータで高い性能を発揮 • 本スライドの目的 – スパースコーディングの基礎を概説 – 代表的な Deep Unrolling 手法の LISTA を紹介 1

I. スパースコーディングとISTA 2

問題設定 • 画像逆問題 – モデルの出力から入力を推定する問題 • ノイズ除去、ボケ除去、超解像など – 一般に劣決定 → 適切な解が一意に定まらない • 解の選択に追加の基準が必要 順問題（生成） （生成）モデル 生成モデルの仮定: ノイズ 𝑤 𝑦 = 𝐻𝑥 + 𝑤 ダウンサンプル 𝑥 : 原画像（入力） 𝑦 : 観測画像（出力） 𝐻 : 線形観測過程 𝑤 : 加法的ノイズ 観測過程 𝐻 原画像 𝑥 （入力） 3 + 観測画像 𝑦 （出力） 逆問題（推定） 逆問題の例（超解像）

辞書ベースのスパースモデリング • 仮定（原画像の事前分布） – 行列 𝐷 が存在し、 𝑥 は 𝐷 の列ベクトルの少数の線形結合で 表現可能（スパース表現） • 𝑥 = 𝐷𝑧 s. t. 𝑧 0 ≤ 𝑁 ∈ ℕ • 𝐷 を辞書、 𝑧 を表現ベクトルと呼ぶ 0 𝑐1 𝑑0 𝑑1 𝑑2 ⋯ 𝑑𝑀−2 • 辞書の選択 𝑑𝑀−1 0 ⋮ 0 𝑐𝑀−1 – 良い辞書 𝐷 の性質 1. 原画像 𝑥 をスパースに表現可能 2. 列ベクトル {𝑑𝑚 } の要素間の内積が小さい 𝐷 = [𝑑0 , 𝑑1 , … , 𝑑𝑀−1 ] 𝑧 – 辞書設計（ウェーブレットなど）、辞書学習（K-SVDなど）の二種に大別 4

辞書の例（辞書設計） • 離散コサイン変換（DCT）* 非ゼロ要素が 一箇所に集中 – 自然画像の周波数成分は 低周波に集中する性質を利用 DCT 原画像 𝑥 分布は不変 周波数領域 DCT ノイズ 𝑤 （ガウシアン） 周波数領域 （ガウシアン） （表現ベクトル） 8x8 DCT基底** * 古典的手法。過完備な辞書に性能で劣るため非実用的 （列ベクトル {𝑑𝑚 } に対応） ** 右側の実験で使ったDCTの基底とは異なる 5

表現ベクトルの推定モデル（スパースコーディング） • 𝑙0 ノルム正則化 – 最適化問題として定式化 1 推定モデル（𝑙0 ノルム正則化）: 2+𝜆 𝑧 , 𝑧 Ƹ = Argmin 1/2 𝐴𝑧 − 𝑦 𝑧 0 ቊ 𝑥ො = 𝐷 𝑧Ƹ 𝐴 = 𝐻𝐷 • LASSO 𝑙0 ノルム（ ⋅ 0 ） – 𝑙0 ノルム正則化問題を直接解くのは非現実的（NP-hard） – 凸緩和問題で近似（𝑙1 ノルム正則化 → LASSO） 推定モデル（LASSO）: 2+𝜆 𝑧 , 𝑧 Ƹ = Argmin (1/2) 𝐴𝑧 − 𝑦 𝑧 1 ቊ 𝑥ො = 𝐷 𝑧Ƹ 6 𝐴 = 𝐻𝐷 𝑙1 ノルム（ ⋅ 1 ）

スパースコーディングのアルゴリズム（ISTA） • Iterative Shrinkage/Thresholding Algorithm (ISTA) – LASSO を効率的に解く反復アルゴリズム – 勾配降下と soft-shrinkage を交互に実行 • soft-shrinkage 𝑆𝜏𝜆 𝑧 ≔ sgn 𝑧 ⋅ max( 𝑧 − 𝜏𝜆, 0) 𝑆𝜏𝜆 𝑧 −𝜏𝜆 𝜏𝜆 𝑧 – 初期値に依らず最適解に収束 soft-shrinkage 𝑆𝜏𝜆 • (証明: Appendix) アルゴリズム: ISTA −2 • 初期値 𝑧 0 を設定し、 𝑘 ← 0、 𝜏 ∈ 0, 2𝜎max とする（𝜎max : 𝐴 の最大特異値） • 終了条件を満たすまで以下の更新式を 𝑘 について反復: 𝑧 𝑘+1 ← 𝑆𝜏𝜆 𝑧 𝑘 − 𝜏𝐴𝑇 𝐴𝑧 𝑘 − 𝑦 7

Fast ISTA (FISTA) • ISTAの収束レート改善版[4] – ステップサイズ 𝜏 を調整し収束レート 𝑂 1/𝑘 → 𝑂 1/𝑘 2 を達成 アルゴリズム: FISTA 2 , +∞ とする。 • 初期値 𝑧 (0) を設定し、 𝑘 ← 0、𝑣 0 ← 𝑧 0 、𝜏0 ← 1、𝐿 ∈ 𝜎max • 終了条件を満たすまで以下の更新式を 𝑘 について反復: 𝑧 𝑘+1 ← 𝑆𝜆/𝐿 𝑣 𝑘 − 𝐿−1 ⋅ 𝐴𝑇 𝐴𝑣 𝑘 − 𝑦 𝜏𝑘+1 ← 1 + 1 + 4𝜏𝑘2 / 2 𝑣 𝑘+1 ← 𝑧 𝑘+1 + 𝜏𝑘 − 1 /𝜏𝑘+1 ⋅ 𝑧 𝑘+1 − 𝑧 𝑘 8

適用例: ボケ除去[4]（1/2） • シミュレーションの生成モデル – 線形観測過程 𝐻: ガウスボケ • フィルタサイズ: 9x9 • 分散: 4 – ノイズ 𝑤: ガウシアン • 分散: 10−3 • ISTA/FISTAパラメータ – 辞書 𝐷: 2D-Haar ウェーブレット – 正則化項 𝜆: 2 × 10−5 原画像と観測画像 ボケ除去画像 （上段: ISTA, 下段: FISTA） 引用: [4, Figure 1 & Figure 2] 9

適用例: ボケ除去[4]（2/2） • 収束速度 – 目的関数 𝐹 の最小値との差 𝐹 𝑧 𝑘 − 𝐹 𝑧 ∗ を比較 • 𝑧 ∗ は 𝐹 の最適解 – FISTA は同反復数の ISTA より非常に速く収束 • テスト画像において、反復数 𝑘 = 200 における FISTA の関数値 𝐹 𝑧 𝑘 ISTAで達成するためには 𝑘 > 1100 の反復が必要[4] 𝐹 𝑧𝑘 テスト画像 − 𝐹 𝑧∗ 引用: [4, Figure 3 & Figure 5] 10 を

II. Learned ISTA (LISTA) 11

（復習）(F)ISTAによる画像逆問題の一般解法 • 処理フロー 観測画像 – Stage 1: 辞書の構築 1. 原画像 𝑥 を十分スパースに表現する辞書 𝐷 を設計 or 学習 𝑦 𝐴𝑇 – Stage 2: スパースコーディング 𝑧 (0) 1. 観測行列 𝐻 を推定し 𝐴 = 𝐻𝐷 とする 2. 推定表現ベクトルの初期値 𝑧 を適切に設定 3. ステップサイズ 𝜏 と 正則化係数 𝜆 を設定 4. (F)ISTA を適用し推定表現ベクトル 𝑧Ƹ を得る 5. 推定画像を 𝑥ො = 𝐷 𝑧Ƹ とする 0 12 𝜏 𝜆 𝐴 (F)ISTA 𝑧Ƹ 𝐷 推定画像 𝑥ො

(F)ISTA の課題 • 推論（スパースコーディング）の処理速度 – 通常の (F)ISTA は、推定表現ベクトル 𝑧 (𝑘) の変化量が 十分小さくなるまで更新を繰り返すので、反復回数の見積もりが不可能 • 経験的に、十分な精度を達成するためには最低でも数十回は必要 – 許容誤差を狭めると反復回数が急激に増大 • FISTA の場合、目的関数の許容誤差 𝜀 以下を達成する 反復回数の下限はおよそ 𝑘 ∝ 𝜀 −1 つまり、許容誤差を 1/2 に変更すると、必要な反復回数が2倍になる – 以上の理由により、リアルタイム処理には不適 13

処理速度改善のアイディア • Truncated ISTA – 更新式の反復を固定回数で打ち切る – ループ展開しフィードフォワード構造化（Unrolling） – （当然ながら）推論精度は悪化 • 反復回数とのトレードオフ 𝑧 (𝑘) ISTA 𝑧 𝑧 𝑧∗ ISTA Iter. 0 ISTA Iter. 𝑘 𝑧∗ 展開&打切 𝜏𝐴𝑇 𝑦 𝑧 𝑘+1 ← 𝑆𝜏𝜆 = 𝑆𝜏𝜆 ISTA 𝑧 𝑘 − 𝜏𝐴𝑇 𝐴𝑧 𝑘 − 𝑦 𝑧𝑘 Id − 𝜏𝐴𝑇 𝐴 𝑧 𝑘 − 𝜏𝐴𝑇 𝑦 14 Id − 𝜏𝐴𝑇 𝐴 𝑧𝑘

学習スキームの導入 • Recurrent Neural Network (RNN) との類似性 – （Affine 変換 + 非線形関数）の構造が ISTA と共通 𝑥∗ • 単純な ReLU ベース RNN との比較（図右下） 𝑧𝑘 – Truncated ISTA を RNN のように学習すれば 少ない反復回数で良い推論が可能になるのでは？ 𝑧 ISTA Iter. 0 ISTA Iter. 𝑘 𝑧∗ 𝑧 𝑥𝑘 RNN Iter. 0 RNN Iter. 𝑘 𝜏𝐴𝑇 𝑦 𝑧𝑘 𝑧∗ 𝑏 Id − 𝜏𝐴𝑇 𝐴 𝑧𝑘 𝑧 𝑘+1 ← 𝑆𝜏𝜆 ISTA Id − 𝜏𝐴𝑇 𝐴 𝑧 𝑘 − 𝜏𝐴𝑇 𝑦 𝑧𝑘 𝑊 RNN 𝑧 𝑘+1 ← ReLU 𝑊𝑧 𝑘 + 𝑏 15 𝑘 𝑧𝑘

Learned ISTA（LISTA）（1/3） • モデル概要 – パラメータを変換しバックプロパゲーションで学習 • 𝑊𝑠 ← Id − 𝜏𝐴𝑇 𝐴, 𝑊𝑒 ← 𝜏𝐴𝑇 , 𝜃 ← 𝜏𝜆 に対応 • 辞書 𝐷 は事前に構築済みのものを利用 • 𝑊𝑠 , 𝑊𝑒 は独立変数として扱う – (vanilla) ISTAは Id − 𝑊𝑠 ∝ 𝑊𝑒 𝑊𝑒𝑇 の制約 Layer 0 Layer 𝐾 − 1 𝑧0 𝑊𝑠 𝑊𝑠 𝑆𝜃 ⋅ 𝑊𝑒 𝑦 𝑊𝑒 𝑦 𝑊𝑒 𝑆𝜃 ⋅ 𝑊𝑒 𝑦 𝐾-layer LISTA architecture 𝑧 𝑘+1 = 𝑆𝜃 𝑊𝑆 𝑧 𝑘 + 𝑊𝑒 𝑦 16 Enc. Dec. 𝑧𝐾 𝐷 𝑥ො

Learned ISTA（LISTA）（2/3） • 学習アルゴリズム[5] – バックプロパゲーション – 𝑆𝜃 (𝑧) は 𝑧 = ±𝜃 を除き微分可能 – パラメータ 𝑊𝑠 , 𝑊𝑒 , 𝜃 は 全レイヤーで共有 Layer 𝑘 𝑧𝑘 𝑊𝑠 𝑆𝜃 ⋅ 𝑧 𝑘+1 𝑊𝑒 𝑦 𝑦 17 アルゴリズム: LISTA back-propagation • 入力: forward の 𝑧 𝑘 、𝐵 = 𝑊𝑒 𝑦、 𝐶 𝑘 = 𝐵 + 𝑊𝑠 𝑧 𝑘−1 、 最適表現ベクトル 𝑧 ∗ • 出力: パラメータの変量 𝛿𝑊𝑒 , 𝛿𝑊𝑠 , 𝛿𝜃 • 初期値: 𝛿𝐵 = 0, 𝛿𝑊𝑠 = 0, 𝛿𝜃 = 0, 𝛿𝑧 𝐾 = 𝑧 𝐾 − 𝑧 ∗ • for 𝑘 in 𝐾 to 1 do • 𝛿𝐶 𝑘 = 𝑆𝜃′ 𝐶 𝑘 ۨ 𝛿𝑧 𝑘 • 𝛿𝜃 = 𝛿𝜃 − sgn 𝐶 𝑘 ۨ 𝛿𝐶 𝑘 • 𝛿𝐵 = 𝛿𝐵 + 𝛿𝐶 𝑘 • 𝛿𝑊𝑠 = 𝛿𝑊𝑠 + 𝛿𝐶 (𝑘) 𝛿𝑧 𝑘−1 𝑇 • 𝛿𝑧 𝑘−1 = 𝑊𝑠𝑇 𝛿𝐶 𝑘 • end for • 𝛿𝐵 = 𝛿𝐵 + 𝑆𝜃′ 𝐵 ۨ 𝛿𝑧 0 • 𝛿𝜃 = 𝛿𝜃 − sgn 𝐵 ۨ 𝑆𝜃′ 𝐵 𝛿𝑧 0 • 𝛿𝑊𝑒 = 𝛿𝐵𝑦 𝑇 , 𝛿𝑦 = 𝑊𝑒𝑇 𝛿𝐵

Learned ISTA（LISTA）（3/3） • 性能評価 – エンコーダの予測符合誤差は同反復数（=レイヤー数）の FISTAより非常に早く減少[5] • データセットの画像からパッチをランダムに切り出し、 最適な表現ベクトルと推論結果との二乗誤差を比較 • 学習済み LISTA の 1 iter. は FISTA の 18 iter. (𝑚 = 100) or 35 iter. (𝑚 = 400) Log と同等の性能 scale データセット名 Berkeley image database パッチサイズ 10x10 辞書の列ベクトル数（𝑚） （青）400, （赤）100 初期辞書（𝐷） 確率的座標降下法で学習 観測過程（𝐻） 単位行列（𝐴 = 𝐷） 18 引用: [5, Figure 3.]

LISTAの応用例: 単一画像超解像[6]（1/4） • Sparse Coding based Network (SCN) – 入力を bicubic で拡大し、LISTA ベースのネットワークで補正するモデル – パッチごとに LISTA レイヤーを適用 & 再合成 – Soft-thresh. パラメータ 𝜃 を学習しやすくなるように構造を修正（図下） パッチ切り出し 辞書（事前学習済み） 学習可能な パラメータ行列 引用: [6, Figure 2] 19 パッチ結合

LISTAの応用例: 単一画像超解像[6]（2/4） • Cascade of SCN (CSCN) – 低倍率の（SCN + bicubic）サブネットワークをカスケード接続し 高倍率のネットワークを実現 • 一般に高倍率のサブネットワーク単体より高性能 – 各サブネットワークごとに Loss（MSE）を計算 • モデル全体の Loss はそれらの総和 引用: [6, Figure 4] 20

LISTAの応用例: 単一画像超解像[6]（3/4） • 性能評価実験 – 当時（2015 年）の SotA と PSNRで比較 – どのデータセットでも 0.2~0.5 dB 程度改善 – モデルサイズも小さい • パラメータ数はPSNR最大の他モデル（CNN-L）の 20% 程度[6] 引用: [6, Table 2] * CSCN-MV: 辞書 𝐷𝑥 の学習にデータ拡張（反転, 回転）したパッチを使った CSCN 21

LISTAの応用例: 単一画像超解像[6]（4/4） • カラー画像超解像実験 – スパースコーディング（SC）と SRCNN（CNN）とで視覚評価 – 境界付近のテクスチャがシャープ – 他手法と比べてリンギングが 目立たない 引用: [6, Figure 8] 22

III. 論文紹介 23

LISTA-CP[7] （1/3） • タイトル – X. Chen, et al., “Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds” (2018) • 概要 – パラメータをレイヤー間で独立化した LISTA の収束性について解析 • 𝑊𝑠 , 𝑊𝑒 , 𝜃 → 𝑊𝑠 𝑘 𝑘 , 𝑊𝑒 , 𝜃 𝑘 0≤𝑘<𝐾−1 に変更 – 重み行列を変更した LISTA を提案（LISTA-CP） • 他に 2 種類提案（LISTA-SS, LISTA-CPSS） – 本スライドでは割愛 – 提案手法が線形収束することを理論的に証明 • ISTA, FISTA の劣線形収束よりも早い 24

LISTA-CP[7] （2/3） • 提案アルゴリズム（LISTA-CP） – 重み行列 𝑊𝑒 • 𝑊𝑆 𝑘 𝑘 (𝑘) , 𝑊𝑆 のパラメータを結合 = Id − 𝑊 𝑘 𝐴, 𝑊 𝑘 ≔ 𝑊𝑒 𝑇 𝑘 𝑧𝑘 𝐴 𝑊𝑘 𝑆𝜃 𝑘 ⋅ LISTA-CP (Layer 𝑘) 生成モデルのノイズが有界かつ十分にスパースな最適解 𝑧 ∗ が存在するとき、 が存在し、任意の 𝑘 について以下が成立: 𝑧 𝑘 − 𝑧 ∗ ≤ 𝐵 exp −𝑐𝑘 + 𝐶 もし、ノイズが無いならば以下が成立（すなわち 𝑧 𝑘 は線形収束）: 𝑧 𝑘 − 𝑧 ∗ ≤ 𝐵 exp −𝑐𝑘 ここで、 𝐵, 𝑐, 𝐶 は生成モデルに依存する定数 25 𝑧 𝑘+1 𝑦 𝑦 LISTA-CPの収束レート [7,Theorem 2] パラメータ 𝑊 𝑘 , 𝜃 𝑘 𝑇

LISTA-CP[7] （3/3） • シミュレーション – 表現ベクトルの近似性能評価 • 推論結果 𝑧Ƹ と Ground Truth 𝑧 ∗ の 正規化 MSE (NMSE) で比較 • 𝑧 ∗ の非ゼロ要素の位置は Bernoulli 分布から生成し、値はガウス分布からサンプル • 行列 𝐴 は i.i.d. ガウス分布で生成後、列ごとに 𝑙2 正規化 – (vanilla) LISTA よりも安定し、やや高速に収束 行列 𝐴 のサイズ（𝑁 × 𝑀） 250 x 500 レイヤー数（𝐾） 16 テストセット数 1000 引用：[7, Figure 3] 26

Analytic LISTA (ALISTA)[8] （1/3） • タイトル – J. Liu, et al., “ALISTA: Analytic Weights are as Good as Learned Weights in LISTA” (2019) • 概要 – LISTA-CP[7]の発展型 – LISTA の収束レートは線形より改善できないことを証明（線形収束が最良） – パラメータ数を削減した LISTA を提案（TiLISTA） – 線形収束を達成する TiLISTA の重みは、辞書だけで 解析的に決定できると主張（ALISTA） 27

Analytic LISTA (ALISTA)[8] （2/3） • TiLISTA – LISTA-CP の重み行列 𝑊 𝑘 を分解（𝑊 𝑘 = 𝛾 𝑘 𝑊） • 𝛾 𝑘 : スカラー（学習パラメータ）、𝑊: 各レイヤーで共通の行列 • ALISTA – 𝐴 との相互コヒーレンス 𝜇෤ を最小化する重み 𝑊 を選んだ TiLISTA • 𝜇: ෤ それぞれの列ベクトルの相互相関の最大値 • 𝑊 ∈ argmin𝑊 𝑊 𝑇 𝐴 2𝐹 s. t. 𝑤𝑚 , 𝑎𝑚 = 1 ∀𝑚（𝑤𝑚 , 𝑎𝑚 : それぞれの列ベクトル） 𝑧𝑘 𝐴 - 𝛾 𝑘 𝑊𝑇 𝑆𝜃 ⋅ 𝑧 𝑘+1 𝑦 𝑦 TiLISTA / ALISTA Layer 𝑘 28

Analytic LISTA (ALISTA)[8] （3/3） • シミュレーション – 表現ベクトルの近似性能評価 • 「LISTA-CP」のスライドと等価な条件で実験 – 収束速度は LISTA-CPSS（LISTA-CPの改良版）とほぼ同等 • 実数パラメータ数は 𝑂(𝐾𝑁𝑀 + 𝐾) → 𝑂(𝐾) と大幅に削減 行列 𝐴 のサイズ（𝑁 × 𝑀） 250 x 500 レイヤー数（𝐾） 16 テストセット数 1000 引用：[8, Figure 1] 29

サーベイ[9]（1/1） • タイトル – V. Monga, et al., “Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing” (to be appeared) • 概要 – 信号処理・画像処理応用の網羅的なサーベイ • 本スライドのトピックの多くはこの文献を参考 – LISTA に加え、各種最適化アルゴリズムの Unrolling Methodを紹介 • ADMM, NMF, PDHG, etc. – 類似手法との関連性や近年のトレンドについて記載 30

参考文献 • 書籍 – [1] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed. Springer International Publishing, 2017. – [2] A. Beck, First-Order Methods in Optimization. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. – [3] M. Elad and 玉木徹, スパースモデリング : l1/l0ノルム最小化の基礎理論と画像処理への応用. 共立出版, 2016. • 学術論文 – [4] A. Beck and M. Teboulle, “A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems,” SIAM J. Imaging Sci., vol. 2, no. 1, pp. 183–202, 2009, doi: 10.1137/080716542. [Online]. Available: http://epubs.siam.org/doi/10.1137/080716542. [Accessed: 26-Jan-2020] – [5] K. Gregor and Y. LeCun, “Learning fast approximations of sparse coding,” in Proceedings of the 27th International Conference on International Conference on Machine Learning, 2010, pp. 399–406. – [6] Z. Wang, D. Liu, J. Yang, W. Han, and T. Huang, “Deep Networks for Image Super-Resolution with Sparse Prior,” arXiv:1507.08905 [cs], Oct. 2015 [Online]. Available: http://arxiv.org/abs/1507.08905. [Accessed: 05-Aug-2020] – [7] X. Chen, J. Liu, Z. Wang, and W. Yin, “Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds,” arXiv:1808.10038 [cs, stat], p. 11, Nov. 2018 [Online]. Available: http://arxiv.org/abs/1808.10038. [Accessed: 16-Jun-2020] – [8] J. Liu, X. Chen, Z. Wang, and W. Yin, “ALISTA: Analytic Weights Are As Good As Learned Weights in LISTA,” in International Conference on Learning Representations, New Orleans, LA, 2019 [Online]. Available: https://openreview.net/forum?id=B1lnzn0ctQ – [9] V. Monga, Y. Li, and Y. C. Eldar, “Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing,” arXiv:1912.10557 [cs, eess], Dec. 2019 [Online]. Available: http://arxiv.org/abs/1912.10557. [Accessed: 16Jun-2020] 31

Appendix: ISTAの最適解収束性（1/8） • 概要 – ISTAで最適解が得られる原理を簡単に説明 • 議論は 𝑁 次元ユークリッド空間上に限定 • 説明の簡略化のため、数学的な厳密性は保証しない – はじめに凸最適化の基礎概念を紹介 • 用語・記号は基本的に[1]に従う – 2段階に分けて証明 1. （最適解の特徴づけ）アルゴリズムの不動点は最適解 2. （大域的収束）任意の初期値でアルゴリズムは不動点に収束 32

Appendix: ISTAの最適解収束性（2/8） • 劣微分（Subdifferential） – 定義: 𝜕𝑓 𝑧 ≔ 𝑢 ∈ ℝ𝑁 ∀𝑥 ∈ ℝ𝑁 𝑓 𝑥 ≥ 𝑓 𝑧 + 𝑢𝑇 𝑥 − 𝑧 • 微分不可能な凸関数に対する勾配の一般化 • 𝑓 のエピグラフ（関数の上側の領域）を半空間に分離し、 点 𝑧, 𝑓 𝑧 で接する超平面の傾きの集合 – この超平面を支持超平面と呼ぶ • もし 𝑧 ∈ ℝ𝑁 で微分可能ならば 𝜕𝑓 𝑧 = ∇𝑓 𝑧 𝑦 epi 𝑓 ≔ 𝑥, 𝑦 𝑦≥𝑓 𝑥 𝑦 = 𝑓 𝑧 + 𝑢 ⋅ (𝑥 − 𝑧) 𝑧 33 𝑥

Appendix: ISTAの最適解収束性（3/8） • Fermat の法則（凸最適化） – 劣微分による目的関数の最適性条件 – 𝑥 ∗ は関数 𝑓 の最小解 ⇔ 0 ∈ 𝜕𝑓 𝑥 ∗ • 𝑓 は最小値を持つ凸関数 • 実は劣微分の定義より明らか – 0 ∈ 𝜕𝑓 𝑥 ∗ ⇔ ∀𝑥 𝑓 𝑥 ≥ 𝑓 𝑥 ∗ + 0𝑇 𝑥 − 𝑥 ∗ = 𝑓(𝑥 ∗ ) 𝑦 epi 𝑓 ≔ 𝑥, 𝑦 𝑦≥𝑓 𝑥 𝑦 = 𝑓 𝑧 + 𝑢 ⋅ (𝑥 − 𝑧) 𝑦 = 𝑓 𝑥 ∗ + 0 ⋅ (𝑥 − 𝑥 ∗ ) 𝑥∗ 𝑧 34 𝑥

Appendix: ISTAの最適解収束性（4/8） • Proximity operator (prox) – 定義： prox𝑓 𝑥 ≔ argmin𝑦∈ℝ𝑁 𝑓 𝑦 • 𝑓 は最小値を持つ凸関数 1 + 2 – 性質 1. 単射かつ prox𝜆𝑓 = Id + 𝜆𝜕𝑓 −1 , 𝜆 > 0 – 右辺は 𝜕𝑓 のレゾルベント 2. 非拡大写像（リプシッツ定数 ≤ 1） – 自明ではないが、一般の証明は長くなるので割愛 3. 𝑥 ∗ は prox𝑓 の不動点 ⇔ 𝑥 ∗ ∈ Argmin𝑥 𝑓 𝑥 –系 • 𝑓: 𝑥 ↦ 𝑥 1 のとき prox𝜆𝑓 = 𝑆𝜆 – 証明略 35 𝑦−𝑥 2

Appendix: ISTAの最適解収束性（5/8） • prox 性質1 の証明（ Id + 𝜆𝜕𝑓 −1 = prox𝜆𝑓 ） 𝑢 ∈ ran Id + 𝜆𝜕𝑓 = ℝ𝑁 とする*。このとき 𝑥 ∈ Id + 𝜆𝜕𝑓 −1 𝑢 ⇔ 𝑢 ∈ Id + 𝜆𝜕𝑓 𝑥 = 𝑥 + 𝜆𝜕𝑓 𝑥 ⇔ 0 ∈ 𝜆𝜕𝑓 𝑥 + 𝑥 − 𝑢 1 ⇔ 0 ∈ 𝜕𝑥 𝜆𝑓 𝑥 + 𝑥 − 𝑢 2 2 1 ⇔ 𝑥 = argmin𝑦 𝜆𝑓 𝑦 + 𝑦 − 𝑢 2 , 2 ⇔ 𝑥 = prox𝜆𝑓 (𝑢) (∗∗) * ran(𝐹) は関数 𝐹 の値域。 𝑓 が凸で最小値を持つならば Minty の定理より等号が成立[1] 1 ** 𝑓 が凸ならば 𝜆𝑓 + ⋅ −𝑢 2 (𝜆 > 0) は狭義凸なので最小解は唯一 2 36

Appendix: ISTAの最適解収束性（6/8） • 最適解の特徴づけ 1 – 目的関数： 2 𝐴𝑧 − 𝑦 2 + 𝜆 𝑧 1 – 以下の議論より 目的関数の最適解 = ISTAの不動点 が示される • 同時に、不動点は必ず存在することもわかる 目的関数は明らかに最適解 𝑧 ∗ が存在する。このとき、Fermat の法則より 1 ∗ 𝑧 ∈ Argmin𝑧 𝐴𝑧 − 𝑦 2 + 𝜆 𝑧 1 2 1 ⇔ 0 ∈ 𝜕𝑧 ∗ 𝐴𝑧 ∗ − 𝑦 2 + 𝜆 𝑧 ∗ 1 = 𝐴𝑇 𝐴𝑧 ∗ − 𝑦 + 𝜆𝜕 𝑧 ∗ 1 2 ⇔ 𝑧 ∗ − 𝜏𝐴𝑇 𝐴𝑧 ∗ − 𝑦 ∈ Id + 𝜏𝜆𝜕 ⋅ 1 𝑧 ∗ , (∀𝜏 > 0) ⇔ 𝑧 ∗ ∈ Id + 𝜏𝜆𝜕 ⋅ 1 −1 𝑧 ∗ − 𝜏𝐴𝑇 𝐴𝑧 ∗ − 𝑦 ⇔ 𝑧 ∗ = 𝑆𝜏𝜆 𝑧 ∗ − 𝜏𝐴𝑇 𝐴𝑧 ∗ − 𝑦 37

Appendix: ISTAの最適解収束性（7/8） • 不動点定理 – 反復法において不動点への収束を保証するための基本原理 • 「最適解の特徴づけ」だけでは、収束性に関してほとんど述べていないので不十分 Banach-Picardの不動点定理 [1,Theorem 1.50 (i)&(iii)] リプシッツ定数 𝛽 < 1 を持つ関数（縮小写像）を 𝜓: ℝ𝑁 → ℝ𝑁 とする。 このとき 𝜓 は唯一の不動点 𝑧 ∗ を持つ。また、任意の 𝑧 0 ∈ ℝ𝑁 について ∀𝑘 ≥ 0 𝑧 𝑘+1 = 𝜓 𝑧 𝑘 で生成される点列 𝑧 𝑘 ∗ に収束する は 𝑧 𝑘≥0 38

Appendix: ISTAの最適解収束性（8/8） • ISTAの大域的収束条件 −2 ならば、ISTA 更新式は縮小写像 – 0 < 𝜏 < 2𝜎max – この条件のもとで、Banach-Picard の定理より 𝑧 (𝑘) は最適解へ収束 ISTAの更新式を 𝜓: 𝑧 ↦ 𝑆𝜏𝜆 𝑧 − 𝜏𝐴𝑇 𝐴𝑧 − 𝑦 と定義する。 このとき、𝜓 の作用素ノルムは 𝜓 2 ≤ 𝑆𝜏𝜆 2 ⋅ Id − 𝜏𝐴𝑇 𝐴 2 = Id − 𝜏𝐴𝑇 𝐴 2 = 1 − 𝜏 𝐴 2 2 である。𝜏 > 0 かつ 𝐴 = 𝜎max なので、 −2 ならば 𝜓 < 1 0 < 𝜏 < 2𝜎max 39