Block_matrix_pseudoinverse
「ブロック行列疑似逆行列」
数学、ブロック行列の擬似逆にするための式である擬似逆のパーティションマトリックス。これは、最小二乗法に基づく信号処理のパラメータを更新する多くのアルゴリズムを分解または近似するのに役立ちます。
コンテンツ
1 導出
2 最小二乗問題への適用
2.1 過剰決定最小二乗法での列ごとの分割 2.2 劣決定最小二乗法での行方向の分割
3 行列の反転に関するコメント
4 も参照してください
5 参考文献
6 外部リンク
導出
列ごとに分割された行列について考えてみます。
、∈ ×× 、∈ ×× 、 ≥ + 。
{{ begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}}、 quad mathbf {A} in mathbb {R} ^ {m times n}、 quad mathbf {B} in mathbb {R} ^ {m times p}、 quad m geq n + p。}
上記の行列がフルランクの場合、そのムーア・ペンローズ逆行列とその転置は次のようになります。+ =（（ []
）。 − 1[]+ =（（ []
）。 − 1 {{ begin {aligned} { begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}} ^ {+}＆= left（{ begin {bmatrix} mathbf { A}＆ mathbf {B} end {bmatrix}} ^ { textsf {T}} { begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}} right）^ { -1} { begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}} ^ { textsf {T}}、\ { begin {bmatrix} mathbf {A} ^ { textsf {T}} \ mathbf {B} ^ { textsf {T}} end {bmatrix}} ^ {+}＆= { begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}} left（{ begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}} ^ { textsf {T}} { begin {bmatrix} mathbf {A }＆ mathbf {B} end {bmatrix}} right）^ {-1}。 end {aligned}}}
この疑似逆行列の計算には、（n + p）-正方行列の反転が必要であり、ブロック形式を利用しません。
計算コストをn-およびp-正方行列の反転に削減し、並列処理を導入してブロックを個別に処理するには、を導き出します。+ =
[ ⊥ （（NS ⊥
NS）。 − 1 ⊥ （（NS ⊥
NS）。− 1 ] =
[ （（⊥
NS）。 + （（⊥
NS）。 + ][]+ =
[ ⊥ （（NS ⊥
NS）。− 1
、 ⊥ （（NS ⊥
NS）。− 1 ] =
[ （（NS ⊥
）。 + （（NS ⊥
）。 + ] {{ begin {aligned} { begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}} ^ {+}＆= { begin {bmatrix} mathbf {P} _ {B} ^ { perp} mathbf {A} left（ mathbf {A} ^ { textsf {T}} mathbf {P} _ {B} ^ { perp} mathbf {A} right ）^ {-1} \ mathbf {P} _ {A} ^ { perp} mathbf {B} left（ mathbf {B} ^ { textsf {T}} mathbf {P} _ { A} ^ { perp} mathbf {B} right）^ {-1} end {bmatrix}} = { begin {bmatrix} left（ mathbf {P} _ {B} ^ { perp} mathbf {A} right）^ {+} \ left（ mathbf {P} _ {A} ^ { perp} mathbf {B} right）^ {+} end {bmatrix}}、 \ { begin {bmatrix} mathbf {A} ^ { textsf {T}} \ mathbf {B} ^ { textsf {T}} end {bmatrix}} ^ {+}＆= { begin {bmatrix} mathbf {P} _ {B} ^ { perp} mathbf {A} left（ mathbf {A} ^ { textsf {T}} mathbf {P} _ {B} ^ { perp} mathbf {A} right）^ {-1}、 quad mathbf {P} _ {A} ^ { perp} mathbf {B} left（ mathbf {B} ^ { textsf {T}} mathbf {P} _ {A} ^ { perp} mathbf {B} right）^ {-1} end {bmatrix}} = { begin {bmatrix} left（ mathbf { A} ^ { textsf {T}} mathbf {P} _ {B} ^ { perp} right）^ {+}＆ left（ mathbf {B} ^ { textsf {T}} mathbf {P} _ {A } ^ { perp} right）^ {+} end {bmatrix}}、 end {aligned}}}
ここで、正射影行列は次のように定義されます。 ⊥= I
− （（NS）。 − 1 、 ⊥= I
− （（NS）。 − 1 。
{{ begin {aligned} mathbf {P} _ {A} ^ { perp}＆= mathbf {I}- mathbf {A} left（ mathbf {A} ^ { textsf {T }} mathbf {A} right）^ {-1} mathbf {A} ^ { textsf {T}}、\ mathbf {P} _ {B} ^ { perp}＆= mathbf { I}- mathbf {B} left（ mathbf {B} ^ { textsf {T}} mathbf {B} right）^ {-1} mathbf {B} ^ { textsf {T}} 。 end {aligned}}}
上記の式は、次の場合に必ずしも有効ではありません。
{{ begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}}}
フルランクではありません-たとえば、 ≠ 0 { mathbf {A} neq 0}
、 それから + =1 2 ≠ [ （（⊥ ）。 + （（⊥ ）。+ ] = 0
{{ begin {bmatrix} mathbf {A}＆ mathbf {A} end {bmatrix}} ^ {+} = { frac {1} {2}} { begin {bmatrix} mathbf { A} ^ {+} \ mathbf {A} ^ {+} end {bmatrix}} neq { begin {bmatrix} left（ mathbf {P} _ {A} ^ { perp} mathbf {A} right）^ {+} \ left（ mathbf {P} _ {A} ^ { perp} mathbf {A} right）^ {+} end {bmatrix}} = 0}
上記の行列がフルランクの場合、そのムーア・ペンローズ逆行列とその転置は次のようになります。+ =（（ [] 最小二乗問題への適用
上記と同じ行列が与えられた場合、次の最小二乗問題を検討します。これらは、信号処理における複数の目的の最適化または制約された問題として表示されます。最終的には、次の結果に基づいて、最小二乗法の並列アルゴリズムを実装できます。
過剰決定最小二乗法での列ごとの分割
解決策を考えてみましょう =
{ mathbf {x} = { begin {bmatrix} mathbf {x} _ {1} \ mathbf {x} _ {2} \ end {bmatrix}}}
過剰決定系を解決します。=、∈ ××
1 {{ begin {bmatrix} mathbf {A}、＆ mathbf {B} end {bmatrix}} { begin {bmatrix} mathbf {x} _ {1} \ mathbf {x} _ {2} \ end {bmatrix}} = mathbf {d}、 quad mathbf {d} in mathbb {R} ^ {m times1}。}
ブロック行列の疑似逆行列を使用すると、次のようになります。= += [ （（⊥ ）。 + （（⊥ ）。 + ]。
{ mathbf {x} = { begin {bmatrix} mathbf {A}、＆ mathbf {B} end {bmatrix}} ^ {+} 、 mathbf {d} = { begin {bmatrix } left（ mathbf {P} _ {B} ^ { perp} mathbf {A} right）^ {+} \ left（ mathbf {P} _ {A} ^ { perp} mathbf {B} right）^ {+} end {bmatrix}} mathbf {d}。}
したがって、分解されたソリューションが 1 = （（⊥
NS）。+、 2 = （（⊥
NS）。 +。 { mathbf {x} _ {1} = left（ mathbf {P} _ {B} ^ { perp} mathbf {A} right）^ {+} 、 mathbf {d}、 quad mathbf {x} _ {2} = left（ mathbf {P} _ {A} ^ { perp} mathbf {B} right）^ {+} 、 mathbf {d}。}
劣決定最小二乗法での行方向の分割
解決策を考えてみましょう { mathbf {x}}
劣決定システムを解決します。
[]= e ∈ ×× 1 、∈ ××
1 {{ begin {bmatrix} mathbf {A} ^ { textsf {T}} \ mathbf {B} ^ { textsf {T}} end {bmatrix}} mathbf {x} = { begin {bmatrix} mathbf {e} \ mathbf {f} end {bmatrix}}、 quad mathbf {e} in mathbb {R} ^ {n times 1}、 quad mathbf {f} in mathbb {R} ^ {p times1}。}
最小ノルム解は次の式で与えられます。=
[] + { mathbf {x} = { begin {bmatrix} mathbf {A} ^ { textsf {T}} \ mathbf {B} ^ { textsf {T}} end {bmatrix}} ^ {+} 、{ begin {bmatrix} mathbf {e} \ mathbf {f} end {bmatrix}}。}
ブロック行列の疑似逆行列を使用すると、次のようになります。=
[ （（NS ⊥
）。 + （（NS ⊥
）。+ ] =（（NS ⊥
）。+ e + （（NS ⊥ ）。 +。
{ mathbf {x} = { begin {bmatrix} left（ mathbf {A} ^ { textsf {T}} mathbf {P} _ {B} ^ { perp} right）^ { +}＆ left（ mathbf {B} ^ { textsf {T}} mathbf {P} _ {A} ^ { perp} right）^ {+} end {bmatrix}} { begin { bmatrix} mathbf {e} \ mathbf {f} end {bmatrix}} = left（ mathbf {A} ^ { textsf {T}} mathbf {P} _ {B} ^ { perp } right）^ {+} 、 mathbf {e} + left（ mathbf {B} ^ { textsf {T}} mathbf {P} _ {A} ^ { perp} right）^ {+} 、 mathbf {f}。}
行列の反転に関するコメント
それ以外の（（
）。 − 1
{ mathbf { left（{ begin {bmatrix} mathbf {A}＆ mathbf {B} end {bmatrix}} ^ { textsf {T}} { begin {bmatrix} mathbf {A }＆ mathbf {B} end {bmatrix}} right）} ^ {-1}}
、直接的または間接的に計算する必要があります （（NS）。 − 1 （（NS）。 − 1 （（NS ⊥
NS）。 − 1 （（NS ⊥
NS）。 − 1 { left（ mathbf {A} ^ { textsf {T}} mathbf {A} right）^ {-1}、 quad left（ mathbf {B} ^ { textsf {T} } mathbf {B} right）^ {-1}、 quad left（ mathbf {A} ^ { textsf {T}} mathbf {P} _ {B} ^ { perp} mathbf { A} right）^ {-1}、 quad left（ mathbf {B} ^ { textsf {T}} mathbf {P} _ {A} ^ { perp} mathbf {B} right ）^ {-1}。}
密集した小さなシステムでは、特異値分解、QR分解、またはコレスキー分解を使用して、行列の反転を数値ルーチンに置き換えることができます。大規模なシステムでは、クリロフ部分空間法などの反復法を採用する場合が
並列アルゴリズムを考慮すると、次のように計算できます。（（）。 − 1
{ left（ mathbf {A} ^ { textsf {T}} mathbf {A} right）^ {-1}}
と（（）。 − 1
{ left（ mathbf {B} ^ { textsf {T}} mathbf {B} right）^ {-1}}
並行して。次に、計算を終了します（（NS ⊥ ）。 − 1
{ left（ mathbf {A} ^ { textsf {T}} mathbf {P} _ {B} ^ { perp} mathbf {A} right）^ {-1}}
と（（NS ⊥ ）。 − 1
{ left（ mathbf {B} ^ { textsf {T}} mathbf {P} _ {A} ^ { perp} mathbf {B} right）^ {-1}}
並行して。
も参照してください
可逆行列§ブロック単位の反転
参考文献
^ JKBaksalaryおよびOMBaksalary（2007）。「列方向に分割された行列のムーア・ペンローズ逆行列の特定の式」。線形代数Appl。421：16–23。土井：10.1016 /j.laa.2006.03.031。
外部リンク
マイクブルックスによるマトリックスリファレンスマニュアル
ジョン・ブルカルトによる線形代数用語集
カーレブラントピーターセンによるマトリックスクックブック
講義8： tanford.edu/~boyd/ Stephen P.Boydによる未決定方程式の最小ノルム解”