特異値分解 - yuuk1's Digital Garden

# 特異値分解 ## 定義任意の行列 $A\in\mathbb{R}^{m\times n}$(階数 $r\in[0,\min(m,n)]$)は、直交行列 $U\in\mathbb{R}^{m\times m}$、$V\in\mathbb{R}^{n\times n}$ と、対角成分に特異値(singular value)$\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r\geq0$ を降順に並べた $m\times n$ 行列 $\Sigma$ を用いて $A = U\Sigma V^\top$ と分解できる(SVD定理、Theorem 4.22)。$U$ の列($u_i$、左特異ベクトル)は $AA^\top$ の固有ベクトル、$V$ の列($v_i$、右特異ベクトル)は $A^\top A$ の固有ベクトルであり、非零特異値は両者の非零固有値の平方根 $\sigma_i=\sqrt{\lambda_i}$ に一致する。特異値方程式 $Av_i=\sigma_i u_i$ が両者を結びつける。SVDは行列の正方性を一切要求せず、任意の行列に対して常に存在する点が「線形代数の基本定理」(Strang, 1993)と呼ばれる所以である。幾何的には、SVDは「$V^\top$ による定義域 $\mathbb{R}^n$ 内での基底変換」「$\Sigma$ による特異値方向ごとのスケーリングと次元の拡大・縮小」「$U$ による値域 $\mathbb{R}^m$ 内での基底変換」という3段階の合成写像である。固有値分解と異なり、定義域と値域という2つの異なる空間でそれぞれ独立な基底変換が行われ、$U,V$ は互いに逆行列の関係にない(それぞれ別の空間での回転を表す)。対称行列に限れば固有値分解とSVDは一致する。SVDの上位 $k$ 項による階数k近似 $\hat A(k)=\sum_{i=1}^k\sigma_i u_iv_i^\top$ は、Eckart-Young定理(Theorem 4.25)によりスペクトルノルムの意味で最適な低ランク近似であることが保証される。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 4 Matrix Decompositions]] §4.5, §4.6) ## 横断的知見 - 1ソース目のため、他のソースとの突き合わせによる知見は今後の蓄積に委ねる。本概念は同一章内の[[固有値分解]]との対比で輪郭が明確になる: 固有値分解が正方行列かつ固有ベクトルが基底を成す場合にのみ存在する条件付きの分解であるのに対し、SVDは正方性も基底の存在も要求せず任意の行列に対して常に存在する。「常に存在する分解」という一般性こそが、SVDが固有値分解より広い応用範囲(非正方のデータ行列、欠損値のある行列、画像圧縮など)を持つ理由になっている。 - **第10章(主成分分析)は、本概念のEckart-Young定理(定理4.25)を低ランク近似の直接的な計算手段として使う**: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 10 Dimensionality Reduction with Principal Component Analysis]] §10.4.1は、データ共分散行列$S=\frac1NXX^\top$の固有値分解を経由せずとも、データ行列$X$自体のSVD $X=U\Sigma V^\top$を打ち切ることで主成分分析の解を直接得られることを示す。Eckart-Young定理により、$X$のランク$M$最良近似$\tilde X_M=U_M\Sigma_MV_M^\top$(上位$M$特異値のみを残す)がスペクトルノルムの意味で最適であることが保証され(本ページ§4.6が既に述べた性質)、$U_M$の列がそのままPCAの主成分方向になる。さらに$S$の固有値$\lambda_d$と$X$の特異値$\sigma_d$は$\lambda_d=\sigma_d^2/N$という具体的な関係式(式10.49)で結びつき、「固有値分解を使うか本概念(SVD)を使うか」という選択は数学的に等価な2つの計算経路であることが確認できる。これは本ページの未解決の問いへの回答であり、[[主成分分析]]ページにも同じ横断的知見を記載した。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 4 Matrix Decompositions]] §4.5–§4.6, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 10 Dimensionality Reduction with Principal Component Analysis]] §10.4.1) - **PCAの射影行列としての解釈は、本概念の低ランク近似とは異なる対象への同じ数学的道具の適用である**: 第10章§10.3.3は、PCAの射影行列$BB^\top$(ランク$M$)が恒等行列$I$のランク$M$最良近似であると解釈する(Remark, 式10.39–10.40)。これは本ページのEckart-Young定理がデータ行列$X$自体の近似に使われる場面(上記)とは別に、「射影」という操作自体もランク制約付き最良近似として捉え直せることを示しており、低ランク近似という単一の数学概念がPCAの導出の複数箇所(データの近似・射影行列の近似)で異なる役割を果たすことが分かる。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 10 Dimensionality Reduction with Principal Component Analysis]] §10.3.3, §10.4.1) - **[[@2022__Gihyo__ディープラーニングを支える技術 - Appendix A ［厳選基礎］機械学習＆ディープラーニングのための数学]] は、本概念を「証明抜きの結果」として1文で提示する**: 同 Appendix A §A.1 は「任意の行列 $A$ は直交行列 $U,V$、対角行列 $S$ を用いて $A=USV^\top$ のように分解できる」とだけ述べ、MML第4章が積み上げる左右特異ベクトルと $AA^\top$・$A^\top A$ の固有ベクトルとの対応関係、特異値方程式 $Av_i=\sigma_iu_i$、Eckart-Young定理による低ランク近似の最適性保証にはいずれも触れない。この対比は、同じSVDという道具でも「なぜ成り立つか・何に最適か」を厳密に積み上げる数学専門書と、「何ができるか」だけを結果として渡すDL実装者向け書籍とで、選び取る情報量が大きく異なることを裏づける——[[固有値分解]]ページで確認した同種の非対称性が、本概念でも同じ形で再現される。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 4 Matrix Decompositions]] §4.5, [[@2022__Gihyo__ディープラーニングを支える技術 - Appendix A ［厳選基礎］機械学習＆ディープラーニングのための数学]] §A.1) ## 未解決の問い - 機械学習実務での低ランク近似の応用(推薦システムの行列分解、埋め込み圧縮など)との対応関係は、既存の応用文脈のconcept(例: [[モデル圧縮]])との突き合わせが必要である。 - 特異値分解とテンソル分解(Tucker分解・CP分解)の関係は本章では言及のみで詳細に踏み込んでいない(§4.8)。テンソル分解を扱うソースが入った際に接続する。 - 第10章§10.5は$N\ll D$のとき$D\times D$の共分散行列でなく$N\times N$のグラム行列$\frac1NX^\top X$の固有値問題に変換する手法を示すが、これをSVD側(本概念)で行う場合の数値的な扱い(例えば経済SVD/thin SVDとの関係)は本書では明示的に論じられていない。 - [[@2022__Gihyo__ディープラーニングを支える技術 - Appendix A ［厳選基礎］機械学習＆ディープラーニングのための数学]] は SVD を証明抜きで導入するのみで、本編(第1〜5章)で SVD が実際にどの手法(次元圧縮・行列圧縮など)に使われるかは 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]](Eckart-Young定理によるPCAの低ランク近似としての実装) / [[@2022__Gihyo__ディープラーニングを支える技術 - Appendix A ［厳選基礎］機械学習＆ディープラーニングのための数学]] - concept: [[固有値分解]] / [[主成分分析]](本書のSVD・低ランク近似がPCAの数学的基礎を与える関係) - entity: [[Mathematics for Machine Learning]] / [[wiki/entities/ディープラーニングを支える技術|ディープラーニングを支える技術]] ## 出典 - Deisenroth, Faisal, Ong, *Mathematics for Machine Learning*, Cambridge University Press, 2020, §4.5 (Singular Value Decomposition), §4.6 (Matrix Approximation), §10.4.1 (PCA Using Low-Rank Matrix Approximations). - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, Appendix A §A.1。