第 9 回
一般化逆行列と
特異値分解
はじめに (1)
•
連立一次方程式Ax = b
の解は,A
が正則で あれば,A
の逆行列A −1
を用いることによ り,x = A − 1 b
と書ける.A
が正則でない(あ
るいは正方行列でない)場合にこの考え方を 拡張したものが一般化逆行列である.•
固有値を正方でない行列に適用できるように 拡張したものが特異値である.•
工学では連立一次方程式は応用上解くべき問 題を数式で表現することで得られるが,数式 表現を作る際に,変数の数と方程式の数が合 わないということがよく起こる. したがって, 正方行列を前提とした数学的手法は不自由で あって,一般化逆行列や特異値といった考え 方が必要になる.一般化逆行列 (1)
•
一般化逆行列の考え方を理解するために,A
をm
行n
列の行列とし,連立一次方程式Ax = b
を解く問題を考える.•
行列A
のランクをr
とする(r ≤ min { m, n } ).
• A
を基本変形によって階段行列に変形すると(空白の部分は零, ∗
の部分は任意)・・・
.. . 1 ∗ · · ·
.. . · · ·
r) 1 ∗
r + 1) ...
n)
一般化逆行列 (3)
• A
の行基本変形は,基本行列をA
に左から掛 けることに相当する.U L · · · U 1 A
が上記の 階段行列になったものとし,U = U L · · · U 1
と定義する.• β = U b
と定義する.• { j 1 , . . . , j n − r } = { 1, . . . , n } \ { i 1 , . . . , i r }
とす る. たたし,j 1 < · · · < j r
とする.• x
の添字を( i 1 , . . . , i r , j 1 , . . . , j n − r )
の順に並 べかえると, 次ページのようになる.
1 ∗ · · · ∗
. .. ... .. .
1 ∗ · · · ∗
x 1
.. . x i
rx j
1.. . x j
n−r
=
β 1
.. . β r β r+1
.. . β m
• x B = (x i
1, . . . , x i
r) T , x N = (x j
1, . . . , x j
n−r
) T , β 1 = (β 1 , . . . , β r ) T , β 2 = (β r+1 , . . . , β m ) T
と おく. また,A B =
1 ∗
. ..
1
を前ページ の行列の左上のブロックとし,その右のブロッ クをA N
とおく.一般化逆行列 (7)
•
以上の定義を使うと, 先ほどの連立一次方程 式は, 次のように書ける.A B x B + A N x N = β 1 0 = β 2
•
数学的には, 解が存在するための必要十分条 件はβ 2 = 0
である. 当面はこれを仮定する.• A B
は正則だから, 連立一次方程式A B x B + A N x N = β 1
は解を持ち, その解はx B =
− A − B 1 A N x N + A − B 1 β 1
である.x N
はフリー パラメータである.•
解をまとめて書くと・・・x
Bx
N!
= − A
−1BA
NI
n−r!
x
N+ A
−B1I
r0
r×(m−r)U 0
(n−r)×m!
b
一般化逆行列 (9)
•
次に,x N
をb
から決めることを考える.x N
は任意だから,K
を任意のn − r
行m
列の行 列とし,x N = Kb
とすればよい. するとx
Bx
N!
= − A
−1BA
NK + A
−1BI
r0
r×(m−r)U K
! b
•
これは,A
が正則な場合の解の表現x = A − 1 b
と似た形になっている.• x B = A − B 1 β 1
以外の解を探す理由は・・・•
たとえば,x B
の各成分に消費エネルギーとい う物理的な意味がある場合には,フリーパラ メータをうまく調整して, 消費エネルギー最 小の解を求めることが望ましい.•
次ページの例を考える.一般化逆行列 (11)
• 10 − 1 0 1
0 1 0
!
x 1 x 2 x 3
= 1 1
!
• x 1 + x 2 + x 3
が小さい解が望ましいものとする• x 2 = 1
は一意的.x 1
とx 3
は一意的ではなく,10 − 3 x 1 + x 3 = 1
を満たせばよい.• (x 1 , x 3 ) = (10 3 , 0)
は解だが, (x1 , x 3 ) = (0, 1)
も解. 後者の方がx 1 + x 3
が小さい(この例で
は( x 1 , x 3 ) = (0 , 1)
がx 1 + x 2 + x 3
を最小に する解になっている)•
このように, 何らかの目的でフリーパラメー タを調整する可能性があるため,その調整の 余地を残しておきたい一般化逆行列 (13)
• A
が正則なら連立一次方程式Ax = b
の解 がx = A − 1 b
であることを踏まえ, 上記の例 のように, うまく「逆行列のような行列」A†
を取って,どのようなb
に対しても,Ax = b
が解を持つのであれば,x = A † b
が解を与え るようにしたい( A †
には調整の余地がある)•
このような条件を満たす行列A †
を,A
の一 般化逆行列(あるいは一般逆行列)
という.•
この定義でまず問題となるのは,一般化逆行 列が存在するか否かであるが, 我々はすでに ある種の一般化逆行列を構成している.一般化逆行列 (15)
• x = V (x T B , x T N ) T
とすると(V
は成分の並べ かえに対応する行列), 先に述べた結果から,V − A −1 B A N K + A −1 B
I r 0 r × (m − r)
U K
!
が 一般化逆行列になる.K
はフリーパラメータ から成る行列である.• A
をm
行n
列の行列とする. このとき,n
行m
列の行列A †
がA
の一般化逆行列であるた めの必要十分条件は,AA † A = A
となることである
(証明は次ページ)
•
したがって, 一般化逆行列をひとつ決めると いうことは,AA † A = A
を満たすA †
をひと つ決める, ということである.• rank( A, b ) = rank A
であるということは,あるn
次のベクトルz
が存在し,b = Az
となるということである. この性質を使って 先に述べた等価性を示す.• A
†b
が任意のb = Az
に対してAx = b
の解になっているという ことは,∀ z, AA
†Az = Aζ ,
すなわちAA
†A = A
を意味する.•
逆に,AA
†A = A
とすると,b = Az
に対し,x = A
†b = A
†Az
とおくと,Ax = AA
†Az = Az = b
だから,x = A
†b
はAx = b
の解である. よって,A
†はA
の一般化逆行列である.•
次に, 一般化逆行列を完全に特徴付ける. ま ず第一に,A † b
はAx = b
の解だから,A †
はn
行m
列の行列でなければならない.• U AV = A B A N
0 0
!
に列基本変形を施して
A B
を単位行列に変え,A N
を消去する. 対応 する基本行列をV ′
とすると・・・一般化逆行列 (19)
• U AV V ′ = I r 0 r × (n − r)
0 (m − r)× r 0 (m − r)×(n − r)
!
• V V ′ = W
と定義し, 上式に左からU − 1 ,
右 からW −1
を掛けると・・・A = U − 1 I r 0 r ×(n − r)
0 (m − r) × r 0 (m − r) × (n − r)
!
W − 1
• A † = W D 1 D 2 D 3 D 4
!
U
とおき,D 1
からD 4
までが満たすべき条件を求める. ただしD 1
はr
次の正方行列である.D 2
等の行と列の 大きさは, ここから自動的に決まる.• AA † A = A
にこれらを代入すると・・・一般化逆行列 (21)
U −1
D 1 0 r
× (n − r)
0 (m
− r) × r 0 (m
− r) × (n − r)
W −1 = U −1
I r 0 r
×(n − r)
0 (m
− r) × r 0 (m
− r) × (n − r)
W −1
したがって,D 1 = I r
で,D 2 , D 3 , D 4
は任意.U
とW
は正則行列だが,一意的ではない.•
一般化逆行列が持つ自由度を利用して,何ら かの意味(後述)
で都合が良い一般化逆行列 を構成する, ということがおこなわれる.•
上記に関する議論に先立って, まずQR
分解 について説明する.QR 分解 (1)
• A
をm
行n
列で階数r
の実あるいは複素行 列とする.• A
の列をならべかえることで,A
の左側のr
個の列ベクトルが線形独立であるようにでき る. このような列の並べかえに対応する行列 をP
とし,AP = (α 1 , . . . , α r , α r+1 , . . . , α n )
とする. (α 1 , . . . , α r )
は線形独立である.• (α 1 , . . . , α r )
からGram-Schmidt
の直交化法 によって作った正規直交系を(v 1 , . . . , v r )
とし
(実あるいは複素内積を使う),
これらを含む正規直交基底
(v 1 , . . . , v r , v r+1 , . . . , v m )
を 構成する. このとき,α i (1 ≤ i ≤ r)
は( v 1 , . . . , v r )
の線形結合である.QR 分解 (3)
• (α r+1 , . . . , α n )
は(α 1 , . . . , α r )
に線形従属だから, これらは
( v 1 , . . . , v r )
の線形結合となる.
•
以下しばらく,標準基底を固定し,ベクトルを 標準基底に関する数ベクトルと同一視する.• Q = (v 1 , . . . , v m )
とする.• A
が実行列の場合には,Q
は直交行列で,次 式が成り立つ.Q
T(AP ) =
⌣
1· · · ⌣
r r+1⌣ · · · ⌣
n1) ∗ · · · ∗ · · · · ∗
... . .. ... ...
r) ∗ · · · · ∗
r + 1) .. . m )
QR 分解 (5)
• A
が複素行列の場合には,Q
はユニタリ行列 で, 次式が成り立つ.Q
∗(AP ) =
⌣
1· · · ⌣
r r+1⌣ · · · ⌣
n1) ∗ · · · ∗ · · · · ∗
... . .. ... ...
r) ∗ · · · · ∗
r + 1) .. . m )
•
いずれの場合も, 右辺の行列をR
とすると,AP = QR
となる. このような行列の分解 表現をQR
分解という.•
以上で見たように, 任意の実あるいは複素行 列は,適切に列をならべかえることで, QR分 解できる.QR 分解 (7)
• QR
分解でR = R 1 R 2
0 (m − r) × r 0 (m − r) × (n − r)
!
とおくと,
R
の右下がりの対角線より下の要 素はすべて零で(このような行列を上三角行
列などという),Q
がAP
の左側のr
列からGram-Schmidt
の直交化法により構成されていることから,
R 1
は正則である.• Ax = b
を満たす解が複数あるとき, その解 の中でノルムが最小のものを与える一般化逆 行列を最小ノルム型一般化逆行列といい,A ∨
であらわす.•
以下の議論では, 重複を避けるため,A
が複 素行列の場合のみを考える. 実行列では,∗
をT
に置き換えればよい.最小ノルム型一般化逆行列 (2)
• A ∗ P
がQR
分解できるような置換行列P
を 取り,AP = QR
とする.Q ∗ AP = R
だか ら,P ∗ AQ = R ∗ = R ∗ 1 0
R ∗ 2 0
!
である.
•
上記の右辺が階段行列となるように行基本変 形を施す.• T
をこれに対応する基本行列の積とし,S = T P ∗
と定義すると,SAQ = I r 0
0 0
!
•
上記が一般化逆行列の「一般形」と異なるの は,Q
がユニタリ行列に限定されていること である. このようにするのは,ベクトルの直 交性を議論に組み込むため.最小ノルム型一般化逆行列 (4)
• z = Qx
とおくと, 解くべき連立一次方程式 はSAQz = Sb
となる.Sb
の第1
要素から 第r
要素までをならべたベクトルをβ 1 ,
残り をβ 2
とする.• β 2 = 0
のとき,I r 0 0 0
!
z = β 1 β 2
!
のノル ム最小の解は・・・
• z = I r D 2 0 D 4
! β 1 β 2
!
がノルム最小の解で,
β 2 = 0
を仮定するから,D 2
とD 4
は任意.•
もとの座標系ではx = Q I r D 2 0 D 4
!
Sb
最小ノルム型一般化逆行列 (6)
•
以上により, 最小ノルム型一般化逆行列の一 般形は次の通り：A ∨ = Q I r D 2 0 D 4
!
S .
これも一意的ではな く,D 2
とD 4
は任意である.•
最小ノルム型一般化逆行列では,Ax = b
の 解の中から, ノルムが最小のものを求めた.•
工学的な応用問題では, 誤差などのために,Ax = b
が厳密解を持たないことがあり得る.このような状況で,
k Ax − b k
を最小にする 近似解を求める問題を考える.最小二乗型一般化逆行列 (2)
•
最小ノルム型一般化逆行列でA
に左からユ ニタリ行列(直交行列)
を掛けたことと比較 すると,A
に右からユニタリ行列(直交行列)
を掛け,先と類似した計算をおこなうことで, 近似解が構成できると考えられる. これに対 応する一般化逆行列を最小二乗型一般化逆行 列といい,A ∧
であらわす.• A
を複素行列とする. 実行列では,∗
をT
に置き換えればよい.• A
をm
行n
列とし,AP
がQR
分解できるよ うな置換行列P
を取る.AP = QR, R =
R 1 R 2 0 0
!
とする.
R 1
は正則な上三角行列 である.最小二乗型一般化逆行列 (4)
• Q ∗ AP = R
であるが, この両辺に列基本変 形を施して,R 1
を単位行列に変形する. これ に対応する基本行列の積をV
とし,P V = T
とおくと,Q ∗ AT = I r 0
0 0
!
である.
• x = T z
とおき,Ax = b
の両辺にQ ∗
を左か ら掛けると,Q ∗ AT z = Q ∗ b .
• z 1 = (z 1 , . . . , z r ) T , z 2 = (z r+1 , . . . , z n ) T
と すると, 解を最小二乗近似するには,z 1 = (I r , 0)Q ∗ b
とすればよく,z 2
は任意である.よって,解の一般形は,
z = I r 0 D 3 D 4
!
Q ∗ b.
最小二乗型一般化逆行列 (6)
•
もとの座標系では,x = T I r 0 D 3 D 4
! Q ∗ b,
よってA ∧ = T I r 0
D 3 D 4
!
Q ∗
であり,D 3
とD 4
は任意である.• Moore-Penrose
の一般化逆行列(A +
と書く) は, 最小ノルム型と最小二乗型の一般化逆行 列の特徴を併せ持つ一般化逆行列である. そ の導出には, 一般化逆行列のフリーパラメー タをすべて使う.• A
を複素行列とする. 実行列では,∗
をT
に置き換えればよい.Moore-Penrose の一般化逆行列 (2)
• A ∗ P
がQR
分解できるような置換行列P
を 取り, 対応するQR
分解をA ∗ P = Q 1 R
と する.R = R 1 R 2
0 0
!
で,
R 1
は上三角な正 方行列,Q 1
はユニタリ行列である.P
は置 換行列だからユニタリ行列であることに注意 する.• P ∗ AQ 1 = R ∗
であるが, 更にR ∗
をQR
分 解する.R
の最初のr
個の列ベクトルは線形 独立なので,R ∗
は置換なしでQR
分解でき,R ∗ = Q 2 R r 0
0 0
!
という形になる
(後半の
零のみから成る列はQR
分解で形を変えない ことに注意).Moore-Penrose の一般化逆行列 (4)
• Q 3 = P Q 2
とおくと,Q ∗ 3 AQ = R r 0 0 0
!
で ある.x = Q 1 z
とおくと,Q ∗ 3 AQ 1 z = Q ∗ 3 b
であり,したがって,Ax = b
のノルムが最小 の最小二乗解はz = R − r 1 0
0 0
!
Q ∗ 3 b
である.•
もとの座標系では,x = Q 1 R −1 r 0 0 0
! Q ∗ 3 b ,
よって
A + = Q 1 R −1 r 0 0 0
!
Q ∗ 3
がA
のMoore-
Penrose
の一般化逆行列である. これはフリーパラメータを持たない.
計算例
A =
2 1 0 0 0 0 3 0 0 0 0 0 0 0 0
とおき,A
+を求める.Q
∗3AQ
1= R
r0 0 0
!
となる
Q
∗3とQ
1を求める必要があるが,A
ははじめから求める形に なっているので,Q
∗3= I , Q
1= I
としてよい. よって,A
+=
1 2
−
160 0
130
0 0 0
0 0 0
0 0 0
. A
+の左上のブロックが2 1 0 3
!
の逆行列になって
いることに注意.
•
固有値は, 行列に対応する線型写像の作用の「倍率」を測る尺度のひとつであるが,正方行 列に対してしか定義できない.
•
正方でない行列に対して固有値と似た性質を 持つ量が定義できると便利.•
この役割を果たすのが特異値である.特異値分解 (2)
•
特異値は, 正方とは限らない実行列あるいは 複素行列に対して定義される(関数行列に拡
張されることもある)•
以下では, 議論の重複を避けるために,A
をm
行n
列の複素行列とする. 実行列について は,∗
をT
で読み換えればよい.• A ∗ A
の正の固有値の平方根をA
の特異値という
(零固有値を無視することに注意).
• A ∗ A
はHermite
行列であるから,ユニタリ行 列によって対角化され, またA ∗ A
の固有値 はすべて非負なので, その特異値は曖昧さな く定まる.特異値分解 (4)
• A ∗ A
がr
個の正の固有値を持つものとし,こ れらを大きい順に並べたものをλ 1 , . . . , λ r
と する. 特異値は(σ 1 , . . . , σ r ) = ( √
λ 1 , . . . , √ λ r )
である.• (λ 1 , . . . , λ r )
に対応する固有ベクトルを{ v 1 , . . . , v r }
とする. また,{ v r+1 , . . . , v n }
を, 零固有値に対応する固有ベクトルとする.• A ∗ A
はHermite
行列なので,{ v 1 , . . . , v r }
を 正規直交系にすることができる.•
標準基底を取り,v i
を, それを標準基底によ り成分表示した列ベクトルと同一視する.• 1 ≤ i ≤ r
に対し,u i = 1
σ i Av i
と定義する.特異値分解 (6)
• u ∗ i u j = σ 1
i
σ
jv ∗ i A ∗ Av j = δ ij
である(δ ij
はKronecker
のデルタ). よって,{ u 1 , . . . , u r }
は正規直交系である. これを含む正規直交基 底{ u 1 , . . . , u r , u r+1 , . . . , u m }
を作る.• 1 ≤ i, j ≤ r
に対し,u ∗ i Av j = σ 1
i
v ∗ i A ∗ Av j =
λ
jσ
iv ∗ i v j = σ i δ ij
であることに注意• ker A = { x : Ax = 0 }
とおく. kerA =
ker A ∗ A
であることを示す.Ax = 0
ならA ∗ Ax = 0
だから, kerA ⊂ ker A ∗ A.
逆 に,x ∈ ker A ∗ A
であれば,A ∗ Ax = 0
より,x ∗ A ∗ Ax = 0.
よって,Ax = 0.
したがって,x ∈ ker A.
ゆえにker A ∗ A ⊂ ker A.
特異値分解 (8)
• v r+1 , . . . , v n
はA ∗ A
の零固有値に対応する固有ベクトルだから,
A ∗ Av j = 0 (j ≥ r + 1).
したがって, 先に述べた結果より,
Av j = 0 ( j ≥ r + 1)
である.• r + 1 ≤ i ≤ m, 1 ≤ j ≤ r
に対し,u ∗ i Av j =
u ∗ i σ j u j = 0
である(正規直交基底だから).
• V = (v 1 , . . . , v r , v r+1 , . . . , v n ),
U = ( u 1 , . . . , u r , u r+1 , . . . , u m )
とおき, 以上 の結果をまとめると,U ∗ AV = diag( σ 1 , . . . , σ r ) 0
0 0
!
となる.
特異値分解 (10)
• A = U diag(σ 1 , . . . , σ r ) 0
0 0
!
V ∗
を,A
の特 異値分解という.•
特異値分解は, 最小二乗問題の解法, 伝達関 数のノルムの定義などに使われる. Moore-Penrose
の一般化逆行列もここから得られる.1. A =
1 1 1 1 0 0
とする.A
TA = 2 2
2 2 , det λ − 2 −2
−2 λ − 2 =
λ
2−4 λ
より,A
TA
の固有値は0
と4
である(実行列なので
∗がTに変わっていることに注意).
2.
標準基底を固定し,ベクトルを数ベクトルと同一視する.3. A
TA
の固有値4
と0
に対応する(正規化された)
固有ベクトルは それぞれv
1=
√121
1
!
, v
2う=
√121
−1
!
である.
A
の特異値は 唯一で,その値はσ
1= √
4 = 2
である.計算例
(2)
4. u
1=
σ11
