Algorithm
カツマルツ 法 、あるいは カツマルツのアルゴリズムは、 線形方程式系を 解くための 反復アルゴリズム です 。ポーランドの数学者 ステファン・カツマルツによって初めて発見され [1] 、 1970年に リチャード・ゴードン 、ロバート・ベンダー、 ガボール・ヘルマン によって投影画像再構成の分野で再発見され、 代数的再構成法 （ART） と呼ばれています [2] 。ARTは正値制約を含むため、非線形となります [3]。 A x = b {\displaystyle Ax=b}
カツマルツ法はあらゆる線形方程式系に適用可能ですが、他の手法と比較した計算上の優位性は、系が 疎行列であるかどうかに依存します。一部の生物医学画像アプリケーションにおいては、 フィルタ逆投影 法などの他の手法よりも優れていることが実証されています 。 [4]
これは、コンピュータ断層撮影 （CT）から 信号処理 に至るまで、幅広い応用分野に用いられています。また、線形システムで記述される超平面に、 凸集合へ の逐次射影法 （POCS）を適用することでも得られます。 [5] [6]
アルゴリズム1：カツマルツアルゴリズム Kaczmarz 反復の例。 オリジナルの Kaczmarz アルゴリズムは、複素数値 の線形方程式系 を解きます。 A x = b {\displaystyle Ax=b}
をの - 行目 の 共役転置 とし ます 。 を任意の複素数値初期近似値に初期化します。(例 : ) について、以下 を計算します。 a i {\displaystyle a_{i}} i {\displaystyle i} A {\displaystyle A} x 0 {\displaystyle x_{0}} x 0 = 0 {\displaystyle x_{0}=0} k = 0 , 1 , … {\displaystyle k=0,1,\ldots }
x k + 1 = x k + b i k − ⟨ a i k , x k ⟩ ‖ a i k ‖ 2 a i k {\displaystyle x_{k+1}=x_{k}+{\frac {b_{i_{k}}-\langle a_{i_{k}},x_{k}\rangle }{\|a_{i_{k}}\|^{2}}}a_{i_{k}}} 1
ここで、の行を任意 の順序 （決定的順序またはランダム順序）で反復します。各行を無限回反復することだけが必要です。 i 0 , i 1 , i 2 , … {\displaystyle i_{0},i_{1},i_{2},\dots } A {\displaystyle A}
実ベクトル空間では、カツマルツ反復法は明確な幾何学的意味を持ちます。これは、 によって定義される 超平面 に直交する投影を意味します 。この解釈では、カツマルツ反復法が収束する場合、 の解のいずれかに収束する必要があることは明らかです 。 x k {\textstyle x_{k}} { x : ⟨ a i , x ⟩ = b i } {\textstyle \{x:\langle a_{i},x\rangle =b_{i}\}} A x = b {\textstyle Ax=b}
より一般的なアルゴリズムは緩和 パラメータ を使用して定義できる。 λ k {\displaystyle \lambda ^{k}}
x k + 1 = x k + λ k b i k − ⟨ a i k , x k ⟩ ‖ a i k ‖ 2 a i k {\displaystyle x_{k+1}=x_{k}+\lambda _{k}{\frac {b_{i_{k}}-\langle a_{i_{k}},x_{k}\rangle }{\|a_{i_{k}}\|^{2}}}a_{i_{k}}} 系に解が存在する場合、反復が零ベクトルから始まる限り、 は最小 ノルム 解に収束します。行が の順に反復され、 の場合 、収束は指数関数的です。 x k {\displaystyle x_{k}} λ k = 1 {\displaystyle \lambda _{k}=1}
この方法には、矛盾した方程式のシステムに適用すると正規化された重み付き最小二乗解に収束するバージョンがあり、少なくとも初期の挙動に関しては、 共役勾配法 などの他の反復法よりもコストが低くなります。 [7]
アルゴリズム2: ランダム化Kaczmarzアルゴリズム 2009年に、過剰決定 線形システムに対するカツマルツ法のランダム化バージョン がトーマス・ストロマーとローマン・ヴェルシニンによって導入された [8]。 この方法では、 i 番目の方程式が、 ‖ a i ‖ 2 . {\displaystyle \|a_{i}\|^{2}.}
この方法は確率的勾配降下法 の特殊なケースとして見ることができる 。 [9]
このような状況では、 は指数関数的に速く の解に収束し 、収束速度はスケールされた 条件数 のみに依存します。 x k {\displaystyle x_{k}} A x = b , {\displaystyle Ax=b,} κ ( A ) {\displaystyle \kappa (A)}
定理。 を の解とすると、 アルゴリズム 2は 期待値で に収束し、平均誤差は次のようになります。 x {\displaystyle x} A x = b . {\displaystyle Ax=b.} x {\displaystyle x} E ‖ x k − x ‖ 2 ≤ ( 1 − κ ( A ) − 2 ) k ⋅ ‖ x 0 − x ‖ 2 . {\displaystyle \mathbb {E} \|x_{k}-x\|^{2}\leq \left(1-\kappa (A)^{-2}\right)^{k}\cdot \|x_{0}-x\|^{2}.}
証拠 我々は持っています
∀ z ∈ C n : ∑ j = 1 m | ⟨ z , a j ⟩ | 2 ≥ ‖ z ‖ 2 ‖ A − 1 ‖ 2 {\displaystyle \forall z\in \mathbb {C} ^{n}:\quad \sum _{j=1}^{m}|\langle z,a_{j}\rangle |^{2}\geq {\frac {\|z\|^{2}}{\|A^{-1}\|^{2}}}} 2
使用
‖ A ‖ 2 = ∑ j = 1 m ‖ a j ‖ 2 {\displaystyle \|A\|^{2}=\sum _{j=1}^{m}\|a_{j}\|^{2}} （ ２ ）は次のように 書ける。
∀ z ∈ C n : ∑ j = 1 m ‖ a j ‖ 2 ‖ A ‖ 2 | ⟨ z , a j ‖ a j ‖ ⟩ | 2 ≥ κ ( A ) − 2 ‖ z ‖ 2 {\displaystyle \forall z\in \mathbb {C} ^{n}:\quad \sum _{j=1}^{m}{\frac {\|a_{j}\|^{2}}{\|A\|^{2}}}\left|\left\langle z,{\frac {a_{j}}{\|a_{j}\|}}\right\rangle \right|^{2}\geq \kappa (A)^{-2}{\|z\|^{2}}} 3
証明の要点は、( 3 )の左辺を何らかの確率変数の期待値として捉えることである。つまり、 方程式 の解空間は 超平面である
ことを思い出してほしい。 j − t h {\displaystyle j-th} A x = b {\displaystyle Ax=b}
{ y : ⟨ y , a j ⟩ = b j } , {\displaystyle \{y:\langle y,a_{j}\rangle =b_{j}\},} その法線は のすべての方程式の法線を値とする ランダムベクトル Z を定義します。確率はアルゴリズムと同じです。 a j ‖ a j ‖ 2 . {\displaystyle {\tfrac {a_{j}}{\|a_{j}\|^{2}}}.} A x = b {\displaystyle Ax=b}
Z = a j ‖ a j ‖ {\displaystyle Z={\frac {a_{j}}{\|a_{j}\|}}} 確率的に ‖ a j ‖ 2 ‖ A ‖ 2 j = 1 , … , m {\displaystyle {\frac {\|a_{j}\|^{2}}{\|A\|^{2}}}\qquad \qquad \qquad j=1,\ldots ,m} そして（ ３ ）は
∀ z ∈ C n : E | ⟨ z , Z ⟩ | 2 ≥ κ ( A ) − 2 ‖ z ‖ 2 {\displaystyle \forall z\in \mathbb {C} ^{n}:\quad \mathbb {E} |\langle z,Z\rangle |^{2}\geq \kappa (A)^{-2}{\|z\|^{2}}} 4
のランダム方程式の解空間への 直交射影は 次のように与えられる。 P {\displaystyle P} A x = b {\displaystyle Ax=b} P z = z − ⟨ z − x , Z ⟩ Z . {\displaystyle Pz=z-\langle z-x,Z\rangle Z.}
これで、アルゴリズムを解析する準備が整いました。誤差が 平均の各ステップ（前のステップを条件とする）で少なくとも 倍減少することを示します 。次の近似は、 ランダム射影の独立した実現 で ある から計算されます。 ベクトル は の核に 含まれます。これは、 が射影される方程式の解空間に直交し 、 にはベクトル （ は すべての方程式の解であることを思い出してください）が含まれます。これら2つのベクトルの直交性から、次の式が得られます。 ‖ x k − x ‖ 2 {\displaystyle {\|x_{k}-x\|^{2}}} ( 1 − κ ( A ) − 2 ) . {\displaystyle (1-\kappa (A)^{-2}).} x k {\displaystyle x_{k}} x k − 1 {\displaystyle x_{k-1}} x k = P k x k − 1 , {\displaystyle x_{k}=P_{k}x_{k-1},} P 1 , P 2 , … {\displaystyle P_{1},P_{2},\ldots } P . {\displaystyle P.} x k − 1 − x k {\displaystyle x_{k-1}-x_{k}} P k . {\displaystyle P_{k}.} P k {\displaystyle P_{k}} x k − x {\displaystyle x_{k}-x} x {\displaystyle x}
‖ x k − x ‖ 2 = ‖ x k − 1 − x ‖ 2 − ‖ x k − 1 − x k ‖ 2 . {\displaystyle \|x_{k}-x\|^{2}=\|x_{k-1}-x\|^{2}-\|x_{k-1}-x_{k}\|^{2}.} 証明を完了するには、 下から境界を引かなければなりません。の定義により 、 ‖ x k − 1 − x k ‖ 2 {\displaystyle \|x_{k-1}-x_{k}\|^{2}} x k {\displaystyle x_{k}}
‖ x k − 1 − x k ‖ = ⟨ x k − 1 − x , Z k ⟩ {\displaystyle \|x_{k-1}-x_{k}\|=\langle x_{k-1}-x,Z_{k}\rangle } ランダムベクトルの独立実現 は Z 1 , Z 2 , … {\displaystyle Z_{1},Z_{2},\ldots } Z . {\displaystyle Z.}
したがって
‖ x k − x ‖ 2 ≤ ( 1 − | ⟨ x k − 1 − x ‖ x k − 1 − x ‖ , Z k ⟩ | 2 ) ‖ x k − 1 − x ‖ 2 . {\displaystyle \|x_{k}-x\|^{2}\leq \left(1-\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k-1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.} ここで、両辺の期待値をランダムベクトルの選択を条件として取ります （したがって、ランダム射影の選択 とランダムベクトルを固定し 、ランダムベクトルを平均します ）。すると、 Z 1 , … , Z k − 1 {\displaystyle Z_{1},\ldots ,Z_{k-1}} P 1 , … , P k − 1 {\displaystyle P_{1},\ldots ,P_{k-1}} x 1 , … , x k − 1 {\displaystyle x_{1},\ldots ,x_{k-1}} Z k {\displaystyle Z_{k}}
E Z 1 , … , Z k − 1 ‖ x k − x ‖ 2 = ( 1 − E Z 1 , … , Z k − 1 , Z k | ⟨ x k − 1 − x ‖ x k − 1 − x ‖ , Z k ⟩ | 2 ) ‖ x k − 1 − x ‖ 2 . {\displaystyle \mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}=\left(1-\mathbb {E} _{Z_{1},\ldots ,Z_{k-1},Z_{k}}\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k-1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.} （ ４ ）と独立性により、
E Z 1 , … , Z k − 1 ‖ x k − x ‖ 2 ≤ ( 1 − κ ( A ) − 2 ) ‖ x k − 1 − x ‖ 2 . {\displaystyle \mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}\leq (1-\kappa (A)^{-2}){\|x_{k-1}-x\|^{2}}.} 双方の期待を総合的に考慮すると、
E ‖ x k − x ‖ 2 ≤ ( 1 − κ ( A ) − 2 ) E ‖ x k − 1 − x ‖ 2 . ◼ {\displaystyle \mathbb {E} \|x_{k}-x\|^{2}\leq (1-\kappa (A)^{-2})\mathbb {E} {\|x_{k-1}-x\|^{2}}.\blacksquare } この選択法の優位性は、不均一間隔のサンプリング値から帯域制限関数を再構成することによって実証された。しかしながら、 StrohmerとVershyninが報告した成功は 、超平面集合の共通点を求める という幾何学的性質を持つ根底問題を代数方程式系に翻訳する際に行われた特定の選択に依存していることが指摘されている[10]。根底問題の正当な代数表現は常に存在し、それらに対しては [8] の選択法は 劣った結果となる。 [8] [10] [11]
Kaczmarz反復法（ 1 ）は純粋に幾何学的な解釈が可能である。このアルゴリズムは、現在の反復を次の方程式で定義される超平面に逐次投影する。したがって、方程式のスケーリングは無関係である。また、（ 1 ）から、方程式のスケーリング（非ゼロ）はいずれも打ち消されることも分かる。したがって、RKでは、 または関連する可能性のある他の任意の重みを使用することができる。具体的には、上記の再構成の例では、方程式は、各サンプル点とその2つの最も近い近傍点からの平均距離に比例する確率で選択された。これは、 Feichtinger とGröchenigによって導入された概念である。このトピックに関するさらなる進展については、 [12] [13] およびそこに含まれる参考文献を参照のこと。 ‖ a i ‖ {\displaystyle \|a_{i}\|}
アルゴリズム 3: Gower-Richtarik アルゴリズム 2015年、ロバート・M・ガワーと ピーター・リヒタリック [14] は、一貫性のある線形方程式系を解くための汎用的なランダム化反復法を開発しました。この手法 には、ランダム化カツマルツアルゴリズムを特殊なケースとして含んでいます。その他の特殊なケースとしては、ランダム化 座標降下法 、ランダム化ガウス降下法、ランダム化ニュートン法などがあります。これらの手法のブロック版や 重要度サンプリング 版も特殊なケースとして挙げられます。この手法は、ランダム性がアルゴリズムに導入される際の非常に緩やかな条件下では、指数関数的な速度減少（線形収束とも呼ばれます）を示すことが示されています。ガワー・リヒタリック法は、これらの手法間の「兄弟」関係を明らかにした最初のアルゴリズムです。これらの手法の中には、以前にも独立して提案されたものもあれば、新しいものもありました。 A x = b {\displaystyle Ax=b}
ランダム化されたカツマルツに関する洞察 ランダム化 Kaczmarz 法の分析から得られる、この方法に関する興味深い新しい洞察には次のものがあります。
Gower-Richtarik アルゴリズムの一般的なレートは、特別なケースではランダム化 Kaczmarz 法のレートを正確に回復します。 ランダム化カツマルツ法が元々定式化され解析された確率（行ノルムの2乗に比例する確率）の選択は最適ではありません。最適確率とは、ある半正定値計画の解です。最適確率を用いたランダム化カツマルツ法の理論的な計算量は、標準確率を用いた場合の計算量よりも任意に小さくなる可能性があります。ただし、どの程度小さくなるかは行列に依存します 。標準確率が最適な問題も存在します。 A {\displaystyle A} 正定値行列を持つシステムに適用された場合 、ランダム化 Kaczmarz 法は、強凸二次関数を最小化する確率的勾配降下法 (SGD) (非常に特殊なステップ サイズを使用) と同等です。は凸である ため 、 の最小化は を 満たす必要が あり、これは と同等であることに注意してください 。 「特殊なステップ サイズ」とは、確率的勾配が張る 1 次元線上で の未知 (!) の最小化からのユークリッド距離を最小化する点 ( つまり、 から ) につながるステップ サイズです。 この洞察は、 反復プロセスの 2 つの視点 (以下、「最適化の観点: 制約と近似」と説明) から得られます。 A {\displaystyle A} f ( x ) = 1 2 x T A x − b T x . {\displaystyle f(x)={\tfrac {1}{2}}x^{T}Ax-b^{T}x.} f {\displaystyle f} f {\displaystyle f} ∇ f ( x ) = 0 {\displaystyle \nabla f(x)=0} A x = b . {\displaystyle Ax=b.} f {\displaystyle f} x ∗ = A − 1 b . {\displaystyle x^{*}=A^{-1}b.}
Gower-Richtarik 法には、一見異なっているが同等の 6 つの定式化があり、その解釈方法 (および、結果として、ランダム化された Kaczmarz 法を含むその多くの変種をどのように解釈するか) について新たな光を当てています。
1. スケッチの視点：スケッチと投影 2. 最適化の観点：制約と近似 3. 幾何学的視点：ランダム交差 4. 代数的視点1：ランダム線形解法 5. 代数的視点2：ランダム更新 6. 分析的視点：ランダム固定点 ここで、これらの視点のいくつかについて説明します。この方法は2つのパラメータに依存します。
重み付きユークリッド内積と誘導ノルム を生じる 正定値行列 B {\displaystyle B} ⟨ x , y ⟩ B := x T B y {\displaystyle \langle x,y\rangle _{B}:=x^{T}By} ‖ x ‖ B = ( ⟨ x , x ⟩ B ) 1 2 , {\displaystyle \|x\|_{B}=\left(\langle x,x\rangle _{B}\right)^{\frac {1}{2}},} そして、行数と同数（列数はランダムの可能性あり）の ランダム行列 。 S {\displaystyle S} A {\displaystyle A}
1. スケッチとプロジェクト 前回の反復処理で与えられた 新しい点 は、ランダム行列 （ある固定分布からiid形式で）を描画し、 x k , {\displaystyle x^{k},} x k + 1 {\displaystyle x^{k+1}} S {\displaystyle S}
x k + 1 = a r g m i n x ‖ x − x k ‖ B subject to S T A x = S T b . {\displaystyle x^{k+1}={\underset {x}{\operatorname {arg\ min} }}\|x-x^{k}\|_{B}{\text{ subject to }}S^{T}Ax=S^{T}b.} つまり、は ランダムに描かれた系 へ の射影として得られる 。この手法の背後にある考え方は、 を、 描かれた系への射影が元の系 の解よりも大幅に単純になるように選択することである。ランダム化カツマルツ法は、 を 単位行列 、 を 確率 の 単位 座標ベクトル として選択すること で得られる。 と の選択によって 、 この手法のさまざまなバリエーションが生まれる。 x k + 1 {\displaystyle x^{k+1}} x k {\displaystyle x^{k}} S T A x = S T b {\displaystyle S^{T}Ax=S^{T}b} S {\displaystyle S} A x = b {\displaystyle Ax=b} B {\displaystyle B} S {\displaystyle S} i t h {\displaystyle i^{th}} p i = ‖ a i ‖ 2 2 / ‖ A ‖ F 2 . {\displaystyle p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2}.} B {\displaystyle B} S {\displaystyle S}
2. 制約と近似 一見異なるが全く同等なこの方法の定式化（ラグランジュ双対性によって得られる）は、
x k + 1 = a r g m i n x ‖ x − x ∗ ‖ B subject to x = x k + B − 1 A T S y , {\displaystyle x^{k+1}={\underset {x}{\operatorname {arg\ min} }}\left\|x-x^{*}\right\|_{B}{\text{ subject to }}x=x^{k}+B^{-1}A^{T}Sy,} ここでも 変化することが許されており、ここで は系の任意の解である 。したがって、 は、 まずランダム行列 の列によって張られる線形部分空間への更新を制約することによって得られる。 すなわち、 y {\displaystyle y} x ∗ {\displaystyle x^{*}} A x = b . {\displaystyle Ax=b.} x k + 1 {\displaystyle x^{k+1}} B − 1 A T S {\displaystyle B^{-1}A^{T}S}
{ h : h = B − 1 A T S y , y can vary } , {\displaystyle \left\{h:h=B^{-1}A^{T}Sy,\quad y{\text{ can vary }}\right\},} そして、この部分空間から を最もよく近似する 点を選択します 。この定式化は、 が未知であるという事実 （結局のところ、計算しようとしているのはこれです！）のために近似ステップを実行することが不可能であるように思われ、驚くべきものに見えるかもしれません。しかし、この方法で計算された は、 スケッチとプロジェクトの定式化で計算された と同じであり、 は そこに現れないため、それでも実行可能です。 x {\displaystyle x} x ∗ {\displaystyle x^{*}} x ∗ {\displaystyle x^{*}} x k + 1 {\displaystyle x^{k+1}} x k + 1 {\displaystyle x^{k+1}} x ∗ {\displaystyle x^{*}}
5. ランダム更新 更新は次のように明示的に書くこともできる。
x k + 1 = x k − B − 1 A T S ( S T A B − 1 A T S ) † S T ( A x k − b ) , {\displaystyle x^{k+1}=x^{k}-B^{-1}A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\dagger }S^{T}\left(Ax^{k}-b\right),} ここで、 は 行列 のムーア・ペンローズ擬似逆行列を表します 。したがって、この方法は の形式で記述できます。 ここでは ランダム更新 ベクトルです 。 M † {\displaystyle M^{\dagger }} M {\displaystyle M} x k + 1 = x k + h k {\displaystyle x^{k+1}=x^{k}+h^{k}} h k {\displaystyle h^{k}}
とおくと、系には 常に解 が存在し 、そのような解すべてに対してベクトル は 同じであること が示されます。したがって、これらの解のどれを選択しても問題はなく、この方法は とも書くことができます 。擬似逆問題によって、特定の解が1つだけ得られます。擬似逆問題の役割は2つあります。 M = S T A B − 1 A T S , {\displaystyle M=S^{T}AB^{-1}A^{T}S,} M y = S T ( A x k − b ) {\displaystyle My=S^{T}(Ax^{k}-b)} y k {\displaystyle y^{k}} x k + 1 − B − 1 A T S y k {\displaystyle x^{k+1}-B^{-1}A^{T}Sy^{k}} x k + 1 = x k − B − 1 A T S y k {\displaystyle x^{k+1}=x^{k}-B^{-1}A^{T}Sy^{k}}
これにより、メソッドを上記のように明示的に「ランダム更新」形式で記述できるようになります。 最後の 6 番目の定式化により、分析が簡単になります。
6. ランダム固定点 ランダム更新式の両辺から 減算すると、 x ∗ {\displaystyle x^{*}}
Z := A T S ( S T A B − 1 A T S ) † S T A , {\displaystyle Z:=A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\dagger }S^{T}A,} そして、最終的な定式化に到達する という事実を使用します。 A x ∗ = b , {\displaystyle Ax^{*}=b,}
x k + 1 − x ∗ = ( I − B − 1 Z ) ( x k − x ∗ ) , {\displaystyle x^{k+1}-x^{*}=\left(I-B^{-1}Z\right)\left(x^{k}-x^{*}\right),} ここで は単位行列です。反復行列は ランダムであり、これがこの定式の名前の由来です。 I {\displaystyle I} I − B − 1 Z , {\displaystyle I-B^{-1}Z,}
収束 6番目の定式化における条件付き期待値（ を条件とする ）をとると、 x k {\displaystyle x^{k}}
E [ x k + 1 − x ∗ | x k ] = ( I − B − 1 E [ Z ] ) [ x k − x ∗ ] . {\displaystyle \mathbb {E} \left.\left[x^{k+1}-x^{*}\right|x^{k}\right]=\left(I-B^{-1}\mathbb {E} [Z]\right)\left[x^{k}-x^{*}\right].} 期待値を再び取り、期待値の塔の性質を利用すると、
E [ x k + 1 − x ∗ ] = ( I − B − 1 E [ Z ] ) E [ x k − x ∗ ] . {\displaystyle \mathbb {E} \left[x^{k+1}-x^{*}\right]=(I-B^{-1}\mathbb {E} [Z])\mathbb {E} \left[x^{k}-x^{*}\right].} ガワーとリヒタリック [14] は、
ρ := ‖ I − B − 1 2 E [ Z ] B − 1 2 ‖ B = λ max ( I − B − 1 E [ Z ] ) , {\displaystyle \rho :=\left\|I-B^{-{\frac {1}{2}}}\mathbb {E} [Z]B^{-{\frac {1}{2}}}\right\|_{B}=\lambda _{\max }\left(I-B^{-1}\mathbb {E} [Z]\right),} ここで行列ノルムは次のように定義される。
‖ M ‖ B := max x ≠ 0 ‖ M x ‖ B ‖ x ‖ B . {\displaystyle \|M\|_{B}:=\max _{x\neq 0}{\frac {\|Mx\|_{B}}{\|x\|_{B}}}.} さらに、 1つに何の仮定もなしに 、ノルムを取り、再帰を展開することで、次の式が得られる。 S {\displaystyle S} 0 ≤ ρ ≤ 1. {\displaystyle 0\leq \rho \leq 1.}
定理 [Gower & Richtarik 2015] ‖ E [ x k − x ∗ ] ‖ B ≤ ρ k ‖ x 0 − x ∗ ‖ B . {\displaystyle \left\|\mathbb {E} \left[x^{k}-x^{*}\right]\right\|_{B}\leq \rho ^{k}\|x^{0}-x^{*}\|_{B}.} 注記 ：期待残差が0に収束するための十分条件は、 がフルカラムランクを持ち、非常に穏やかな条件下で は、この条件が満たされれば達成できる 。この方法の収束は、フルカラムランクの仮定がない場合でも、別の方法で確立できる。 [15] ρ < 1. {\displaystyle \rho <1.} A {\displaystyle A} S . {\displaystyle S.}
より強力な結果を表示することも可能です。
定理 [Gower & Richtarik 2015] 期待される 二乗ノルム （期待値のノルムではなく）は同じ速度で収束します。
E ‖ [ x k − x ∗ ] ‖ B 2 ≤ ρ k ‖ x 0 − x ∗ ‖ B 2 . {\displaystyle \mathbb {E} \left\|\left[x^{k}-x^{*}\right]\right\|_{B}^{2}\leq \rho ^{k}\left\|x^{0}-x^{*}\right\|_{B}^{2}.} 注 ：この2番目のタイプの収束は、任意のランダムベクトル と任意の固定ベクトル に対して成り立つ次の恒等式 [14] により 強く なります。 x {\displaystyle x} x ∗ {\displaystyle x^{*}}
‖ E [ x − x ∗ ] ‖ 2 = E [ ‖ x − x ∗ ‖ 2 ] − E [ ‖ x − E [ x ] ‖ 2 ] . {\displaystyle \left\|\mathbb {E} \left[x-x^{*}\right]\right\|^{2}=\mathbb {E} \left[\left\|x-x^{*}\right\|^{2}\right]-\mathbb {E} \left[\|x-\mathbb {E} [x]\|^{2}\right].}
ランダム化カツマルツの収束 ランダム化カツマルツ法は、ガワー・リヒタリック法の特別なケースとして現れ 、 確率が単位座標ベクトル であることを確認しました。 ここで、は行です。直接計算によって、 次 の ことが確認できます。 B = I {\displaystyle B=I} S {\displaystyle S} i t h {\displaystyle i^{th}} p i = ‖ a i ‖ 2 2 / ‖ A ‖ F 2 , {\displaystyle p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2},} a i {\displaystyle a_{i}} i t h {\displaystyle i^{th}} A . {\displaystyle A.}
ρ = ‖ I − B − 1 E [ Z ] ‖ B = 1 − λ min ( A T A ) ‖ A ‖ F 2 . {\displaystyle \rho =\|I-B^{-1}\mathbb {E} [Z]\|_{B}=1-{\frac {\lambda _{\min }(A^{T}A)}{\|A\|_{F}^{2}}}.}
その他の特別なケース
アルゴリズム4: PLSS-Kaczmarz （ランダム化）カツマルツ法の収束は 収束速度 に依存するため、いくつかの実用的な問題では収束が遅い場合がある。 [10] この方法の有限終了を保証するために、ヨハネス・ブラストと マイケル・サンダース（学術的） [16] は、（ランダム化）カツマルツ反復法を一般化し、最大で 反復回数で無矛盾なシステムの解に到達するプロセスを開発した 。このプロセスは 次元削減 、つまり低次元空間への射影に基づいており、これがPLSS（Projected Linear Systems Solver）という名前に由来する。PLSS-カツマルツ反復法は、 m {\displaystyle m} A x = b {\displaystyle Ax=b}
x k + 1 = x k + A : , 1 : k T ( A 1 : k , : A : , 1 : k T ) † ( b 1 : k − A 1 : k , : x k ) {\displaystyle x^{k+1}=x^{k}+A_{:,1:k}^{T}(A_{1:k,:}A_{:,1:k}^{T})^{\dagger }(b_{1:k}-A_{1:k,:}x^{k})} ここで、 は の1行目から までとすべての 列の選択です 。この手法のランダム化バージョン では、各反復で重複しない行インデックスを使用します。 ここで、各 は にあります 。反復は のときに解に収束します 。 特に、 A 1 : k , : {\displaystyle A_{1:k,:}} k {\displaystyle k} A {\displaystyle A} k {\displaystyle k} { i 1 , … , i k − 1 , i k } {\displaystyle \{i_{1},\ldots ,i_{k-1},i_{k}\}} i j {\displaystyle i_{j}} 1 , 2 , . . . , m {\displaystyle 1,2,...,m} k = m {\displaystyle k=m} A 1 : m , : = A {\displaystyle A_{1:m,:}=A}
A x m + 1 = A x m + A A T ( A A T ) † ( b − A x m ) = b {\displaystyle Ax^{m+1}=Ax^{m}+AA^{T}(AA^{T})^{\dagger }(b-Ax^{m})=b} したがって、 これは線形システムの解である。PLSS-Kaczmarzにおける反復計算は簡略化され、効果的に整理することができる。結果として得られるアルゴリズムは行列とベクトルの積のみを必要とし、直接的な形をとる。 x m + 1 {\displaystyle x^{m+1}}
アルゴリズム PLSS-Kaczmarz は 入力: 行列 Aの 右辺 b、 出力: Ax=b となる 解 xである。 x := 0 , P = [0] 1,2,...,m 内 の k に対して a := A(i k ,:)' // 1,...,m から再サンプリングせずに インデックス i k を選択するd := P' * a c 1 := norm(a) c 2 := norm(d) c 3 := (b i k -x'*a)/((c 1 -c 2 )*(c 1 +c 2 )) p := c 3 *(a - P*(P'*a)) P := [ P, p/norm(p) ] // 正規化された更新を追加する x := x + p x を返す
注記 ^ カチマルツ（1937） ^ ゴードン、ベンダー、ハーマン（1970） ^ ゴードン（2011） ^ ハーマン（2009） ^ 検閲官とゼニオス（1997） ^ アスター、ボルチャーズ、サーバー (2004) ^ Herman (2009)およびその中の参考文献を参照。 ^ abc Strohmer & Vershynin (2009) ^ ニーデル、スレブロ、ウォード (2015) ^ abc Censor、Herman & Jiang（2009） ^ シュトロマー & ヴァーシャニン (2009b) ^ Bass & Gröchenig (2013) ^ ゴードン（2017） ^ abc ガワー＆リヒタリク (2015a) ^ ガワー＆リヒタリック（2015b） ^ ブラスト＆サンダース（2023）
参考文献 Kaczmarz、Stefan (1937)、「Angenäherte Auflösung von Systemen Linear Gleichungen」 (PDF) 、 国際科学アカデミー紀要。 Classe des Sciences 数学と自然。セリエ A、科学数学 、vol. 35、pp. 355–357 、オリジナル (PDF) から2012-04-25 にアーカイブ 、 2011-10-07 に取得 チョン、エドウィン KP; ザック、スタニスワフ H. (2008) 『最適化入門』 （第3版）、ジョン・ワイリー・アンド・サンズ、pp. 226– 230 ゴードン、リチャード ； ベンダー、ロバート ； ハーマン、ガボール （1970）「三次元電子顕微鏡およびX線写真のための代数的再構成技術（ART）」 Journal of Theoretical Biology 、 29 （3）： 471– 481、 Bibcode ：1970JThBi..29..471G、 doi ：10.1016/0022-5193(70)90109-8、 PMID 5492997 リチャード・ゴードン （2011）「 乳がんを今すぐ止めよう！転移前乳がんの探索、破壊、治癒、そして経過観察に向けた画像診断経路の構想」乳がん - 大葉性疾患、ティボール・トット編、シュプリンガー、 167～ 203 頁 ハーマン、ガボール （2009年）、コンピュータ断層撮影の基礎：投影からの画像再構成（第2版）、シュプリンガー、 ISBN 9781846287237 センサー、ヤイル ；ゼニオス、SA（1997）、 並列最適化：理論、アルゴリズム、およびアプリケーション 、ニューヨーク：オックスフォード大学出版局 アスター、リチャード、ボルチャーズ、ブライアン、サーバー、クリフォード（2004）、 パラメータ推定と逆問題 、エルゼビア Strohmer, Thomas; Vershynin, Roman (2009)「指数収束性線形システムのためのランダム化Kaczmarzアルゴリズム」 （PDF） , Journal of Fourier Analysis and Applications , 15 (2): 262– 278, arXiv : math/0702226 , doi :10.1007/s00041-008-9030-4, S2CID 1903919 Needell, Deanna; Srebro, Nati; Ward, Rachel (2015)、「確率的勾配降下法、重み付きサンプリング、およびランダム化Kaczmarzアルゴリズム」、 Mathematical Programming 、 155 ( 1– 2): 549– 573、 arXiv : 1310.5715 、 doi :10.1007/s10107-015-0864-7、 S2CID 2370209 センサー, ヤイル; ハーマン, ガボール ; ジャン, M. (2009)「StrohmerとVershyninのランダム化Kaczmarzアルゴリズムの挙動に関する注記」 Journal of Fourier Analysis and Applications , 15 (4): 431– 436, Bibcode :2009JFAA...15..431C, doi :10.1007/s00041-009-9077-x, PMC 2872793 , PMID 20495623 Strohmer, Thomas; Vershynin, Roman (2009b)、「ランダム化Kaczmarz法に関するコメント」、 Journal of Fourier Analysis and Applications 、 15 (4): 437– 440、 Bibcode :2009JFAA...15..437S、 doi :10.1007/s00041-009-9082-0、 S2CID 14806325 Bass, Richard F. ; Gröchenig, Karlheinz (2013)、「帯域制限関数の関連サンプリング」、 Illinois Journal of Mathematics 、 57 (1): 43– 58、 arXiv : 1203.0146 、 doi :10.1215/ijm/1403534485、 S2CID 42705738 ゴードン、ダン（2017）「広範囲のランダムサンプリングレートにわたる帯域制限信号の回復のためのデランダム化アプローチ」、 数値アルゴリズム 、 77 （4）： 1141– 1157、 doi ：10.1007/s11075-017-0356-3、 S2CID 1794974 Vinh Nguyen, Quang; Lumban Gaol, Ford (2011)、 2011年第2回国際コンピュータアプリケーションおよび計算科学会議議事録 、第2巻、Springer、pp. 465– 469 ガワー、ロバート; リヒタリック、ピーター (2015a)、「線形システムのためのランダム化反復法」、 SIAM Journal on Matrix Analysis and Applications 、 36 (4): 1660– 1690、 arXiv : 1506.03296 、 doi :10.1137/15M1025487、 S2CID 8215294 ロバート・ガワー、 ピーター・リヒタリック （2015b）「線形システムの解法における確率的双対上昇法」 arXiv : 1512.06890 [math.NA] Brust, Johannes J; Saunders, Michael A (2023)、「PLSS: 射影線形システムソルバー」、 SIAM Journal on Scientific Computing 、 45 (2): A1012 – A1037 、 arXiv : 2207.07615 、 Bibcode :2023SJSC...45A1012B、 doi :10.1137/22M1509783
外部リンク [1] 指数収束を伴うランダム化カツマルツアルゴリズム [2] [ 永久リンク切れ ] ランダム化カツマルツ法に関するコメント [3] コルモゴロフ・アーノルドネットワークの訓練におけるカツマルツアルゴリズム
![\displaystyle \mathbb {E} \left.\left[x^{k+1}-x^{*}\right|x^{k}\right]=\left(IB^{-1}\mathbb {E} [Z]\right)\left[x^{k}-x^{*}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72122d8f63d0021170676a6eee7eea1f0b961db3)
![{\displaystyle \mathbb {E} \left[x^{k+1}-x^{*}\right]=(IB^{-1}\mathbb {E} [Z])\mathbb {E} \left[x^{k}-x^{*}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fba5fcaf63644d27a40e57bddb56260db77f085a)
![{\displaystyle \rho :=\left\|IB^{-{\frac {1}{2}}}\mathbb {E} [Z]B^{-{\frac {1}{2}}}\right\|_{B}=\lambda _{\max }\left(IB^{-1}\mathbb {E} [Z]\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7b159ae1e4bfd476daf7b2d1fb663576fcbc854)
![\displaystyle \left\|\mathbb {E} \left[x^{k}-x^{*}\right]\right\|_{B}\leq \rho ^{k}\|x^{0}-x^{*}\|_{B}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8b5f91f15ae8f2551d8307f970ee9c379d3b679)
![\displaystyle \mathbb {E} \left\|\left[x^{k}-x^{*}\right]\right\|_{B}^{2}\leq \rho ^{k}\left\|x^{0}-x^{*}\right\|_{B}^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b0934fd41c6b4698918b7440906f14cdeb7c07e)
![{\displaystyle \left\|\mathbb {E} \left[xx^{*}\right]\right\|^{2}=\mathbb {E} \left[\left\left\|xx^{*}\right\|^{2}\right]-\mathbb {E} \left[\|x-\mathbb {E} [x]\|^{2}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59de3fd31c633934ef1b0bf20a52ef00e0359549)
![{\displaystyle \rho =\|IB^{-1}\mathbb {E} [Z]\|_{B}=1-{\frac {\lambda _{\min }(A^{T}A)}{\|A\|_{F}^{2}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d38cbac2e0daade1038d1effa3b992544a48df23)
