レッスン 12 CS 分解

再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
レッスン 12
CS 分解
CS 分解
このレッスンでは特異値分解の応用として Paige-Saunders 型 CS 分解を学ぶ。これはユニタリ
行列（このレッスンでは便宜上実直交行列）を任意に 4 分割し、すべてのブロックを（8 個で
はなく）4 個の直交行列によって同時特異値分解するものである。結果は、各ブロック間の特異
値はすべて 0 と 1 の間にあり、これらが単純な関係で結ばれていることを示す。特異値 1、0 と
他特異値が陽に区別されている点にも特徴があり、これと分割の任意性が一般性と使いやすさ
の素になっている。つぎに、応用への予備知識として、正射影を丁寧に解説する。ついで応用
−1
−1
例として、二つの部分空間間の距離の評価、B を陽に計算することなく行う AB 型行列の特
異値分解法を学ぶ。CS 分解はさらに商 CS 分解 Quotient CS decomposition と積 CS 分解
Product CS decomposition に発展するが、これらについては参考文献に譲る。Stewart[5], p.77
によれば、
「CS 分解」という名称は Stewart 自身の命名による。
このレッスンの準備には次の文献（とくに論文[2]）を一次資料として利用した。この場を
借りて著者各位に深甚の謝意を表す。
[1] G. H. Golub and C. F. Van Loan, Matrix Computations, Third Edition, The Johns
Hopkins University Press, 1996, 75-79
[2] C.C. Paige and M. A. Saunders, Towards a generalized singular value decomposition,
SIAM Journal in Numerical Analysis 18, 398-405 (1981)
[3] C. C. Paige and M. Wei, History and generality of the CS decomposition, Linear Algebra
and Its Applications 208 / 209, 303-326 (1994)
[4] G. W. Stewart, On the perturbation of pseudo-inverses, projections and linear least
square problems, SIAM Review 19, 634-662 (1977)
[5] G. W. Stewart, Matrix Algorithms, Volume I, Basic Decompositions, SIAM, 1998, 73-77
12.1
Paige - Saunders 型 CS 分解
直交行列を 4 分割し、すべてのブロックを個別に特異値分解すれば、8 個の直交行列を必
要とする。
これを 4 個のみの直交行列を用いて、
同時に特異値分解できる、
というのが Paige and
Saunders 型 CS 分解の主張である。これを可能にするのは、むろん、親行列の直交性である。
P-S 型 CS 分解は薄型 CS 分解( Golub & Van Loan[1], p.77)、Stewart 型 CS 分解
( Stewart[3], TheoremA.1, [4], Theorem 4.38, p.75)の一般化に相当する。この節では P-S 型 CS
分解形の説明のみを行い、証明は次節で行う。
⎡m × k
⎡Q11 Q12 ⎤ ⎢
与えられた直交行列 Q を Q = ⎢
⎥=⎢
⎣Q 21 Q 22 ⎦ ⎢ p × k
⎣
Copyright 再履修線形代数研究会
m × q⎤
⎥ と分割するものとする。ここ
⎥
p × q ⎥⎦
1
再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
CS 分解
に、 k , m, p, q の大小関係についての制約はまったくない。
⎡x x x
⎢
分割例： Q = ⎢
⎢x x x
⎢
⎣x x x
x⎤
⎥ ⎡1× 3 1× 1 ⎤
⎥ = ⎡Q11 Q12 ⎤
⎥=⎢
⎥ ⎢Q Q ⎥
x⎥ ⎢
⎣ 21 22 ⎦
⎥ ⎢ 2 × 3 2 × 1 ⎦⎥
x⎦ ⎣
すると、適当な直交行列 U1 （ m 次）、 U 2 （ p 次）、 V1 （ k 次）、 V2 （ q 次）をとれば、
次の P-S 型 CS 分解が成立する（記号使いは[2]より踏襲）：
⎡ U1T 0 ⎤ ⎡Q11 Q12 ⎤ ⎡ V1 0 ⎤ ⎡ U1T Q11V1 U1T Q12 V2 ⎤ ⎛ m ⎞
⎥ ⎜ ⎟
⎢
⎥⎢
⎥⎢
⎥=⎢
T
(1) U QV ≡ ⎢⎣ 0 U 2T ⎥⎦ ⎣Q 21 Q 22 ⎦ ⎣ 0 V2 ⎦ ⎣⎢ U 2T Q 21V1 U 2T Q 22 V2 ⎦⎥ ⎝ p ⎠
q )
( m p)
( k q)
( k
⎡I
⎢
⎢
⎢
⎢
=⎢
⎢0
⎢ S
⎢
⎢
⎣
(r
⎤
⎥
C
S
⎥
0C
I ⎥
⎥
⎥
⎥
I
⎥
−C
S
⎥
⎥
I
0 CT ⎦
s k − r − s p − k + r s m − r − s)
0S T
⎛r
⎜
⎜s
⎜m−r − s
⎜
⎜
⎜ p−k +r
⎜
⎜s
⎜k −r − s
⎝
⎞
⎟
⎟
⎟
⎟
⎟ ⎡ Σ11 Σ12 ⎤
⎟ ≡ ⎢Σ Σ ⎥ ≡ Σ
⎟ ⎣ 21 22 ⎦
⎟
⎟
⎠
この最終形 Σ を便宜上（Paige & Saunders 型 CS 分解の）標準形と呼ぶことにする。
説明を追加する：
Σ 自体も直交行列を表す（∵ U, V, Q は直交行列）
(b) 空欄部のブロックはすべて 0 ブロックを表す。 0C , 0S もゼロブロックを表す。
(c) 行列の傍に記した式は対応する行列の列数または行数を表す。例：U1 : m × m 、V2 : q × q 、
C : s × s 、 0C : ( m − r − s ) × ( k − r − s ) 。
(d) I, C, 0C , の中には空ブロックのものもあり得る。
(e) Q11 , , Q 22 の特異値は標準形内の対応するブロック Σ11 , , Σ 22 から直接読み取れる。
Q11 の特異値：これらは、後述するように、0 と 1 の間にあるので、これらを 1, ,1 （ r 個）、
(1 >) cr +1 ≥ ≥ cr + s (> 0) （ s 個）、 0, , 0 （ min{m, k} − r − s 個）に分類する。 r = 0 また
は s = 0 の場合もあり得る。そして、 diag{cr +1 , , cr + s } ≡ C 、 diag{sr +1 , , sr + s } ≡ S と定義
(a)
する。ここに、 si = 1 − ci , i = r + 1,
2
, r + s 。ゆえに、 0 < sr +1 ≤
≤ sr + s < 1 である。
ci = cos θi (0 < θi < π / 2) と書けば、 si = sin θi となる。CS 分解の名はここから来ている。
C−1 , S −1 の存在性と C2 + S 2 = I に注意のこと。
Q 21 の特異値： I k − r − s , S の対角成分および min{ p, k} − k + r 個の 0
Copyright 再履修線形代数研究会
2
再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
CS 分解
Q12 の特異値： I m − r − s , S の対角成分および min{m, q} − m + r 個の 0
Q 22 の特異値： I p − k + r , C の対角成分および min{m, k} − r − s 個の 0
ここに、 m +
p = k + q に注意。
(f) Σ11 , , Σ 22 のどれか一つが定まれば、r , s の値が定まり、従って標準形 Σ の形も確定する。
結局、Q11 , , Q 22 の特異値は、そのどれか一つの特異値がわかれば、一意的に定まってしまう。
⎡1 0 0 0 0 ⎤
⎢0 0 0 0 1 ⎥
⎢
⎥
⎢
⎥
Q
Q
0
1
0
0
0
⎡ 11 12 ⎤
例1 Q=⎢
=⎢
⎥ （ m = k = 3, p = q = 2 ） Q は確かに直交行列を
⎥
⎣Q 21 Q 22 ⎦ ⎢
⎥
⎢0 0 1 0 0 ⎥
⎢
⎥
⎣0 0 0 1 0 ⎦
⎡0 0 ⎤
⎡1 0 ⎤
T
表す。 Q 22 = ⎢
に着目すると、 Q 22 Q 22 = ⎢
⎥ だから、その特異値は {1, 0} によって与
⎥
⎣0 0 ⎦
⎣1 0 ⎦
えられる。これを一般形に照らせば、 p − k + r = 1, s = 0 。これより、 r = 2 が得られ、標準形
⎡I 2
⎢
⎢0
Σ=⎢
⎢
は
⎢ 0S
⎢0
⎣
(2
例2
I1
0S T 0 ⎤ ⎛ 2 ⎞
⎥
0 I1 ⎥ ⎜⎜ 1 ⎟⎟
⎥ ⎜ ⎟
⎥ ⎜ ⎟ によって与えられる。■
I1 0 ⎥ ⎜ 1 ⎟
0 0C ⎥⎦ ⎜⎝ 1 ⎟⎠
1
1
0
0C
0
1
)
⎡Q11 Q12 ⎤
⎥ のように分割したところ（ここに Q 21 : 5 × 1 ）、
⎣Q 21 Q 22 ⎦
ある 8 次直交行列 Q を Q = ⎢
Q 21 の特異値は α （ 0 < α < 1 ）であったという。 Σ を求めよ。まず、一般形(1)に照らせば、
⎡0 ⎤
T
m = 3, p = 5, k = 1, q = 7 、 Σ 21 = ⎢ ⎥ = [ 0 0 0 0 α ] （ S = [α ] :1× 1 ）、 r = 0, s = 1 のはず
⎣S ⎦
⎡C
⎢0
⎢
⎢
である。ゆえに、 Σ = ⎢
⎢0
⎢⎣S
(1
0
0
S
0
I4
0
0 −C
4
Copyright 再履修線形代数研究会
1
0 ⎤ ⎛1
I 2 ⎥⎥ ⎜⎜ 2
⎥⎜
⎥⎜
0 ⎥ ⎜4
0 ⎥⎦ ⎜⎝1
2 )
⎞
⎟
⎟
⎟
⎟ （ C = ⎡ 1 − α 2 ⎤ ）。■
⎣
⎦
⎟
⎟
⎠
3
再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
CS 分解
[ ]
例 3 ある 6 次直交行列の標準形 Σ の Σ 21 ブロックが 0 （ 1× 1 ）であるという。標準形は
⎡ I1
⎢0
⎢
Σ= ⎢
⎢
⎣0
(1
0 ⎤⎛ 1
I 4 ⎥⎥ ⎜⎜ 4
⎥⎜
⎥⎜
0 ⎦⎝ 1
4)
0
0
I1
1
⎞
⎟
⎟
⎟ によって与えられる。■
⎟
⎠
例 4 一般形(1)の特別の場合として、直交行列を上下または左右に 2 分割した場合を考える。
⎡Q11 ⎤
⎢
⎥
直交行列 Q =
⎢
⎥
⎢⎣Q 21 ⎥⎦
⎡I m
⎛m ⎞
⎢
⎜ ⎟
⎜ ⎟（ m + p = n ）の P-G 分解標準形は Σ = ⎢
⎜p⎟
⎢0
⎝ ⎠
⎣
る（∵ Q11Q11 = I m 、 Q 21Q 21 = I p ）。また、
T
T
⎡I k
⎣0
標準形は Σ = ⎢
Q = [Q11 Q12 ]
(k
q)
0⎤
⎥
⎥ によって与えられ
I p ⎥⎦
（ k + q = n ）と分割すれば、
0 ⎤
T
T
となる（∵ Q11 Q11 = I k , Q12 Q12 = I q ）。■
⎥
Iq ⎦
例5 最後の例として、標準形 Σ を区分けの形状に無関係に与えることはできないことを示す。
⎡0
⎢0
Σ=⎢
⎢
⎢
⎣x
x⎤
x ⎥⎥
型の標準形はあり得ない。仮に可能だとすれば、 Σ 自体も直交行列を表すは
⎥
⎥
x⎦
0
0
x
ずから、最初の 2 列は正規直交系をなすべきであるが、これは不可能である。ゆえに、標準形
[]
⎡I 0 ⎤
⎡C 0 ⎤
型、 [C] 型、または ⎢
⎥ 型の
⎥
⎣0 C⎦
⎣0 0 ⎦
の(1,1)ブロックはゼロブロックではあり得ず、 I 型、 ⎢
いずれかでなければならない。■
12.2
Paige-Saunders 型 CS 分解の証明
この節における記号の意味は 12.1 節から引き継ぐものとする。証明のポイントは直交性の
繰り返し利用である。
(I) Q 第 1 列の特異値分解
（ブロックとしての）第 1 列
QT Q = I n (n ≡ m + p = k + q) より、
に関して、 Q11 Q11 + Q 21 Q 21
T
T
= I k (∵ Q11 : m × k , Q 21 : p × k ) が成立する。ここに、左辺の各
Copyright 再履修線形代数研究会
4
再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
CS 分解
項は実対称行列を表す。第 1 項をシュール分解すれば、その固有値はすべて正または 0 でなけ
T
T
ればならないからこれを、 V1 Q11 Q11V1
T
T
ると、 V1 Q 21 Q 21V1
, ck 2 } （ c1 ≥
= diag{c12 ,
= I − V1T Q11T Q11V1 = diag{1 − c12 ,
Q 21T Q 21 の固有値は 1 − c12 ,
≥ ck ≥ 0 ）とする。す
,1 − ck 2 } となる。ゆえに
,1 − ck 2 によって与えられる。 Q 21T Q 21 の形からこれらもすべて
正または 0 でなければならないから、
1 ≥ c1 ≥
≥ ck ≥ 0 および 0 ≤ s1 ≡ 1 − c12 ≤
≤ sk ≡ 1 − ck 2 ≤ 1
が真でなければならない。
ここで、 c1 ,
の値を 1 のもの、1 と 0 の中間にあるもの、および０に分類し、1 のものの
個数を r 、中間にあるものの個数を s とすれば、
c1 =
s1 =
= cr = 1 > cr +1 ≥
= sr = 0 < sr +1 ≤
≥ cr + s > 0 = cr + s +1 =
≤ sr + s < 1 = sr + s +1 =
= ck
= sk
となる。これ以降
C ≡ diag{cr +1 ,
, cr + s }, S ≡ diag{sr +1 , , sr + s }
と書くことにする（対角成分 ci , si はすべて 0 < ci , si < 1 を満たすことに注意）。これまでの結果
をまとめると
(2)
V1T Q11T Q11V1 = diag{c12 ,
, ck 2 } = diag{I r , C2 , 0k − r − s } （ 1 ≥ c1 ≥
≥ ck ≥ 0 ）
(3)
V1T Q 21T Q 21V1 = diag{s12 ,
, sk 2 } = diag{0r , S 2 , I k − r − s } （ 0 ≤ s1 ≤
≤ sk ≤ 1 ）
この 2 式から
(4)
min{m, k} ≥ rank (Q11 ) = rank (Q11V1 ) = rank (V1T Q11T Q11V1 ) = r + s
(5)
min{ p, k} ≥ rank (Q 21 ) = rank (Q 21V1 ) = rank (V1T Q 21T Q 21V1 ) = s + (k − r − s ) = k − r
（∵ 一般に rank ( A A ) = rank ( AA ) = rank ( A ) ）
T
T
[
つぎに、 U1 , U 2 を構築する。 Q11V1 ≡ X ≡ x1
x k ] : m × k と書けば、(2)は
XT X = diag{I r , C2 , 0k − r − s }: k × k 、を意味し、これは X の列は互いに直交し、かつ
x1T x1 =
x r T x r = 1, x r +1T x r +1 = cr +12 ,
Copyright 再履修線形代数研究会
, x r + sT x r + s = cr + s 2 , x r + s +1 =
xk = 0
5
レッスン 12
再履修線形代数―分解定理を主軸に整理整頓
が成り立っていることを意味する。これより、 {x1 ,
, xr ,
CS 分解
x r +1
,
cr +1
,
xr +s
} は正規直交系を表す。
cr + s
~
ここで(5)式 min{m, k} ≥ r + s を考慮すると、m − r − s (≥ 0) 本のベクトル x r + s +1 ,
~
, x m を適当
に選択すれば、
⎡
U1 ≡ ⎢ x1
⎣
(6)
~ ⎤
xm ⎥ : m × m
⎦
xr +s ~
x r + s +1
cr + s
x r +1
cr +1
xr
が直交行列を表すようできる。すると
⎡
(7) U Q11V1 = U X = ⎢ x1
⎣
T
1
T
1
⎡I
= ⎢⎢0
⎢⎣0
(r
x
x r r +1
cr +1
xr +s ~
x r + s +1
cr + s
T
⎤
x m ⎥ [ x1
⎦
~
x r x r +1
xr +s 0
0]
0⎤ ⎛r
⎞
⎜
⎟
⎥
C
0⎥ ⎜ s
⎟
0
0 ⎥⎦ ⎜⎝ m − r − s ⎟⎠
s k − r − s)
0
[
つぎに、 Q 21V1 ≡ Z ≡ z1
z k ] : p × k と書けば、(3)は ZT Z = diag{0r , S 2 , I k − r − s }: k × k
となる。これは Z の列は直交し、かつ
z1 =
z r = 0, z r +1T z r +1 = sr +12 ,
, z r + sT z r + s = sr + s 2 , z r + s +1T z r + s +1 =
を示している。ここで、(5)より min{ p, k} ≥ k − r だから、
~
zkT zk = 1
p − k + r (≥ 0) 本のベクトル
~
z1 ,
, z p − k + r を適当に選択すれば、
(8)
⎡~
U 2 ≡ ⎢ z1
⎣
~
z p −k + r
z r +1
sr +1
z r +s
z r + s +1
sr + s
⎤
zk ⎥ : p × p
⎦
が直交行列を表すようにできる。すると
(9)
⎡~
U 2 Q 21V1 = U 2 Z = ⎢ z1
⎣
T
T
~
z p −k + r
Copyright 再履修線形代数研究会
z r +1
sr +1
zr+s
z r + s +1
sr + s
T
⎤
z k ⎥ [0
⎦
0 z r +1
z r + s z r + s +1
zk ]
6
再履修線形代数―分解定理を主軸に整理整頓
⎡ 0S
= ⎢⎢0
⎢⎣0
(r
0
S
0
s
レッスン 12
CS 分解
0 ⎤ ⎛ p−k +r⎞
⎜
⎟
0 ⎥⎥ ⎜ s
⎟
I ⎥⎦ ⎜⎝ k − r − s ⎟⎠
k − r − s)
以上をまとめると、
⎡I
⎢0
⎢
⎢0
⎡ U1T 0 ⎤ ⎡Q11 ⎤
⎢
⎢
⎥⎢
⎥ V1 = ⎢
(10) ⎢⎣ 0 U 2T ⎦⎥ ⎣Q 21 ⎦
⎢ 0S
⎢
⎢0
⎢0
⎣
(
r
0
C
0
0
S
0
0 ⎤⎛r
⎞
⎜
⎟
⎥
0 ⎥⎜s
⎟
0C ⎥ ⎜ m − r − s ⎟
⎟
⎥⎜
⎟
⎥⎜
0 ⎥⎜ p − k + r⎟
⎟
⎥⎜
0 ⎥⎜s
⎟
⎜
⎥
I ⎦ ⎝ k − r − s ⎟⎠
s k − r − s)
⎡Q11 ⎤
T
T
の列が正規直交系をなす、すなわち、 Q11 Q11 + Q 21 Q 21 = I k 、だけを使
⎥
⎣Q 21 ⎦
この式は ⎢
って導いた関係である。(10)式は Golub & Van Loan[1], p. 77 の薄型 CS 分解 thin version CS
decomposition に相当する。
(II)
Q 第 1 行の特異値分解
⎡Q11T Q 21T ⎤
も直交行列だから、その第 1 列に(I)の結果を適用すれば、
QT = ⎢ T
T⎥
⎢⎣Q12 Q 22 ⎥⎦
⎡I
⎢0
⎢
⎢0
⎡ V1T 0 ⎤ ⎡Q11T ⎤
⎢
U1 = ⎢
⎢
T⎥⎢
T⎥
⎢⎣ 0 V2 ⎦⎥ ⎣⎢Q12 ⎦⎥
⎢0
⎢ S
⎢0
⎢0
⎣
(r
0
C
0
0
S
0
0 ⎤⎛r
⎞
⎟
0 ⎥⎥ ⎜ s
⎜
⎟
0 CT ⎥ ⎜ k − r − s ⎟
⎥⎜
⎟
⎥⎜
⎟
0 ⎥⎜q − m+ r⎟
⎥⎜
⎟
0 ⎥⎜s
⎟
⎥
⎜
I ⎦ ⎝ m − r − s ⎟⎠
s m − r − s)
を満たす直交行列 V2 : q × q がとれる。ここに 0 S
Copyright 再履修線形代数研究会
: (q − m + r ) × r である。転置をとれば
7
再履修線形代数―分解定理を主軸に整理整頓
⎡I
V
0
⎡
⎤
⎢
1
T
(11) U1 [Q11 Q12 ] ⎢
=⎢ C
⎥
⎣0 V2 ⎦ ⎢0
⎣
レッスン 12
0
CS 分解
0⎤⎛r
⎞
⎥⎜
⎟
⎥⎜s
⎟
⎜
⎥
I ⎦ ⎝ m − r − s ⎟⎠
0S T
S
0C
0
(r s k − r − s q − m + r s
m − r − s)
以上(10)(11)を使うと
⎡ U1T 0 ⎤ ⎡Q11 Q12 ⎤ ⎡ V1 0 ⎤ ⎡ U1T Q11V1 U1T Q12 V2 ⎤ ⎛ m ⎞
⎥ ⎜ ⎟
⎢
⎥⎢
⎥=⎢
⎥⎢
(12) ⎣⎢ 0 U 2T ⎦⎥ ⎣Q 21 Q 22 ⎦ ⎣ 0 V2 ⎦ ⎢⎣ U 2T Q 21V1 U 2T Q 22 V2 ⎥⎦ ⎝ p ⎠
q )
( m p) (k q) ( k q)
( k
⎡I
⎢
⎢
⎢
⎢
=⎢
⎢0
⎢ S
⎢
⎢
⎣
(r
⎤
⎥
C
S
⎥
0C
I ⎥
⎥
⎥
X11
X12 X13 ⎥
⎥
S
X 21
X 22 X 23 ⎥
⎥
I
X31
X32 X33 ⎦
s k − r − s p − k + r s m − r − s)
0S T
⎛r
⎜
⎜s
⎜m−r − s
⎜
⎜
⎜ p−k +r
⎜
⎜s
⎜k −r − s
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
となる（ m +
p = k + q ゆえ、 p − k + r = q − m + r に注意）。
ここに X11 , , X33 は、未知行列であるが、以下で示すように、直交性を利用すれば定まる。
T
実際、(12)の左辺は直交行列を表すから、最終辺も直交行列を表す。C
= C 、ST = S 、CS = SC 、
C−1 , S −1 の存在性、を使うと、次の関係が出る：
2 列 ⊥ 4 列： S X 21 = 0 → X 21 = 0
T
2 列 ⊥ 5 列： C S + S X 22 = 0 → X 22 = −C
T
T
2 列 ⊥ 6 列： S X 23 = 0 → X 23 = 0
T
3 列 ⊥ 4 列： IX31 = 0 → X31 = 0
3 列 ⊥ 5 列： IX32 = 0 → X32 = 0
3 列 ⊥ 6 列： IX33 = 0 → X33 = 0 = 0C
T
3 行 ⊥ 4 行： IX13 = 0 → X13 = 0
(4 列) (4 列) = I ： X11 X11 = I
T
T
( X11 : ( p − k + r ) × ( p − k + r )) → X11 は p − k + r 次直交行列
Copyright 再履修線形代数研究会
8
再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
(5 列) (5 列) = I ： S + X12 X12 + C = I → X12 = 0 （∵ C
T
2
T
2
CS 分解
2
+ S2 = I ）
まとめると
⎡ X11 X12 X13 ⎤ ⎡ X11 0
⎢ X X X ⎥ = ⎢0 − C
(13)
⎢ 21 22 23 ⎥ ⎢
⎢⎣ X31 X32 X33 ⎥⎦ ⎢⎣0
0
0 ⎤
⎥
0 ⎥ （ X11 は p − k + r (= q − m + r ) 次直交行列）
0CT ⎥⎦
仕上げは X11 部が I p − k + r になるように U 2 または V2 の定義を変更すればよい。すなわち、
⎡ X11
I
U 2 を U 2 ⎢⎢
⎢⎣
⎡ X11T
⎤
⎥ ≡ U ' または V を V ⎢
I
2
2 ⎢
2
⎥
⎢
I ⎥⎦
⎣
⎤
⎥
'
'
⎥ ≡ V2 ' に変更すれば、U 2 , V2 も直交行
I ⎥⎦
列を表し、最終的に
⎡ U1T 0 ⎤ ⎡Q11 Q12 ⎤ ⎡ V1 0 ⎤ ⎡ U1T 0 ⎤ ⎡Q11 Q12 ⎤ ⎡ V1 0 ⎤
⎢
⎥⎢
⎥⎢
⎥
⎥⎢
⎥=⎢
⎥⎢
(14) ⎣⎢ 0 U 2 'T ⎦⎥ ⎣Q 21 Q 22 ⎦ ⎣ 0 V2 ⎦ ⎣⎢ 0 U 2T ⎦⎥ ⎣Q 21 Q 22 ⎦ ⎣ 0 V2 '⎦
( m p)
( k q)
⎡I
⎢
⎢
⎢
⎢
=⎢
⎢0
⎢ S
⎢
⎢
⎣
(r
⎤
⎥
C
S
⎥
0C
I ⎥
⎥
⎥
⎥
I
⎥
−C
S
⎥
T⎥
I
0C ⎦
s k − r − s p − k + r s m − r − s)
0S T
⎛r
⎜
⎜s
⎜m−r − s
⎜
⎜
⎜ p−k +r
⎜
⎜s
⎜k −r − s
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
証明は以上で完了した。ただし、 Q11 の特異値分解以降は Q 21 ,
に QR 分解を施すという
別法もあるので、これは腕試し問題とする（問題 12.8）。■
p ≥ m ≥ k の場合
p ≥ m ≥ k の場合に特化した Paige-Saunders 型 CS 分解について考える。このときは当然
q = m + p − k ≥ k となる。とくに、 p ≥ m = k の場合は、後述する「Stewart 型 CS 分解」
12.3
（Stewart [4, Theorem A.1]に還元することを示そう。
さて、 p ≥ m ≥ k 場合、P-S 型 CS 分解における Q11 、 Q 21 の特異値は、それぞれ
Copyright 再履修線形代数研究会
9
レッスン 12
再履修線形代数―分解定理を主軸に整理整頓
CS 分解
⎞
⎡I 0 0 ⎤ ⎛ r
⎡0 0 0 ⎤ ⎛ r
⎞
⎜
⎟
⎜
⎟
⎢
⎥
⎢
⎥
C ' ≡ ⎢0 C 0 ⎥ ⎜ s
⎟ 、 S ' ≡ ⎢0 S 0 ⎥ ⎜ s
⎟ 、（ C '2 + S '2 = I ）
(1)
⎜
⎢⎣0 0 0 ⎥⎦ ⎝ k − r − s ⎟⎠
⎢⎣0 0 I ⎥⎦ ⎜⎝ k − r − s ⎟⎠
( r s k − r − s)
( r s k − r − s)
の特異値（ C , S は k × k 行列ゆえそれぞれの対角成分 k 個）によって与えられる。ゆえに、P-S
'
'
型 CS 分解の標準形 Σ は次のようになる：
⎡I r
⎢
⎢0
⎢0
⎢
⎢0
Σ=⎢
⎢
⎢0
⎢
⎢0
⎢0
⎢
⎢⎣ 0
(r
⎡
⎢
⎢
=⎢
⎢
⎢
⎢
⎣
(
0
0
0
0
0
C
0
0
0
S
0
0
0
0
0
0
0
0
0
0
0
0
I p−k 0
0
0
0
0
Ir
0
S
0
0
0
−C
0
I k −r −s
0
0
0
p−k
r
s
s k −r−s
C'
0
0
0
0
I p−k 0
S'
0
k
S'
0
−C'
p−k k
⎤
⎥
0
0 ⎥
I k −r −s 0 ⎥
⎥
0
I m−k ⎥
⎥
⎥
0
0 ⎥
⎥
0
0 ⎥
0
0 ⎥
⎥
0
0 ⎥⎦
k −r −s m−k
0
0
⎛r
⎞
⎜
⎟
⎜s
⎟
⎜k −r − s ⎟
⎜
⎟
⎜ m − k (≥ 0) ⎟
⎜
⎟
⎜
⎟
⎜ p − k (≥ 0) ⎟
⎜r
⎟
⎜
⎟
⎜s
⎟
⎜k −r − s ⎟
⎝
⎠
)
0 ⎤⎛k
⎞
⎥⎜
I m − k ⎥ ⎜ m − k ⎟⎟
⎥⎜
⎟
⎥⎜
⎟
0 ⎥⎜ p − k ⎟
⎜
⎟
0 ⎦⎥ ⎝ k
⎠
m−k)
ここで、この行列の上下の各ブロック内での行交換または非零スカラー倍、左右の各ブロ
ック内での列交換または非零スカラー倍は、すべて原分解形中の直交行列 U1 ,
, V2 の定義を適
当に修正することにより実現できることに着目し、次の演算を行う：
⎡
⎢
⎢
Σ=⎢
⎢
⎢
⎢
⎣
(
C'
0
0
0
S'
0
0
I p −k 0
S'
0
k
p−k k
− C'
0 ⎤⎛k
⎞
⎥⎜
I m − k ⎥ ⎜ m − k ⎟⎟
⎥⎜
⎟
⎥⎜
⎟
0 ⎥⎜ p − k ⎟
⎜
⎟
0 ⎥⎦ ⎝ k
⎠
→
最後の 2 行を交換
m−k)
Copyright 再履修線形代数研究会
10
再履修線形代数―分解定理を主軸に整理整頓
⎡
⎢
⎢
→ ⎢
⎢
⎢
⎢
⎣
C'
0
S'
0
0
0
−C'
S'
0
0
I p−k 0
⎡
⎢
⎢
→ ⎢
⎢
⎢
⎢
⎣
C'
0
0
I m−k 0
⎡
⎢
⎢
→ ⎢
⎢
⎢
⎢
⎣
S'
S'
0
−C'
0
0
0
C'
0
−S'
0
I m−k 0
S'
0
C'
0
0
0
ゆえに、適当な直交行列 U1 ',
⎤
⎥
I m−k ⎥
⎥
⎥
0 ⎥
0 ⎥⎦
p)
0 ⎤
⎥
0 ⎥
⎥
⎥
0 ⎥
I p − k ⎥⎦
→2 列と 4 列を交換
→3 列に −1 を乗じる
⎤
⎥
0 ⎥
⎥
⎥
0 ⎥
I p − k ⎥⎦
0
, V2 ' をとれば
( k q)
⎡
⎢
⎢
=⎢
⎢
⎢
⎢
⎣
(
⎤
⎥
⎥
⎥
⎥
S' 0
C' 0 ⎥
0
0
0
I p − k ⎦⎥
k m−k k p−k )
C'
0
0 −S'
I m−k 0
これは Paige & Saunders[2] (4.10)式である。とくに
⎡ U1 ' 0 ⎤ ⎡Q11 Q12 ⎤ ⎡ V1 ' 0 ⎤
⎢
⎥⎢
⎥
⎥⎢
(3) ⎣⎢ 0 U 2 'T ⎦⎥ ⎣Q 21 Q 22 ⎦ ⎣ 0 V2 '⎦
T
(m
p)
CS 分解
0
⎡ U1 'T 0 ⎤ ⎡Q11 Q12 ⎤ ⎡ V1 ' 0 ⎤
⎢
⎥⎢
⎥
⎥⎢
(2) ⎣⎢ 0 U 2 'T ⎦⎥ ⎣Q 21 Q 22 ⎦ ⎣ 0 V2 '⎦
(m
レッスン 12
( k q)
⎡ C' − S '
⎢
=⎢
⎢ S' C'
⎢
0
⎣⎢ 0
(
k
k
0
0
⎛k
⎞
⎜
⎟
⎜m−k ⎟
⎜
⎟
⎜
⎟
⎜k
⎟
⎜ p−k ⎟
⎝
⎠
p ≥ m = k の場合、(2)式は
⎤⎛k
⎞
⎥⎜
⎟
⎥⎜
⎟
⎟
0 ⎥⎜k
⎥⎜
⎟
I p − k ⎦⎥ ⎝ p − k ⎠
0
p −k)
となる。これが Stewart 型 CS 分解（Stewart [4], pp. 657-659, Theorem A.1）である。
以上を振り返ると、薄型 CS 分解（前節(10)式）の上に Stewart 型分解(3)式があり、その
上に P-S 型 CS 分解の特別の場合(2)が位置し、その上に最も一般的な P-S 型 CS 分解 12.1 節(1)
Copyright 再履修線形代数研究会
11
レッスン 12
再履修線形代数―分解定理を主軸に整理整頓
CS 分解
式が位置していることがわかる（12.1 節当初でもこのことに言及している）
。
さて、直交行列をブロックに区分けし、個々のブロックの特異値を考える必要性はどんな
場合に起るのか？これ以降は CS 分解の応用を考えることにする。
12.4
正射影
本節の主題「正射影」はこれ以降の話しへの予備知識として必要である。正射影とは、簡
単にいえば、
「任意点から与えられた部分空間へ垂線を下す演算」と考えてよい。この演算は前
レッスンにおいて、最小自乗法に関連して出てきている（レッスン 11、11.8 節）
。
以下において正射影の基礎知識をまとめてのべる。まずは定義から： P = P P を満たす n
T
次行列 P を正射影 orthogonal projection という。与えられた部分空間を R ( P ) としてもつよう
正射影をその部分空間上への正射影ともいう。ここに R (
)は
の値域を表す。とくに、
P = 0, I は、それぞれ、 {0}, R n×1 上への正射影を表す。
P を正射影とすれば、以下(a)-(e)が成り立つ（証明は後述）：
(a) I − P も正射影を表す。また、 P = P （対称性）
、 P = P （ベキ等性 idempotency）、
2
T
R (I − P) = R(P) ⊥ （すなわち、 I − P は R(P) の直交補空間 R (P ) ⊥ 上への正射影）、
R(I − P) ⊥ = R(P) （すなわち、 P は R(I − P) の直交補空間 R (I − P) ⊥ 上への正射影）。
, w k } を R(P) の任意基底、 W1 ≡ [ w1
(b) 0 < k ≡ dim R ( P ) ≤ n とし、 {w1 ,
−1
w k ] とすれば
（ R (P ) = R ( W1 ) に注意）、 P = W1 ( W1 W1 ) W1 と書ける。これは、与えられた部分空間上
T
T
への正射影は一つしかないこと、すなわち、正射影 P1 , P2 に対して、P1 = P2 ↔ R ( P1 ) = R ( P2 )
が成り立つことを示す。
(c) (b)において {w1 ,
, w k } を正規直交系にとり、これを R n×1 の正規直交基底に拡張したもの
を {w1 ,
, w n } とし、 W = [ w1
, w k , w k +1 ,
w n ] ∈ R n×n （ WT W = I n ）とおけば、 P は
⎡I 0 ⎤
P = W1W1T = W ⎢ k ⎥ WT と書ける。これは P の特異値分解を表す（シュール分解でもある）。
⎣0 0 ⎦
(d) P ≠ 0 なら
P =1
(e) 任意の x, y ∈ R
n×1
に対して x − Px ≤ x − Py が成り立つ。すなわち、 Px は x から最短距
離にある R ( P ) 上の点を表し、 x − Px ⊥
R(P) も成り立つ。この意味において、 Px は x から
R(P) 上に下した垂線の足を表す。（実はこの逆も真である：問題 12.9 参照。）
証明
(a) まず、P は正射影 → P = P P → P = P → P = P （∴ P は R (P) 上での恒等変換）。
Copyright 再履修線形代数研究会
T
T
2
12
レッスン 12
再履修線形代数―分解定理を主軸に整理整頓
CS 分解
これを使うと、I − P = (I − P ) (I − P ) が出るから、I − P も正射影を表す。R (I − P ) = R ( P )
T
を示そう： b ∈ R (I − P) ↔ (*)
⊥
b = (I − P)x と書ける ↔ Pb = 0 （∵ → ：(*)の左から P を乗
じる、 ← ： b = (I − P)b ） ↔ すべての y ∈ R
n×1
に対して 0 = y Pb = y P b = ( Py ) b ↔
T
T
T
T
b ⊥ RB b ⊥ R(P) ↔ b ∈ R(P) ⊥ 。
⊥
(b) R (I − P ) = R ( P ) （(a)で証明済み）より、任意の x ∈ R
n×1
に対して、 x − Px ⊥
R(P) 、
すなわち、 (†) W1 ( x − Px) = 0 が成り立つ。また一般に、 y ⊥ R ( P ) ↔ W1 y = 0 ゆえ、
T
T
y T W1 = 0 → yT Px = 0 が成り立つ。これは方程式 (††) W1z = Px が z に関して可解であるこ
とを示す。これを (†) に代入すれば W1 ( x − W1z ) = 0 となるから、これを z について解けば、
T
z = ( W1T W1 ) −1 W1T x が出る。ここに k × k 行列 W1T W1 は確かに可逆行列を表す（実際、
rank ( W1T W1 ) = rank ( W1 ) = k ）。この z を (††) に代入すれば Px = W1 ( W1T W1 ) −1 W1T x
−1
が出る。 x は任意であったから、これは P = W1 ( W1 W1 ) W1 を示す。
T
T
(c) (b)より従う。
(d) (c)で得られた特異値分解から従う。
（別証）
x = 1 を満たす任意の x ∈ R n×1 に対して x = Px + (I − P ) x ≡ y + z と分解すれば
y T z = (Px)T (I − Px) = xT PT (I − P)x = xT ⋅ 0 ⋅ x = 0 (∵PT = P, P 2 = P) ゆえ、
1 = x = y + z 。ゆえに、 y
2
2
2
2
= Px = 1 − z ≤ 1 。これより P ≤ 1 。他方、
2
2
P = P ⋅ P ≤ P 。 P ≠ 0 ゆえ P > 0 。ゆえに 1 ≤ P 。）
2
(e)
x − Py = x − Px + Px − Py = x − Px + Px − Py ≥ x − Px
2
2
2
2
2
(∵ x − Px ⊥ Px − Py ∵ (I − P)T P = 0)
これより、Px ≠ Py なら
x − Py > x − Px となる。ゆえに Px は R(P) 内のベクトルのうち、
2
2
x から最短距離にある唯一つのベクトルを表す。■
12.5 部分空間間の距離
この節では CS 分解に応用事例として、部分空間間の距離の評価について考える。
まず、 S1 , S2 を R
n×1
の部分空間、 P1 , P2 を、それぞれ、 S1 , S2 上への正射影とすれば、
Copyright 再履修線形代数研究会
13
再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
CS 分解
dist ( S1 , S 2 ) ≡ P1 − P2
(1)
を S1 , S 2 間の距離 distance という。前節で示したように、与えられた部分空間とその上への正
射影は 1 対 1 に対応するから、この定義に曖昧性はない。とくに
dist ( S1 , S1⊥ ) = 1 （∵ 左辺＝ P1 − (I − P1 ) ＝1、前節(a)参照）。
(2)
また、 dist ( ⋅ , ⋅) は明らかに距離の公理を満たす： S1 , S 2 , S3 を R
n×1
内の部分空間とすれば、
dist ( S1 , S2 ) ≥ 0; dist ( S1 , S2 ) = 0 ↔ S1 = S2
(4) dist ( S1 , S 2 ) = dist ( S 2 , S1 )
(5) dist ( S1 , S 2 ) + dist ( S 2 , S3 ) ≥ dist ( S1 , S3 ) （3 角不等式）
(3)
以下、 dist ( S1 , S 2 ) を評価する作業に入るが、 S1 , S 2 の一方が {0} または R
n×1
の場合は簡単
である（前節(a)、(d)参照）
：
(5)
dist ( S1 ,{0}) = P1 − 0 = 1 （ S1 ≠ {0} ）、 dist ( S1 , R n×1 ) = P1 − I = 1 （ S1 ≠ R n×1 ）
ゆえに、0 < dim S1
≡ m < n, 0 < dim S 2 ≡ k < n の場合のみについて考えれば十分である。
そこで、 {w1 , , w m } を S1 の正規直交基底、これを全空間の正規直交基底に拡張したものを
{w1 , , w m , , w n } 、 {z1 , , z k } を S2 の正規直交基底、これを全空間の正規直交基底に拡張
したものを {z1 , , z k , , z n } とし、
W1 = [ w1 ,
Z1 = [ z1 ,
, w m ] , W2 = [ w m +1 ,
, z k ] , Z 2 = [ z k +1 ,
, w n ] , W = [ w1 ,
, z n ] , Z = [ z1 ,
, w n ] = [ W1 W2 ]
, z n ] = [ Z1 Z 2 ]
とすれば、 P1 , P2 は前節(c)により
(6)
P1 = W1W1T 、 P2 = Z1Z1T
によって与えられる。すると、 dist ( S1 , S 2 ) について以下の評価が成り立つ（証明は後述）
：
(7)
dist ( S1 , S 2 ) = W1W1T − Z1Z1T = max{ W1T Z 2 , Z1T W2 }
(8)
dist ( S1 , S 2 ⊥ ) = W1W1T − Z 2 Z 2T = max{ W1T Z1 , W2T Z 2 }
(9)
dim S1 = dim S 2 なら、 dist ( S1 , S 2 ) = W1T Z 2 = Z1T W2 = 1 − σ min 2 ( W1T Z1 ) ≤ 1
dim S1 ≠ dim S 2 なら、 dist ( S1 , S 2 ) = 1
(11) 0 ≤ dist ( S1 , S 2 ) ≤ 1
(10)
Copyright 再履修線形代数研究会
14
再履修線形代数―分解定理を主軸に整理整頓
証明
T
まず、 W1
レッスン 12
W1 = I m , W1T W2 = 0, W2T W2 = I n− k ,
CS 分解
ゆえ、
⎡ W1T ⎤
⎡ 0
W1T Z 2 ⎤
T
T
W ( W1W − Z1Z )Z = ⎢ T ⎥ ( W1W1 − Z1Z1 ) [ Z1 Z 2 ] = ⎢
⎥
T
⎣⎢ W2 ⎦⎥
⎣⎢ − W2 Z1 0 ⎥⎦
T
T
1
T
1
⎡W T ⎤
⎡W T Z
⎤
0
WT ( W1W1T − Z 2 Z 2T )Z = ⎢ 1 T ⎥ ( W1W1T − Z 2 Z 2T ) [ Z1 Z 2 ] = ⎢ 1 1
⎥
− W2T Z 2 ⎥⎦
⎢⎣ W2 ⎥⎦
⎢⎣ 0
WT W = ZT Z = I n に注意してノルムをとれば、前レッスン 11.6 節(X)(XI)により(7)(8)が出る。
(9)(10)の証明には W
T
Z （これも直交行列）を計算し、P-S 型 CS 分解を使う！実際、
⎡ W1T ⎤
⎡ W1T Z1 W1T Z 2 ⎤
W Z = ⎢ T ⎥ [ Z1 Z 2 ] = ⎢ T
⎥
T
⎣⎢ W2 ⎦⎥
⎣⎢ W2 Z1 W2 Z 2 ⎦⎥
T
(
k
⎛m
⎞
⎜
⎟
⎝ n − m ≡ p > 0⎠
n−k ≡ q >0
)
に P-S 型 CS 分解を適用すると
(†)
⎡ U1T 0 ⎤ ⎡ W1T Z1 W1T Z 2 ⎤ ⎡ V1 0 ⎤ ⎛ m ⎞
⎢
⎥⎢
⎥ ⎜ ⎟
T⎥⎢
T
T
⎢⎣0 U 2 ⎥⎦ ⎢⎣ W2 Z1 W2 Z 2 ⎥⎦ ⎣ 0 V2 ⎦ ⎝ p ⎠
( m p)
( k q)
⎡I
⎢
⎢
⎢
⎢
=⎢
⎢0
⎢ S
⎢
⎢
⎣
(r
⎤ ⎛r
⎥ ⎜
C
S
⎥ ⎜s
0C
I ⎥ ⎜m−r − s
⎥ ⎜
⎥ ⎜
⎥ ⎜ p−k +r
I
⎥ ⎜
−C
S
⎥ ⎜s
T⎥ ⎜ − −
I
0C ⎦ ⎝ k r s
s k − r − s p − k + r s m − r − s)
0S T
T
が得られる（記号については 12.1 節参照）
。ここに、 W1
⎞
⎟
⎟
⎟
⎟
⎟ ⎡ Σ11 Σ12 ⎤
⎟ ≡ ⎢Σ Σ ⎥
⎟ ⎣ 21 22 ⎦
⎟
⎟
⎠
Z1 、 W2T Z1 、 W1T Z 2 、 W2T Z 2 の
特異値は、それぞれ、 Σ11 、 Σ 21 、 Σ12 、 Σ 22 の特異値と一致する
まず、 m = dim S1
= dim S 2 = k なら（ t ≡ m − r − s = k − r − s ）、
Copyright 再履修線形代数研究会
15
再履修線形代数―分解定理を主軸に整理整頓
⎡I
⎤
⎢
⎥
C
Σ11 = ⎢
⎥
⎢⎣
0C ⎥⎦
(r s t)
レッスン 12
⎡ 0S
Σ 21 = ⎢⎢
S
⎢⎣
(r s
⎛r⎞
⎜ ⎟
⎜s⎟
⎜t ⎟
⎝ ⎠
CS 分解
⎤ ⎛ p−k +r⎞
⎟
⎥ ⎜s
⎟
⎥⎜
⎟
I ⎥⎦ ⎜⎝ t
⎠
t)
⎡ 0S T
⎢
S
Σ12 = ⎢
⎢
⎣
(r s
⎤ ⎛r⎞
⎥⎜ ⎟
⎥ ⎜s⎟
I ⎥⎦ ⎜⎝ t ⎟⎠
t)
となる。視察により
W2T Z1 = σ max (Σ 21 ) = σ max (Σ12 ) = W1T Z 2 = 1 − σ min 2 ( W1T Z1 ) （∵ C2 + S 2 = I ）
が得られる。 m = dim S1 ≠ dim S 2 = k なら、分解形 (†) における Σ 21 、 Σ12 の少なくとも一方
の右下隅に必ず“ 1 ”が存在する（ I k − r − s 、 I m − r − s の一方は空ブロックではない）
。ゆえに
1 = max{ W2T Z1 , W1T Z 2 } = dist ( S1 , S2 ) 。■
w1 = z 1 = 1, w1T z1 = cos θ ≥ 0 （ 0 ≤ θ ≤ π / 2 、 w1 , z1 ∈ R 3×1 ）とし、
例1
S1 = span{w1}, S2 = span{z1} とすれば
dist ( S1 , S2 ) = 1 − σ min 2 (w1T z1 ) = 1 − cos 2 θ = sin θ
ゆえに、 S1 , S 2 間の距離とは、それぞれの表す直線のなす角を θ とすれば、 sin θ に等しい。■
12.6
AB −1 型行列の特異値分解
−1
この節では、CS 分解の巧妙な応用例として、 AB 型行列の特異値分解を考える。ここに
A : m × n, B : n × n とし、 B −1 の存在を仮定する。 B −1 の計算を避けつつ行う点がポイントであ
る。これは一般化特異値分解 generalized singular value decomposition, GSVD
（Paige-Saunders[2]）
、または商特異値分解 quotient singular value decomposition , QSVD
（Paige and Wei [3]）の特別の場合を表す。このような分解は最小自乗問題
「 f ( x) = Ax − b
2
+ λ 2 Bx − d ＝最小」の最適解が λ の変化にどう反応するか、の解析に
2
必要となることが報告されているが、ここでは立ち入らない。
⎡A⎤
⎥ を特異値分解し（これが工夫の第一）、それを
⎣B ⎦
⎡R ⎤
T ⎡A⎤
(1) P ⎢ ⎥ Q = ⎢ ⎥
⎣B ⎦
⎣ 0⎦
とする。ここに、P : m + n 次直交行列、Q : n 次直交行列、R :n 次可逆対角行列（対角成分 > 0 ）
まず、 C ≡ ⎢
⎡A⎤
⎥ ) = rank (R ) ）。
⎣B ⎦
である（∵ n = rank (B) = rank ( ⎢
Copyright 再履修線形代数研究会
16
再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
CS 分解
⎡ P11 P12 ⎤ ⎛ m ⎞
P=⎢
⎥⎜ ⎟
つぎに、(1)中の P を
⎣ P21 P22 ⎦ ⎝ n ⎠ と区分けし、第 1 列に P- S 型 CS 分解を施すと
(n m)
（これが工夫の第二）
、
⎡I
⎢
⎢
⎢
⎡ UT P11W ⎤ ⎢
⎡ UT 0 ⎤ ⎡ P11 ⎤
⎥=⎢
⎢
⎥⎢ ⎥W = ⎢ T
(2) ⎣ 0 V T ⎦ ⎣ P21 ⎦
⎢⎣ U P21W ⎥⎦ ⎢
0
⎢
⎢
⎢
⎣
( n)
(m n) (n) (n)
(r
⎤ ⎛r
⎥ ⎜s
C
⎥ ⎜
0 ⎥ ⎜m−r − s
⎥ ⎜
⎥ ⎜
⎥ ⎜r
⎥ ⎜
S
⎥ ⎜s
I ⎥⎦ ⎝⎜ n − r − s
s n − r − s)
⎞
⎟
⎟
⎟ ⎡Σ A ⎤ ⎛ m ⎞
⎟ ⎢ ⎥⎜ ⎟
⎟ ≡ ⎢ ⎥⎜ ⎟
⎟ ⎢Σ ⎥ ⎜ n ⎟
⎟ ⎣ B ⎦⎝ ⎠
⎟
⎟
⎠
(n)
が得られる（記号については 12.1 節参照）
。ここに、 Σ A , Σ B は（ A, B ではなく） P11 , P21 の特
異値分解標準形を表していることに注意。
⎡A⎤
⎡R ⎤
Q = P ⎢ ⎥ と書き直し、これと(2)から P11 , P21 を消去すると、次式が得られる：
⎥
⎣B ⎦
⎣0 ⎦
(1)を ⎢
(3)
UT AX = Σ A ( m )
V T BX = Σ B ( n )
(m n n) ( n )
( n n n) ( n )
−1
（ X = QR W ）
後者の左辺は可逆行列を表すから、 Σ B も可逆行列を表す。結局この 2 式より X も消去できて
(4)
UT ( AB −1 )V = Σ A Σ B −1
−1
が得られる。これは AB の特異値分解に他ならない！さらに、 Σ B が可逆行列であることを考
慮すれば、(2)は実際には
⎡C
⎤ ⎛s
⎞
⎜
⎟ Σ
⎢
⎥
0 ⎥ ⎜m− s⎟ ⎡ A⎤⎛m ⎞
⎡ UT P11W ⎤ ⎢
⎡ UT 0 ⎤ ⎡ P11 ⎤
⎟ = ⎢ ⎥⎜ ⎟
⎥ ⎜
W=⎢ T
⎥=⎢
⎢
⎥
T⎥⎢
(5) ⎣ 0 V ⎦ ⎣ P21 ⎦
⎟ ⎢ ⎥ ⎜⎜ ⎟⎟
⎥ ⎜
⎣⎢ U P21W ⎦⎥ ⎢S
s
⎟ ⎢⎣Σ B ⎥⎦ ⎝ n ⎠
⎢
⎥ ⎜
⎢⎣
I ⎥⎦ ⎜⎝ n − s ⎟⎠
( n)
(m n) (n) (n)
( s n − s)
( n)
の形をとることがわかる。これより、
Copyright 再履修線形代数研究会
17
レッスン 12
再履修線形代数―分解定理を主軸に整理整頓
(6)
CS 分解
⎡CS −1 ⎤ ⎛ s
⎞
UT ( AB −1 )V = Σ A Σ B −1 = ⎢
⎥ ⎜
⎟
0⎦ ⎝ n − s ⎠
⎣
( s n − s)
ここで(5)(6)を見ると、 U, V はそれぞれ P11 , P21 の特異値分解に必要な直交行列であるが、
これが AB
−1
の特異値分解に役立っている！これは一見不思議だが、(2)式から出る関係
AQR −1 = P11 、BQR −1 = P21 を見ると、P11 , P21 は共通の座標変換によって「化けた A, B の姿」
−1
と見なせる。同様に(3)式 U AX = Σ A 、 V BX = Σ B （ X = QR W ）を見ると、これは特異
T
T
値分解ではないが、 Σ A , Σ B もそれぞれ「 A, B の化けた姿」と見なせる。この間の事情を Paige
and Saunders[2]は“We can ascribe n singular value pairs (α i , β i ), i = 1,
, n to A and
B ,…“ といっている（「 Σ A , Σ B の対角成分の対 α i , βi は A, B に帰することができる、・・」
⎡1
⎡A⎤ ⎢
例 1 ⎢ ⎥=
⎢
⎣B ⎦ ⎢
⎣1
⎤
⎥ の特異値分解： PT
⎥
⎥⎦
⎡A⎤
⎢B ⎥ Q ≡
⎣ ⎦
⎡ 2 ⎤ ⎡R ⎤
⎡ a a ⎤ ⎡1⎤
⎢ −a a ⎥ ⎢1⎥ [1] = ⎢ ⎥ ≡ ⎢ 0 ⎥ （ a = 1/ 2 ）
⎣
⎦⎣ ⎦
⎣ 0⎦ ⎣ ⎦
⎡ a a ⎤ ⎡ P11 P12 ⎤
−1
だから、 Σ A = Σ B = [ a ]:1× 1 、 Σ A Σ B = [1] となる。これは
≡⎢
⎥
⎥
⎣ − a a ⎦ ⎣ P21 P22 ⎦
より、 P = ⎢
確かに AB
−1
= [1] の特異値分解標準形である。■
最後にひとこと：Paige-Saunders 型 CS 分解最大の特徴は、全く任意の区分けを許してい
る点と特異値を 0、1、その他、に陽に区別している点である。このため、特定ブロックの標準
形がわかれば、他ブロックの標準形も簡単に構築できるし、応用上も使いやすい。部分空間間
−1
−1
の距離の評価、 B を計算することなく AB 型行列の特異値分解を実現する算法、への P-S
型 CS 分解の応用は意外性があっておもしろい。
腕試し問題
問題 12.1（Paige-Saunders 型 CS 分解）
(1) ある 9 次直交行列 Q を
Copyright 再履修線形代数研究会
18
レッスン 12
再履修線形代数―分解定理を主軸に整理整頓
⎡m × k
⎡Q11 Q12 ⎤ ⎢
Q=⎢
⎥=⎢
⎣Q 21 Q 22 ⎦ ⎢ p × k
⎣
m × q ⎤ ⎡3 × 4
⎥ ⎢
⎥=⎢
p × q ⎥⎦ ⎢⎣6 × 4
CS 分解
3× 5 ⎤
⎥ （m+ p = k +q = 9）
⎥
6 × 5 ⎥⎦
に分割したところ、 Q11 の特異値は {1, c2 , 0}(0 < c2 < 1) によって与えられるという。
Paige-Saunders 型 CS 分解の標準形 Σ を求めよ。
⎡1 0 0 ⎤
⎥（ 0 < c2 < 1 ）によって与え
⎣0 c2 0 ⎦
(2) ある 5 次直交行列の P-G 標準形左上ブロックは Σ11 = ⎢
られるという。標準形 Σ を求めよ。
(3)
[ ]
ある 3 次直交行列の P-G 標準形右上ブロックは Σ12 = 0 :1× 1 であるという。Σ を求めよ。
[ ]
[ ]
（略解：(1) r = s = 1, C = c2 、 S = s2 ( s2 = 1 − c2 ) だから、標準形は
⎡I
⎢
⎢0
⎢0
⎢
⎢
⎢0
⎢ S
⎢0
⎢
⎣0
(1
0
0S T 0
C 0
0 −S
0
0C
0
0
0
0
I
0
S
0
0
C
0
I
0
0
0 ⎤ ⎛1
⎥
0 ⎥ ⎜⎜ 1
I ⎥ ⎜1
⎥⎜
⎥⎜
0 ⎥⎜3
⎥⎜
0 ⎥ ⎜1
⎥⎜
0C T ⎦ ⎝ 2
1 2
3
1
1
0
)
⎞
⎡ I1
⎟
⎢0
⎟
⎢
⎟
⎢
⎟
⎢
⎟
(2) ⎢ 0
⎟
⎢0
⎟
⎢
⎟
⎢⎣ 0
⎟
⎠
(1
2
0
0
0
C
0
0
0
0
I1
S 0
0 I1
0
0
1 1
1
0 ⎤ ⎛1
S ⎥⎥ ⎜⎜1
⎥⎜
⎥⎜
0 ⎥ ⎜1
− C⎥ ⎜1
⎥⎜
0 ⎥⎦ ⎜⎝1
1)
⎞
⎟
⎡1 0
⎟
⎢
⎟
⎢
⎟
⎢0 0
(3)
⎟
⎢
⎟
⎣0 1
⎟⎟
(1 1
⎠
0 ⎤ ⎛1
⎥⎜
⎥⎜
1 ⎥ ⎜1
⎥⎜
0 ⎦ ⎝1
1)
⎞
⎟
⎟
⎟ ■）
⎟
⎠
⎡ x x x⎤
⎡ 4 0 0⎤
⎢ x x x⎥
T
⎥ に対して Y Y = ⎢ 0 0 0 ⎥ が
問題 12.2 与えられた 4 x 3 実行列 Y = [ y1 y 2 y 3 ] = ⎢
⎢
⎥
⎢ x x x⎥
⎢
⎥⎦
0
0
9
⎢
⎥
⎣
⎣ x x x⎦
⎡ −2 0 0 ⎤
⎢ 0 0 0⎥
T
⎢
⎥ となるような 4 次直交行列 U を構築せよ。
成り立つという。 U Y =
⎢ 0 0 3⎥
⎢
⎥
⎣ 0 0 0⎦
y3
⎡ y
⎤
（答： U = ⎢ − 1 u 2
u 4 ⎥ 、ここに u 2 , u 4 は U の列が正規直交系をなすように選ぶ。■）
3
⎣ 2
⎦
Copyright 再履修線形代数研究会
19
再履修線形代数―分解定理を主軸に整理整頓
[
問題 12.3 与えられた 3 × 4 実行列 Y = y1
レッスン 12
CS 分解
⎡ x x x x⎤
y 4 ] = ⎢⎢ x x x x ⎥⎥ に対して
⎢⎣ x x x x ⎥⎦
0⎤
⎡0
⎡0 0 0 0 ⎤
⎢ 4
⎥
⎢
⎥
T
T
⎢
⎥
という。 U Y = 0 2 0 0 を満たす 3 次直交行列 U を構築せよ。
Y Y=
⎢
⎥
⎢
0 ⎥
⎢⎣ 0 0 0 − 3⎥⎦
⎢
⎥
9⎦
⎣0
y2
y ⎤
⎡
T
T
（答： Y の形は Y = [ 0 y 2 0 y 4 ] 、 y 2 y 2 = 4, y 4 y 4 = 9 ゆえ、 U = ⎢u1
− 4⎥と
2
3⎦
⎣
すればよい。ここに、 u1 は
{u1 ,
y2
y
, − 4 } が正規直交系をなすように選ぶ。■）
2
3
⎡ x1 ⎤ ⎡ x x x x ⎤
⎡ 4 0 0⎤
⎢
⎥
⎢
⎥
⎢
⎥
T
問題 12.4 与えられた 3 x 4 実行列 X = x 2 = x x x x に対して XX = 0 0 0 が成立
⎢ ⎥ ⎢
⎥
⎢
⎥
⎢⎣ x3 ⎥⎦ ⎢⎣ x x x x ⎥⎦
⎢⎣ 0 0 9 ⎥⎦
⎡ −2 0 0 0 0 ⎤
⎢
⎥
するという。 XV = 0 0 0 0 0 となるような 4 次直交行列 V を構築せよ。
⎢
⎥
⎢⎣ 0 0 3 0 0 ⎥⎦
（答：
V = ⎡⎣ −x1T / 2 v 2 x3T / 3 v 4 ⎤⎦ 、ここに v 2 , v 4 は VVT = I となるように選ぶ。■）
⎡3 × 2 ⎤
⎡Q1 ⎤ ⎢
⎥ の列は正規直交系をなし、適当な 2 次
問題 12.6 与えられた 7 x 2 実行列 Q = ⎢
⎥=⎢
⎥
Q
⎣ 2 ⎦ ⎢4 × 2⎥
⎣
⎦
T
直交行列 V1 に対してシュール分解 V1
(1)
⎡3 / 4 0 ⎤
Q1T Q1V1 = ⎢
⎥ が成立するという。
⎣ 0 1 / 4⎦
V1T Q 2T Q 2 V1 を計算せよ。
⎡ 3/2 0 ⎤
⎢
⎥ ⎡C ⎤
T
1/ 2 ⎥ ≡ ⎢ ⎥ となるような 3 次直交行列 U1 を構築せよ。
(2) U1 Q1V1 = = ⎢ 0
⎢ 0
⎥ ⎣0 ⎦
0
⎣
⎦
Copyright 再履修線形代数研究会
20
再履修線形代数―分解定理を主軸に整理整頓
レッスン 12
CS 分解
0 ⎤
⎡ −1/ 2
⎢
⎥
0 − 3 / 2 ⎥ ⎡S ⎤
T
⎢
≡ ⎢ ⎥ となるような 4 次直交行列 U 2 を構築せよ。
(3) U 2 Q 2 V1 =
⎢ 0
0 ⎥ ⎣0 ⎦
⎢
⎥
0 ⎦⎥
⎣⎢ 0
(4)
⎡U
⎢
⎢⎣ 0
T
1
⎡C ⎤
⎢0 ⎥
0 ⎤ ⎡Q1 ⎤
⎢
⎥ ⎢ ⎥ V1 = ⎥ を検算せよ。
⎢S ⎥
U 2T ⎥⎦ ⎣Q 2 ⎦
⎢ ⎥
⎣0 ⎦
T
（略解：(1) 列の正規直交性 Q1
Q1 + Q 2T Q 2 = I と V1 の直交性より
⎡3 / 4 0 ⎤ ⎡1/ 4 0 ⎤
V1T Q 2T Q 2 V1 = I − V1T Q1T Q1V1 = I − ⎢
⎥=⎢
⎥
⎣ 0 1/ 4 ⎦ ⎣ 0 3 / 4 ⎦
(2)
⎡3 / 4 0 ⎤
Q1V1 ≡ Y ≡ [ y1 y 2 ] とおけば、 YT Y = ⎢
⎥ だから、
⎣ 0 1/ 4 ⎦
U1 = ⎣⎡ y1 /( 3 / 2) y 2 /(1/ 2) u3 ⎤⎦ をとれば（ u3 は U1 の列が正規直交系をなすように選ぶ）、
⎡ 3/4 0 ⎤
⎢
⎥
1/ 2 ⎥ となる。
U1T Q1V1 = U1T Y = ⎢ 0
⎢ 0
0 ⎥⎦
⎣
(3)
⎡1/ 4 0 ⎤
Q 2 V1 ≡ Y ≡ [ y1 y 2 ] とし、(2)と同様の手続きを踏めば、 YT Y = ⎢
⎥ 。ゆえに、
⎣ 0 3 / 4⎦
U 2 = ⎡⎣ −y1 /(1/ 2) − y 2 /( 3 / 2) u3 ' u 4 '⎤⎦ をとれば（ u3 ', u 4 ' は U 2 の列が正規直交系をな
⎡ −1/ 2
⎢
0
T
すように選ぶ）、 U 2Q 2 V1 = U 2 Y = ⎢
⎢ 0
⎢
⎣⎢ 0
Copyright 再履修線形代数研究会
⎤
⎥
− 3 / 2⎥
(4) 略 ■）
0 ⎥
⎥
0 ⎥⎦
0
21
再履修線形代数―分解定理を主軸に整理整頓
⎡1
⎢0
⎢
⎢
Q
Q
⎡ 11 12 ⎤
問題 12.7 Q ≡ ⎢
⎥≡⎢
⎣Q 21 Q 22 ⎦ ⎢0
⎢0
⎢
⎣0
レッスン 12
CS 分解
0 0 0⎤
0 − 1 0 ⎥⎥
⎡C ' − S '
⎥ ⎢
⎥ ≡ S' C
0 1 0 0⎥ ⎢
⎢0 0
1 0 0 0⎥ ⎣
⎥
0 0 0 1⎦
⎡1
はすでに Stewart 型 CS 分解の標準形をなす。ここに、C ' = ⎢
⎣0
0
0
0⎤
0 ⎥⎥
I1 ⎥⎦
0⎤
⎡0 0 ⎤
, S' = ⎢
⎥
⎥ としている。
0⎦
⎣0 1 ⎦
この行列の Paige-Saunders 型標準形を求めよ。
Q11 の特異値は {1, 0} であるから r = 1, s = 0 となる。ゆえに、 C は空ブロックを表
（略解：
す。これにより Paige-Saunders 型標準形は次のように確定する：
⎡1
⎢0
⎢
⎢
⎢
⎢0
⎢0
⎢
⎣0
0
0
0
0
1
0 0 0⎤
⎡ I1
0 0 1⎥⎥ ⎢
0
⎥ ⎢
⎥=⎢
1 0 0⎥ ⎢
⎢ 0S
0 1 0⎥ ⎢
⎥ 0
0 0 0⎦ ⎣
(1
I1
0S T 0 ⎤ ⎛ 1
⎥
0 I1 ⎥ ⎜⎜ 1
⎥⎜
⎥⎜
I2 0 ⎥ ⎜ 2
⎥⎜
0 0 CT ⎦ ⎝ 1
1
2
0
0C
0
1
⎞
⎟
⎟
⎟
⎟ ■）
⎟
⎟
⎠
)
問題 12.8（P-Ｇ型 CS 分解証明への補足）次の n 次実行列（ n = m +
p = k + q ）は直交行列
を表すという：
⎡I
⎢
C
⎢
⎢
⎢
⎢
⎢W
⎢ 11
⎢ W21 W22
⎢W W
32
⎣ 31
(
r
Y11
Y12
Y22
0C
W33
X11
X12
X 21
X 22
X31
X32
Y13 ⎤
Y23 ⎥⎥
Y33 ⎥
⎥
⎥
X13 ⎥
⎥
X 23 ⎥
X33 ⎥⎦
⎛r
⎜
⎜s
⎜m−r − s
⎜
⎜
⎜ p−k +r
⎜
⎜s
⎜k −r − s
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟（空欄は 0 ブロックを表す）こ
⎟
⎟
⎟
⎠
s k − r − s p − k + r s m − r − s)
ここに W22 , W33 は対角成分が負でないような下三角行列、 Y22 , Y33 は対角成分が負でない上三
⎡cr +1
⎢
角行列、 C は C =
⎢
⎢⎣0
0 ⎤
⎥ (1 > c ≥
r +1
⎥
cr + s ⎥⎦
≥ cr + s > 0) 型の行列、 0C は 0 行列を表す。
すると、上の行列は実は次の形でなければならないことを示せ：
Copyright 再履修線形代数研究会
22
レッスン 12
再履修線形代数―分解定理を主軸に整理整頓
⎡I
⎢
⎢
⎢
⎢
⎢
⎢0
⎢ S
⎢
⎢
⎣
(r
⎤
⎥
C
S
⎥
0C
I⎥
⎥
⎥
⎥
X11
⎥
−C
S
⎥
T⎥
I
0C ⎦
s k − r − s p − k + r s m − r − s)
0S T
⎡ sr +1
⎢
ただし、 S =
⎢
⎢⎣0
0 ⎤
⎥ (0 < s ≤
r +1
⎥
sr + s ⎥⎦
CS 分解
⎛r
⎜
⎜s
⎜m−r − s
⎜
⎜
⎜ p−k +r
⎜
⎜s
⎜k −r − s
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
≤ sr + s < 1, si = 1 − ci 2 ) 、 X11 は p − k + r 次直交行
列を表す。
（略解：与えられた行列の直交性と W22 , W33 , Y22 , Y33 の形に関する仮定から出る。与えられ
た行列は標準形の一歩手前の形を表す。 X11 は直交行列ゆえ、これを左または右へ括り出せば
標準形が得られることは 12.2 節の証明で示した。この問題は左上ブロックに特異値分解
⎡I 0 0 ⎤
U Q11V1 = ⎢⎢0 C 0 ⎥⎥ を施し、Q 21V1（ V1 は今や既知！）に QR 分解を施して U 2T (Q 21V1 ) =
⎢⎣0 0 0 ⎥⎦
T
1
下三角行列とし、 U1 Q12 （ U1 も今や既知！）に QR 分解を施して ( U1 Q 21 )V2 = 上三角行列
T
T
T
とすれば、これらは実は特異値分解を表すのみならず、 U 2 Q 22 V2 も特異値分解直前の形をし
ていることを示す。QR 分解はシュール分解に関するレッスンの中で説明した。■）
問題 12,9 （正射影）12.4 節(e)の逆：与えられた n × n 行列 P 、任意の x, y ∈ R
n×1
に対して
x − Px ≤ x − Py が成り立つという。 PT (I − P) = 0 を示せ。すなわち、 P は正射影を表す。
（略証
PT (I − P) ≠ 0 と仮定すれば矛盾が起ることを示せばよい。実際、
0 ≠ PT (I − P)x 0 ≡ u 0 （ x 0 ∈ R n×1 ）とすれば、若干の計算後
x0 − P(x0 + ε u 0 ) = x0 − Px 0 − ε (2 u 0 − ε Pu 0 ) が得られる。 u 0 > 0 だから、十分
2
2
小さい ε > 0 に対して、右辺 < x 0 − Px 0
Copyright 再履修線形代数研究会
2
2
2
となる。これは与えられた条件に矛盾する。■）
23

Download Report