エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

行列のランクに仮定をおかないときの最小二乗法の解表現と列フルランクを仮定することの意味について考える

数学 線形代数 数理最適化

本記事は以下の過去記事の内容を用います．

最小二乗法の基礎をまとめる - エンジニアを目指す浪人のブログ

ムーア・ペンローズ逆行列の定義，構成，一意性についてまとめる - エンジニアを目指す浪人のブログ

ムーア・ペンローズ逆行列と元の行列の4つの基本部分空間との関係について考える - エンジニアを目指す浪人のブログ

ムーア・ペンローズ逆行列による連立一次方程式の解表現について考える - エンジニアを目指す浪人のブログ


最小二乗法(least squares method ; LSM)を説明するとき，冒頭の過去記事(最小二乗法)がそうであるように，対象とする行列が列フルランクであることを仮定している場合が多いです．これは実際の問題に適用することを想定しているためと思います．勉強を進めていて，行列のランクに仮定をおかないときの最小二乗法の解表現と列フルランクを仮定することの意味について知り，とても面白く感じたのでその内容をまとめておくことにしました．Laub(2004)の8章1節を参考にしています．

=================================================================================

記号を準備します．

{\displaystyle \;\;\; \mathbf{R}^{n} \;\;\;\;\;\;\;\; } {\displaystyle \mathbf{R} } の要素を要素にもつ {\displaystyle n } 次元ベクトルの集合
{\displaystyle \;\;\; \mathbf{R}^{m \times n} \;\;\;\; } {\displaystyle \mathbf{R} } の要素を要素にもつ {\displaystyle m \times n } 行列の集合
{\displaystyle \;\;\; I_n \;\;\;\;\;\;\;\;\;\; } {\displaystyle n \times n } 単位行列
{\displaystyle \;\;\; x \;\;\;\;\;\;\;\;\;\; } {\displaystyle n } 次元ベクトル ( {\displaystyle x = [ x_1 \ \cdots \ x_n ]^T } )
{\displaystyle \;\;\; A \;\;\;\;\;\;\;\;\;\; } {\displaystyle m \times n } 行列
{\displaystyle \;\;\; b \;\;\;\;\;\;\;\;\;\; } {\displaystyle m } 次元ベクトル
{\displaystyle \;\;\; C(A^T) \;\;\; } {\displaystyle A } の行空間
{\displaystyle \;\;\; C(A) \;\;\;\;\; } {\displaystyle A } の列空間
{\displaystyle \;\;\; N(A) \;\;\;\;\; } {\displaystyle A } の零空間
{\displaystyle \;\;\; N(A^T) \;\;\; } {\displaystyle A } の左零空間
{\displaystyle \;\;\; A^+ \;\;\;\;\;\;\;\; } {\displaystyle A } のムーア・ペンローズ逆行列(擬似逆行列)( {\displaystyle n \times m } 行列 )


ムーア・ペンローズ逆行列 {\displaystyle A^+ } の定義は冒頭の過去記事(ムーア・ペンローズ逆行列の定義)にあります．

{\displaystyle \left\| \cdot \right\| \;\;\; } (ユークリッド)ノルム {\displaystyle \left\| x \right\| = \sqrt{ x^T x } = \sqrt{ x_1^2 + \cdots + x_n^2 } \;\;\; }



以上の設定のもとで本記事の目的に進みます．

{\displaystyle A \in \mathbf{R}^{m \times n}, \ b \in \mathbf{R}^{m} } とします．線形最小二乗問題(linear least squares problem)とは以下の集合の要素を探索する問題のことです．

{\displaystyle \;\;\; \mathcal{X} = \{ x \in \mathbf{R}^n : \ \rho (x)= \left\| Ax - b \right\|^2 \ \mathrm{is \ minimized} \} }

{\displaystyle r = b - A x } を残差(residual)といいます．


行列のランクに仮定をおかないときの(行列のランク落ち，列フルランク，行フルランク，フルランクすべてのときを包括する)線形最小二乗問題の解表現について，以下の事実が成り立ちます．
'--------------------------------------------------------------------------------------------------------------------------------------------
事実2.
{\displaystyle x \in \mathcal{X} } であるための必要十分条件は {\displaystyle x } が以下の形式で表現できることである．

(8.1){\displaystyle \;\;\; x = A^+ b + (I_n - A^+ A)y, \;\;\; y \in \mathbf{R}^n }


証明.

{\displaystyle \;\;\; r = b - A x }
{\displaystyle \;\;\;\;\; = (b - A A^+ b) + ( A A^+ b - A x) }
{\displaystyle \;\;\;\;\; = (I_m - A A^+ ) b + ( A A^+ b - A x) }

ここで冒頭の過去記事(ムーア・ペンローズ逆行列と元の行列)より以下を得る．

{\displaystyle \;\;\;\;\; ( A A^+ b - A x) \in C(A) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 同記事の事実2.(2.1)
{\displaystyle \;\;\;\;\; (I_m - A A^+ ) b \; \in N(A^T) \; ( = C(A)^\perp ) \;\;\; \because } 同記事の事実2.(2.3)

これらと同記事の事実0.(0.1.2)より以下を得る．

{\displaystyle \;\;\;\;\; ( A A^+ b - A x) \perp (I_m - A A^+ ) b }


したがってピタゴラスの定理より以下を得る．

{\displaystyle \;\;\; \left\| r \right\|^2 = \left\| b - Ax \right\|^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\; = \left\| (I_m - A A^+ ) b + ( A A^+ b - A x) \right\|^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\; = \left\| (I_m - A A^+ ) b \right\|^2 + \left\| A A^+ b - A x \right\|^2 \;\;\; \because } ピタゴラスの定理
{\displaystyle \;\;\;\;\;\;\;\;\;\; \ge \left\| (I_m - A A^+ ) b \right\|^2 }

{\displaystyle \left\| r \right\|^2 } は {\displaystyle x} が {\displaystyle A x = A A^+ b } をみたすとき最小となる．この方程式は冒頭の過去記事(ムーア・ペンローズ逆行列による連立一次方程式)定理6.2(存在).より {\displaystyle A A^+ b \in C(A) } であることからつねに解をもつ．同記事の定理6.3.で {\displaystyle b = A A^+ b } と置き換えてこの方程式のすべての解は以下となる．

{\displaystyle \;\;\; x = A^+ A A^+ b + (I - A^+ A)y }
{\displaystyle \;\;\;\;\;\; = A^+ b + (I - A^+ A)y, \;\;\; y \in \mathbf{R}^n \;\;\; \because } 冒頭の過去記事(ムーア・ペンローズ逆行列の定義)(d.2)

(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------


{\displaystyle x^* = A^+ b } とします．線形最小二乗問題の無数の解のうちの一つである {\displaystyle x^* } について以下の事実が成り立ちます．
'--------------------------------------------------------------------------------------------------------------------------------------------
事実4.
{\displaystyle x^* \in \mathcal{X} } であると同時に，{\displaystyle x^* } はそのような {\displaystyle x } の中で {\displaystyle \left\| x \right\| } を最小化するただ一つのベクトルである．


証明.
前半は事実2.であるので後半を示せばよい．

冒頭の過去記事(ムーア・ペンローズ逆行列と元の行列)より以下を得る．

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; A^+ b \;\;\; \in C(A^T) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 同記事の事実1.(1.1)
{\displaystyle \;\;\;\;\; (I_n - A^+ A ) y \; \in N(A) \; ( = C(A^T)^\perp ) \;\;\; \because } 同記事の事実2.(2.4)

これらと同記事の事実0.(0.1.1)より以下を得る．

{\displaystyle \;\;\; A^+ b \perp (I_n - A^+ A ) y }


したがって {\displaystyle x \in \mathcal{X} } についてピタゴラスの定理より以下を得る．

{\displaystyle \;\;\; \left\| x \right\|^2 = \left\| A^+ b + ( I_n - A^+ A)y \right\|^2 \;\;\;\;\;\;\; \because } 事実2.(8.1)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \left\| A^+ b \right\|^2 + \left\| ( I_n - A^+ A)y \right\|^2 \;\;\; \because } ピタゴラスの定理
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \ge \left\| A^+ b \right\|^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \left\| x^* \right\|^2 }

(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------


最小二乗法において列フルランクを仮定することの意味を説明する以下の事実が成り立ちます．
'--------------------------------------------------------------------------------------------------------------------------------------------
事実5.
線形最小二乗問題がただ一つの解(のみ)をもつ，すなわち {\displaystyle \mathcal{X} = \{ x^* \} = \{ A^+ b \} } が成り立つための必要十分条件は {\displaystyle A^+ A = I_n }，あるいは同じことであるが {\displaystyle A } が列フルランクであることである．


証明.
前半は事実2.の任意項が {\displaystyle 0 } になることからいえる．冒頭の過去記事(ムーア・ペンローズ逆行列の定義)定理 1.(で {\displaystyle G=I_n } とすること)より {\displaystyle A } が列フルランクであることと {\displaystyle A^+ A = I_n } は同値である．よって示せた．(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------


=================================================================================

以上，行列のランクに仮定をおかないときの最小二乗法の解表現と列フルランクを仮定することの意味について考えてみました．



参考文献
[1] Laub, A.J. (2004), Matrix Analysis for Scientists and Engineers, Society for Industrial and Applied Mathematics.
[2] Mathematics Stack Exchange https://math.stackexchange.com/questions/2253443/difference-between-least-squares-and-minimum-norm-solution/2253455

おまけ
[1] へのリンク https://epdf.tips/matrix-analysis-for-scientists-and-engineers6eadd0270d0930c60f36adaea67057c230700.html