固有値分解 - yuuk1's Digital Garden

# 固有値分解 ## 定義正方行列 $A\in\mathbb{R}^{n\times n}$ が $n$ 個の線形独立な固有ベクトル $p_1,\dots,p_n$(対応する固有値 $\lambda_1,\dots,\lambda_n$)を持つとき、$A$ は対角化可能(diagonalizable)であるといい、$P:=[p_1,\dots,p_n]$、$D:=\mathrm{diag}(\lambda_1,\dots,\lambda_n)$ とおくと $A = PDP^{-1}$ という固有値分解(eigendecomposition)が成り立つ。これは「$A$ と対角行列 $D$ が相似である」ことと同値であり、$P$ が可逆であること(= $P$ がフルランクであること、Theorem 4.3)、すなわち固有ベクトルが $\mathbb{R}^n$ の基底を成すことを要求する。$n$ 個より少ない線形独立な固有ベクトルしか持たない行列を欠損行列(defective matrix)と呼び、これは対角化できない(Definition 4.13, Theorem 4.20)。幾何的には、固有値分解は「$P^{-1}$ による標準基底から固有ベクトル基底への基底変換」「$D$ による固有ベクトル方向ごとの独立なスケーリング」「$P$ による基底変換を元に戻す操作」という3段階の合成写像として理解できる。対称行列 $S$ は常に対角化可能であり(スペクトル定理、Theorem 4.15・4.21)、固有ベクトルは正規直交基底(ONB)を成すため $P$ は直交行列になり、$S=PDP^\top$ と書ける。固有値分解が存在すれば、行列式は固有値の積 $\det(A)=\prod_i\lambda_i$、トレースは固有値の和 $\mathrm{tr}(A)=\sum_i\lambda_i$ に一致し(Theorem 4.16・4.17)、行列のべき乗も $A^k=PD^kP^{-1}$ と対角成分ごとの計算に帰着できるため効率的に求まる。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 4 Matrix Decompositions]] §4.2, §4.4) ## 横断的知見 - 1ソース目のため、他のソースとの突き合わせによる知見は今後の蓄積に委ねる。本概念は同一章内の[[特異値分解]]と対比されることで輪郭が明確になる: 固有値分解は正方行列かつ固有ベクトルが基底を成す場合にのみ存在し、基底変換は定義域=値域という単一のベクトル空間内で完結する($P^{-1}$ による変換を $P$ が打ち消す)。これに対しSVDは正方性も基底の存在も要求せず任意の行列に対して常に存在し、定義域と値域という異なる2つの空間でそれぞれ独立な基底変換($V^\top$ と $U$)を行う。「常に存在する分解」対「条件付きで存在する分解」という非対称性は、単一ソース内(第4.4節と第4.5.3節)の対比から得られた観察であり、章をまたぐ突き合わせが増えた際にさらに厚みを持たせたい。 - [[線形写像と変換行列]](第2章)が導入した「基底を変えると変換行列は $S^{-1}AS$ の形で変わる(相似)」という一般論に対し、固有値分解は「固有ベクトルという特別な基底を選べば変換行列を対角行列まで単純化できる」という、相似変換の中で最も単純な代表元を与える具体例に当たる。(Source: [[線形写像と変換行列]], [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 4 Matrix Decompositions]]) - **第10章(主成分分析)は本概念を、分散最大化・射影誤差最小化という2つの独立した最適化問題の解として使う**: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 10 Dimensionality Reduction with Principal Component Analysis]] §10.2.1は、単位ノルム制約下でデータ共分散行列$S$の二次形式$b^\top Sb$を最大化する制約付き最適化問題(ラグランジュ乗数法)の停留条件が、本ページの固有値方程式$Sb=\lambda b$そのものになることを示す。すなわち本概念(固有値分解)は第4章では「行列を単純化する分解」として導入されたが、第10章では「制約付き二次形式最大化の解」という最適化理論上の意味づけを獲得する。これは固有値分解が単なる行列の分解手法ではなく、対称行列の二次形式に関する最適化問題全般に現れる普遍的な構造であることを示す横断的な観察である。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 4 Matrix Decompositions]] §4.4, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 10 Dimensionality Reduction with Principal Component Analysis]] §10.2.1) - **固有値分解とSVDのどちらを計算の主軸に据えるかへの回答**: 前回の未解決の問いに対し、第10章§10.4.1は「どちらでも同じ主成分が得られる」ことを明示する。データ共分散行列$S=\frac1NXX^\top$を直接固有値分解(本概念)しても、データ行列$X$自体をSVD([[特異値分解]])してもよく、両者は$\lambda_d=\sigma_d^2/N$という関係で結びつく。実務上SVDが好まれる場面があるのは、$S$を明示的に計算せずに済む(数値的な平方誤差の蓄積を避けられる)ためだが、この数値安定性の詳細な比較は本書では踏み込まれていない。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 10 Dimensionality Reduction with Principal Component Analysis]] §10.4.1) - **[[@2022__Gihyo__ディープラーニングを支える技術 - Appendix A ［厳選基礎］機械学習＆ディープラーニングのための数学]] は、本概念を一般の対角化可能行列からではなく最初から対称行列に限定して導入する**: 同 Appendix A §A.1 は「任意の対称行列 $A$ は直交行列 $U$ を用いて $A=USU^\top$ と分解できる」という結果だけを提示し、MML第4章が扱う一般の(非対称)行列の対角化可能性・欠損行列(defective matrix)といった条件分岐には立ち入らない。これはMMLのスペクトル定理(対称行列は常に対角化可能で$P$が直交行列になる、Theorem 4.15)の主張内容と一致するが、証明も一般の対角化可能性の議論も省き「機械学習・ディープラーニングで実際に使う形」だけを抜き出した記述になっている。同じ数学的事実でも、読者(数学を体系的に学ぶ読者対 DL実装者)によって選び取る範囲が変わることを示す一例である。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 4 Matrix Decompositions]] §4.2, §4.4, [[@2022__Gihyo__ディープラーニングを支える技術 - Appendix A ［厳選基礎］機械学習＆ディープラーニングのための数学]] §A.1) ## 未解決の問い - 第6章(確率分布)で共分散行列の固有値分解がどのように使われるか(主成分分析の分散最大化方向との関係を含む)は、本チャプターの範囲外であり今後の ingest で確認する必要がある。 - 機械学習実務で固有値分解が明示的に使われる場面(スペクトラルクラスタリング、グラフラプラシアンなど)との対応関係は、既存concept([[スペクトラルクラスタリング]]等)との突き合わせが必要である。 - SVDと固有値分解の数値安定性の違い(第10章§10.4.1は理論的等価性のみ示し、浮動小数点演算での誤差蓄積の比較には踏み込まない)は、本書の範囲では検証されていない。 - [[@2022__Gihyo__ディープラーニングを支える技術 - Appendix A ［厳選基礎］機械学習＆ディープラーニングのための数学]] は対称行列に限定した固有値分解のみを紹介し、本編(第1〜5章)でこれがどの具体的な文脈(共分散行列・注意機構など)で使われるかは Appendix 単体では言及されない。本編の該当箇所との突き合わせが必要である。 ## 関連 - source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 4 Matrix Decompositions]] / [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 10 Dimensionality Reduction with Principal Component Analysis]](分散最大化問題の解としての固有値分解) / [[@2022__Gihyo__ディープラーニングを支える技術 - Appendix A ［厳選基礎］機械学習＆ディープラーニングのための数学]] - concept: [[特異値分解]] / [[線形写像と変換行列]] / [[主成分分析]] - entity: [[Mathematics for Machine Learning]] / [[wiki/entities/ディープラーニングを支える技術|ディープラーニングを支える技術]] ## 出典 - Deisenroth, Faisal, Ong, *Mathematics for Machine Learning*, Cambridge University Press, 2020, §4.2 (Eigenvalues and Eigenvectors), §4.4 (Eigendecomposition and Diagonalization), §10.2.1, §10.4.1. - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, Appendix A §A.1。