初級Mathマニアの寝言

数学は色々なところで応用可能であり、多くの人が数学の抽象的な概念の意味や意義を鮮明に知ることができれば今まで以上に面白い物や仕組みが生まれるかもしれません。このブログは数学を専門にしない人のために抽象的な概念の意味や意義を分かりやすく説明することを目的としています。数学を使って何かしたい人のお役に立てたら幸いです。

Courant-Fischerの定理,主成分分析,最適化の概要など

に載せてる8回目の動画

ではCourant-Fischerの定理,主成分分析,最適化の概要などを説明しています.

・0~27分ぐらいまで:Courant-Fisherの定理の説明

・27分ぐらい~58分ぐらいまで:Courant-Fisherの定理の応用(シュティーフェル多様体が登場します)

・58分ぐらい~1時間15分ぐらいまで:Courant-Fisherの定理の主成分分析への応用

・1時間15分ぐらい~1時間33分ぐらいまで:Courant-Fisherの定理の特異値分解への応用

・1時間33分ぐらい~最後まで:最適化の概要(1時間42分40秒ぐらいから何回か「勾配は等高線に接する」とか言ってますが,「勾配は等高線に直交する」の間違いですね(時間がなくて焦ってたように記憶しております).こんな感じの言い間違い授業終わって少ししてから気付くことよくあるんですが,あちゃーって感じですね.

動画で利用している資料は

です.

シュール分解,スペクトル分解,(半)正定値対称行列,特異値分解など

に載せてる7回目の動画

では,シュール分解,スペクトル分解,(半)正定値対称行列,特異値分解などを説明しています.興味がありましたらご覧ください.

・0~34分まで:シュール分解,スペクトル分解について説明しています.

・34分~1時間20分まで:(半)正定値対称行列を説明しています.

・1時間20分~最後まで:特異値分解を説明しています.

動画で利用している資料は

 です.

ノルム,内積,射影など

に載せてる6回目の動画

では,ノルム,内積,射影などを説明しています.興味がありましたらご覧ください.

・0~1時間5分ぐらいまで:ノルム,内積を導入して,任意の有限次元ノルム空間はバナッハ空間であることを説明しています.

・1時間5分~1時間38分ぐらいまで:凸集合上やベクトル空間上への射影の説明をしています.

・1時間38分ぐらい~最後まで:グラム・シュミットの直交化法QR分解を説明しています.

動画で利用している資料は

です.また

も利用しています.

発展的な線形代数の資料について

 東京大学大学院情報理工学系研究科の線形数理要論という授業を担当しているのですが,新型コロナ対策のためオンライン授業をすることになり,急遽オンライン向けの資料などを用意することになりました.線形代数の発展版なので興味がございましたら以下をご覧ください.

www.kazuhirosato.work

特異値分解

この記事では線形代数の基本定理とも言われるほど応用上非常に重要な特異値分解について解説します。今はやりのデータサイエンスでもかなり使われています。

対称行列のスペクトル分解

特異値分解は対称行列のスペクトル分解に密接に関係しているので、まずは対称行列のスペクトル分解について説明します。

実数を成分に持つ正方行列  A=(a_{ij})\in {\bf R}^{n\times n}対称行列だとしましょう。すなわち、 a_{ij}=a_{ji} です。このとき、\begin{align} Av_i = \lambda_i v_i \end{align} となる  \lambda_i\in {\bf R} 0 \neq v_i\in {\bf R}^n が存在します。ただし、 i=1, 2,\ldots, n です。よく知られているように、このような  \lambda_i A固有値 v_i A の固有値  \lambda_i に対応する固有ベクトルと呼びます。行列  A が対称なので、固有ベクトルの集合  \{ v_1,v_2,\ldots, v_n\} {\bf R}^n の正規直交基底とすることができます。いま、\begin{align} V &:= \begin{pmatrix} v_1 & v_2 & \cdots & v_n \end{pmatrix},\quad D:= {\rm diag} (\lambda_1,\lambda_2,\ldots, \lambda_n) \end{align} とすると、\begin{align} A = VDV^T\end{align} となります。右辺の  VDV^T を対称行列  Aスペクトル分解と言います。より詳しくは、以下の記事を参照してください。

特異値分解

次に、 A\in {\bf R}^{m\times n} m\neq n でも良い場合を考えてみましょう。正方でない、つまり  m\neq n の場合は、 A の固有値や固有ベクトルを考えることができないので  A をスペクトル分解することができません。しかし、 A^TA {\bf R}^{n\times n} に入っているので正方であり、しかも対称行列です。よって、 A^TA のスペクトル分解を考えることができます。

対称行列  A^TA のスペクトル分解を\begin{align} A^TA = VDV^T\end{align}としましょう。ただし、 D は対角行列で対角成分に  A^TA の固有値  \lambda_i が並び、 V\in {\bf R}^{n\times n} の各列ベクトルは  A^TA の固有ベクトル  v_i からなる  {\bf R}^n の正規直交基底  \{v_1, v_2,\ldots, v_n\} で構成されているとします。ただし、 \lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n とします。このとき、\begin{align} \langle Av_i, Av_j\rangle = \lambda_j \langle v_i, v_j \rangle = \begin{cases} \lambda_i\quad (i=j)\\ 0\quad\,\,\,\,\,\, (i\neq j) \end{cases} \end{align} となります。ただし、 \langle \cdot, \cdot \rangle はユークリッド内積です。したがって、 \{Av_1, Av_2,\ldots, Av_n\} は直交しており、ゼロでないベクトルは  {\rm Im}\,A\subset {\bf R}^m の基底を構成します。また、 i=j とすると\begin{align} ||Av_i||^2 = \lambda_i \end{align} となるので  \lambda_i\geq 0 が分かります。よって、 {\rm rank}\,A=k だとすると、\begin{align} \lambda_i = 0\quad (k<i\leq n)\end{align} となります。したがって、\begin{align} u_i:= \frac{Av_i}{||Av_i||} = \frac{1}{\sqrt{\lambda_i}} Av_i\quad (1\leq i\leq k) \end{align} は  {\rm Im}\,A\subset {\bf R}^m の正規直交基底を構成します。もし、 k<m の場合は、この正規直交基底を  {\bf R}^m の正規直交基底へ延長することもできます。実際に、この正規直交基底をなすベクトル  u_1,u_2,\ldots,u_k に一次独立な  m-k 個のベクトルをもってきて次の記事で解説したグラム・シュミットの直交化法を利用することで  {\bf R}^m の正規直交基底  \{u_1,u_2,\ldots,u_m\} を作ることができます。

以上より、\begin{align} Av_i &= \sigma_i u_i\quad (1\leq i\leq k)\\ Av_i &=0\quad\,\,\,\,\,\, (k<i\leq n) \end{align} となります。ただし、 \sigma_i:= \sqrt{\lambda_i} です。このことより、  \Sigma:= {\rm diag}(\sigma_1,\sigma_2,\ldots, \sigma_k,0,\ldots, 0)\in {\bf R}^{m\times n} を用いると(作り方から  \sigma_1\geq \sigma_2\geq \cdots \geq \sigma_k>0 であることに注意)、行列  A は\begin{align} A=U\Sigma V^T \end{align} と分解できることが分かります。ただし、\begin{align} U:=\begin{pmatrix} u_1 & u_2 & \cdots & u_m \end{pmatrix}\end{align} で  \{u_1,u_2,\ldots, u_m\} {\bf R}^m の正規直交基底です。この  U\Sigma V^T A特異値分解 \sigma_1, \sigma_2,\ldots, \sigma_k A特異値 U の各列を左特異ベクトル V の各列を右特異ベクトルと言います。特異値分解は、以下のように任意の行列による写像が回転や拡大の写像に分解できることを意味しています。

f:id:ogyahogya:20190819152422p:plain

また、特異値分解は\begin{align} A= \sum_{i=1}^k \sigma_i u_i v_i^T \end{align} というように、 {\rm rank}\, A=k 個分だけランク1の行列を加算することを意味します。この表現を用いると、任意の  x=x_1v_1+x_2v_2+\cdots +x_nv_n\in {\bf R}^n に対して\begin{align} Ax = \sigma_1x_1u_1+\sigma_2x_2u_2+\cdots +\sigma_k x_k u_k \end{align}が成り立つことが分かります。特に、 x_1=x_2=\cdots =x_n=1 なら\begin{align} Ax = \sigma_1u_1+\sigma_2u_2+\cdots +\sigma_k  u_k \end{align}となります。このことを  k=2 A\in {\bf R}^{2\times 2} に対して可視化したのが上の図です。

行列の作用素ノルム

任意の  A\in {\bf R}^{m\times n} に対して\begin{align} ||A||:= \max_{x\in {\bf R}^n\backslash\{0\}} \frac{||Ax||}{||x||} = \max_{||x||=1} ||Ax|| \end{align}とすると  \|\cdot \| はノルムとなります。このノルムを作用素ノルムと言います。以下のように、行列  A の作用素ノルムは最大特異値になります。

f:id:ogyahogya:20191229184335p:plain

f:id:ogyahogya:20191229184349p:plain

例えば、 U^TU=I となる任意の  U\in {\bf R}^{s\times m} の作用素ノルムは  1 になります。なぜなら、任意の  x\in {\bf R}^m に対して\begin{align} ||Ux||^2=x^TU^TUx=||x||^2 \end{align} が成り立つからです。また、サイズの異なる行列  A\in {\bf R}^{m\times n},\, B\in {\bf R}^{n\times p} に対して\begin{align} ||AB||\leq ||A||\cdot ||B|| \end{align}が成り立ちます。なぜなら、任意の  x\in {\bf R}^n に対して\begin{align} ||ABx||\leq ||A||\cdot ||Bx||\leq ||A||\cdot ||B||\cdot ||x|| \end{align} が成り立つからです。さらに、以下が成り立ちます。

f:id:ogyahogya:20191229191417p:plain

証明は以下の通りです。

f:id:ogyahogya:20191229191436p:plain

行列の低ランク近似

与えられた行列  A\in {\bf R}^{m\times n} の最適な近似が特異値分解を利用することで以下のように得られます。この結果はエッカート・ヤング(Eckart-Young)の定理と言われています。

f:id:ogyahogya:20200114120225p:plain

証明は以下の通りです。

f:id:ogyahogya:20191229192723p:plain

f:id:ogyahogya:20191229192733p:plain

f:id:ogyahogya:20191229192747p:plain

 この定理は以下を意味します。

f:id:ogyahogya:20191230121939p:plain

この定理は行列  A\in {\bf R}^{m\times n} のランクを  k だとしたときに、ランク  k-1 以下で  A に最も近い行列が  A 自身を特異値分解することで得られることを示しており、このことから特異値分解が応用上非常に重要だということになります。例えばデータサイエンスの文脈では、 A はデータを格納した行列ということが多いですが、この  A のサイズが非常に大きい( m, n が非常に大きい)と情報処理が大変になります。このようなときに、 A を特異値分解して、 A に最も近い低ランクな行列を構成する特異値と特異ベクトルを抽出しておけば、データ処理が非常に簡単になります

参考文献

この記事を書くにあたって参考にした文献です。

世界標準MIT教科書 ストラング:線形代数イントロダクション

世界標準MIT教科書 ストラング:線形代数イントロダクション

 
現代線形代数 ―分解定理を中心として―

現代線形代数 ―分解定理を中心として―

 
Approximation of Large-Scale Dynamical Systems (Advances in Design and Control)

Approximation of Large-Scale Dynamical Systems (Advances in Design and Control)

  • 作者:Athanasios C. Antoulas
  • 出版社/メーカー: Society for Industrial and Applied Mathematics
  • 発売日: 2009/06/25
  • メディア: ペーパーバック
 

 

行列のシュール分解

この記事では、与えられた複素正方行列  A\in {\bf C}^{n\times n}シュール分解を紹介します。また、応用上よく利用される実対称行列のスペクトル分解はシュール分解の特別な場合であることも説明します。

シュール分解

以下のような行列  A\in {\bf C}^{n\times n} の固有値が対角成分に並んだ上三角行列への分解をシュール分解と言います。

f:id:ogyahogya:20191228170359p:plain

ただし、 \dagger は複素共役転置を表します。これの証明は以下の通りです。

f:id:ogyahogya:20191228170423p:plain

f:id:ogyahogya:20191228170434p:plain

f:id:ogyahogya:20191228170501p:plain

f:id:ogyahogya:20191228170527p:plain

証明の中でグラム・シュミットの直交化法を利用しました。グラム・シュミットの直交化法は以下の記事で解説しています。

正規行列:シュール分解によって対角化可能な行列

一般の行列  A\in {\bf C}^{n\times n} はシュール分解によって上三角行列に分解できることを上で示しましたが、 A正規行列、すなわち\begin{align} AA^{\dagger} = A^{\dagger}A \end{align}を満たすなら以下で示すようにシュール分解によって対角化できます。正規行列の例としては、複素数を成分にもつユニタリ行列、エルミート行列、反エルミート行列や実数を成分に持つ直交行列、対称行列、反対称行列があります。

f:id:ogyahogya:20191229105800p:plain

証明は以下の通りです。

f:id:ogyahogya:20191229105830p:plain

f:id:ogyahogya:20191229105847p:plain

f:id:ogyahogya:20191229110038p:plain

f:id:ogyahogya:20191229110046p:plain

エルミート行列

正規行列の特別な場合であるエルミート行列に限定したときに、シュール分解がどうなるかを調べます。そのために、エルミート行列  A\in {\bf C}^{n\times n} のすべての固有値は実数だったことを思い出しましょう。実際に、 Ax= \lambda x\quad (x\neq 0) とすると、\begin{align} x^{\dagger}Ax = \lambda x^{\dagger}x \end{align} となりますが、 x^{\dagger}x は非ゼロの実数で、 (x^{\dagger}Ax)^{\dagger} = x^{\dagger}Axなので左辺も実数なので、 \lambda は実数となります。したがって、エルミート行列  A のシュール分解を考えると、次の結論を得ます。

f:id:ogyahogya:20191229120011p:plain

すなわち、エルミート行列は固有値によって重み付けされた直交射影の和として表現されます。実数の世界での直交射影は

で説明しましたが、少し修正すると複素数に対しても成り立ちますので、 u_iu_i^{\dagger} u_i が張る1次元部分空間への直交射影だということになります。

対称行列

エルミート行列の特別な場合である実数を成分に持つ対称行列に限定したときに、シュール分解がどうなるかを調べます。そのために、対称行列  A\in {\bf R}^{n\times n} の固有値は実数であり、固有ベクトルとして実ベクトルを常に選ぶことができることを思い出しましょう。実際に、固有値が実数であることはエルミート行列のところの議論と同じですし、固有ベクトルを実ベクトルとして選ぶことが可能なのは以下のように示せます。

f:id:ogyahogya:20191229123736p:plain

f:id:ogyahogya:20191229123811p:plainしたがって、対称行列  A のシュール分解を考えると、次の結論を得ます。

f:id:ogyahogya:20191229123906p:plainすなわち、エルミート行列の場合と同様に、対称行列は固有値によって重み付けされた直交射影の和として表現されます。ただし、ここの直交射影は

で説明した直交射影とまったく同じです。


参考文献

記事を書くにあたって参考にした文献です。

これならわかる工学部で学ぶ数学

これならわかる工学部で学ぶ数学

  • 作者:千葉 逸人
  • 出版社/メーカー: プレアデス出版
  • 発売日: 2009/01/01
  • メディア: 単行本
 
現代線形代数 ―分解定理を中心として―

現代線形代数 ―分解定理を中心として―

 
世界標準MIT教科書 ストラング:線形代数イントロダクション

世界標準MIT教科書 ストラング:線形代数イントロダクション

 

グラム・シュミットの直交化法とQR分解

この記事では、グラム・シュミットの直交化法QR分解について解説します。

グラム・シュミットの直交化法

ベクトル  a_1, a_2, \ldots, a_n\in {\bf R}^n は一次独立だとします。このとき、 \{a_1,a_2,\ldots,a_n\} {\bf R}^n の基底となります。しかし、 \{a_1,a_2,\ldots,a_n\} {\bf R}^n正規直交基底ではないかもしれません。グラム・シュミットの直交化法は  {\bf R}^n の任意の基底  \{a_1,a_2,\ldots,a_n\} から以下のように正規直交基底を構成する方法です。\begin{align} q_1 &:=\frac{a_1}{||a_1||}\\ q_k &:= \frac{a_k-P_{q_1,\ldots,q_{k-1}}(a_k)}{||a_k-P_{q_1,\ldots,q_{k-1}}(a_k)||}\quad (k=2,\ldots,n) \end{align}

ただし、 P_{q_1,\ldots,q_{k-1}} {\rm Im}\, Q_{k-1} 上への直交射影で、\begin{align}Q_{k-1}:= \begin{pmatrix} q_1 & q_2 & \cdots & q_{k-1} \end{pmatrix}\in {\bf R}^{n\times (k-1)}\end{align}

です。ベクトル  q_i の作り方から  Q_{k-1}^TQ_{k-1}=I となるので、直交射影  P_{q_1,\ldots,q_{k-1}}

で説明したように、\begin{align}P_{q_1,\ldots,q_{k-1}} = Q_{k-1}Q_{k-1}^T=q_1q_1^T+q_2q_2^T+\cdots+ q_{k-1}q_{k-1}^T \end{align} となります。

 {\bf R}^2 の場合のグラム・シュミットの直交化法は次のような感じでイメージできます。

f:id:ogyahogya:20191228102436p:plain

 {\bf R}^3 の場合は次のような感じです。

f:id:ogyahogya:20191228102519p:plain

 QR分解

ベクトル  a_1, a_2, \ldots, a_n\in {\bf R}^n は一次独立だとして、\begin{align} A:= \begin{pmatrix} a_1 & a_2 & \cdots & a_n \end{pmatrix}\in {\bf R}^{n\times n} \end{align} だとします。グラム・シュミットの直交化法により、 c_k:=||a_k-P_{q_1,\ldots,q_{k-1}}(a_k)|| とすると、以下のように行列  A を分解できます。

f:id:ogyahogya:20191228114946p:plain

f:id:ogyahogya:20191228115047p:plain

このように、行列  A を直交行列  Q と 上三角行列  R へ分解することを  AQR分解と言います。QR分解の構成から、QR分解することはグラム・シュミットの直交化をすることと同値ですので、 A の各列ベクトルが一次独立なら常に  A のQR分解を実行することができます。

注意1

 m\geq n でベクトル  a_1, a_2, \ldots, a_n\in {\bf R}^m は一次独立だとします ( m<n の場合は一次独立にならないので考えません)。 m=n の場合は上と同じなので、 m>n の場合の注意を書いときます。

 m>n の場合も上のグラム・シュミットの直交化法はまったく同じように実行できて、 a_1, a_2, \ldots, a_n\in {\bf R}^m から正規直交ベクトル  q_1, q_2, \ldots, q_n\in {\bf R}^m を得ることができます。このとき\begin{align} A:= \begin{pmatrix} a_1 & a_2 & \cdots & a_n \end{pmatrix}\in {\bf R}^{m\times n} \end{align} は\begin{align} A=QR \end{align} というようにQR分解できます。ただし、 R m=n の場合と同じ  n\times n の上三角行列ですが、\begin{align} Q:= \begin{pmatrix} q_1 & q_2 & \cdots & q_n \end{pmatrix}\in {\bf R}^{m\times n} \end{align}は各列が正規直交しているものの、 m>n なので直交行列とは言えません。このような各列が正規直交している行列全体の集合をシュティーフェル多様体と言い、色々な応用で出てきます。

注意2

 m\geq n でベクトル  a_1, a_2, \ldots, a_n\in {\bf C}^m は一次独立だとします。注意1との違いはベクトルの成分が実数ではなく、複素数だということです。この場合もグラム・シュミットの直交化法が適用できます。ただし、ノルムの定義や直交射影に若干の変更が必要です。すなわち、 x\in {\bf R}^m の場合のノルムは(陽に書いていませんでしたが)\begin{align} ||x||^2 = x_1^2+x_2^2+\cdots +x_m^2 \end{align} だとしていましたが、 x\in {\bf C}^m のノルムは\begin{align} ||x||^2 = |x_1|^2+|x_2|^2+\cdots +|x_m|^2 \end{align} に変更する必要があります。また、直交射影は\begin{align} P_{q_1,\ldots,q_{k-1}} =Q_{k-1}Q_{k-1}^{\dagger} \end{align} と変更されます。ただし、 \dagger は複素共役転置を表しています。この変更のもとで、\begin{align} A:= \begin{pmatrix} a_1 & a_2 & \cdots & a_n \end{pmatrix}\in {\bf C}^{m\times n} \end{align} は\begin{align} A=QR \end{align} というようにQR分解できます。ただし、 Q\in {\bf C}^{m\times n} は各列が正規直交しており、 R\in {\bf C}^{n\times n} は上三角行列です。さらに、 m=n の場合には  Q\in {\bf C}^{n\times n} はユニタリ行列となります。

参考文献

この記事を書くにあたって参考にした文献です。

世界標準MIT教科書 ストラング:線形代数イントロダクション

世界標準MIT教科書 ストラング:線形代数イントロダクション