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

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

最小ノルム解の基礎をまとめる

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

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

行列における全射,左零空間が零ベクトルのみ,行フルランクは同値であることを証明する - エンジニアを目指す浪人のブログ

グラム行列についての定理を証明する - エンジニアを目指す浪人のブログ

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

行列のランク落ち,列フルランク,行フルランク,フルランクそれぞれのときの4つの基本部分空間を図示する - エンジニアを目指す浪人のブログ


勉強を進めていて,最小ノルム解(least norm solutions)について知りました.応用でよく使われているようなので,その内容をまとめておくことにしました.Boyd and Vandenberghe(2018)の16章1,2,3節を参考にして,問題を設定し最小ノルム解を導出していきます.

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

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. 制約付き最小二乗問題としての最小ノルム問題
{\displaystyle \; } 2. 解
{\displaystyle \;\;\; } 2.1. KKT方程式
{\displaystyle \;\;\; } 2.2. 最小ノルム解


[ 0. 準備 ]

記号を準備します.

{\displaystyle \;\;\; I \;\;\;\;\;\;\;\;\;\;  } {\displaystyle n \times n } 単位行列
{\displaystyle \;\;\; x \;\;\;\;\;\;\;\;\;\; } {\displaystyle n } 次元ベクトル ( {\displaystyle  x = [ x_1 \ \cdots \ x_n ]^T } )
{\displaystyle \;\;\; z \;\;\;\;\;\;\;\;\;\; } {\displaystyle p } 次元ベクトル
{\displaystyle \;\;\; A \;\;\;\;\;\;\;\;\;\; } {\displaystyle m \times n } 行列
{\displaystyle \;\;\; C \;\;\;\;\;\;\;\;\;\; } {\displaystyle p \times n } 行列
{\displaystyle \;\;\; b \;\;\;\;\;\;\;\;\;\; } {\displaystyle m } 次元ベクトル
{\displaystyle \;\;\; d \;\;\;\;\;\;\;\;\;\; } {\displaystyle p } 次元ベクトル
{\displaystyle \;\;\; \lambda \;\;\;\;\;\;\;\;\;\; } 正の実数

 {\displaystyle  \langle \cdot , \cdot \rangle \;\;\; } 通常の内積  {\displaystyle \langle x,y \rangle = y^T x \;\;\; } (性質は文献[2]にあります)
{\displaystyle \left\| \cdot \right\| \;\;\; } (ユークリッド)ノルム {\displaystyle \left\| x \right\| = \sqrt{ x^T x } = \sqrt{ x_1^2 + \cdots + x_n^2 } \;\;\; } (性質は文献[3]にあります)



[ 1. 制約付き最小二乗問題としての最小ノルム問題 ]

最小ノルム問題のベースである制約付き最小二乗問題(constrained least squares problem)は,冒頭の過去記事(制約付き最小二乗法)にあるように以下です.

(1.0)
{\displaystyle \;\;\; \mathrm{minimize} \;\;\;\; \left\| Ax - b \right\|^2 }
{\displaystyle \;\;\; \mathrm{subject \; to} \;\;\ Cx=d }


制約付き最小二乗問題(1.0)で {\displaystyle A=I, \ b=0} として以下です.

(1.1)
{\displaystyle \;\;\; \mathrm{minimize} \;\;\;\; \left\| x \right\|^2 }
{\displaystyle \;\;\; \mathrm{subject \; to} \;\;\ Cx=d }

これは連立一次方程式 {\displaystyle Cx=d } をみたす最小のノルムをもつベクトルを探索する問題であり,最小ノルム問題(least norm problem)(minimum-norm problem)といいます.

冒頭の過去記事(制約付き最小二乗法)仮定.(0.1)(0.2)は以下となります.(1.4)は(任意の {\displaystyle C} について)常に成り立ちます.

仮定.
(1.3) {\displaystyle \; C } は線形独立な行をもつ.

(1.4) {\displaystyle \; \begin{bmatrix} I \\ C \end{bmatrix} } は線形独立な列をもつ.

さらに以下を仮定し以後 {\displaystyle C } は行フルランクであるとします.冒頭の過去記事(行列における全射)も参考になります.

仮定.
(1.5) {\displaystyle \; C } は横長の行列( {\displaystyle \Leftrightarrow [ p \lt n ] } )



[ 2. 解 ]
[ 2.1. KKT方程式 ]

冒頭の過去記事(制約付き最小二乗法)KKT方程式(2.1.1)は {\displaystyle A=I, \ b=0} として以下です.この方程式をみたす解を {\displaystyle (x,z) = (\hat{x},\hat{z}) } とします.

(2.1.1) {\displaystyle \;\;\; \begin{bmatrix} 2 I & C^T \\  C & 0 \end{bmatrix} \begin{bmatrix} x \\ z \end{bmatrix} = \begin{bmatrix} 0 \\ d \end{bmatrix}  \;\;\;\;\;\; ( (n + p) \times (n + p) ) \times ( (n + p) \times 1 )  = (n + p) \times 1 }

同記事のただ一つの解(2.1.2)は同様に以下です.

(2.1.2){\displaystyle \;\;\;  \begin{bmatrix} \hat{x} \\ \hat{z} \end{bmatrix} = \begin{bmatrix} 2 I & C^T \\  C & 0 \end{bmatrix}^{-1} \begin{bmatrix} 0 \\ d \end{bmatrix} }


[ 2.2. 最小ノルム解 ]

行列 {\displaystyle C C^T } について以下が成り立ちます.{\displaystyle \tilde{c}_1^T,\ldots,\tilde{c}_n^T }{\displaystyle C } の行です.

{\displaystyle \;\;\; C C^T = \begin{bmatrix} \tilde{c}_1^T \\ \tilde{c}_2^T \\ \vdots \\ \tilde{c}_n^T  \end{bmatrix} \begin{bmatrix} \tilde{c}_1 & \tilde{c}_2 & \cdots & \tilde{c}_n  \end{bmatrix} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\; =  \begin{bmatrix} \tilde{c}_1^T \tilde{c}_1 & \tilde{c}_1^T \tilde{c}_2 & \cdots & \tilde{c}_1^T \tilde{c}_n \\ \tilde{c}_{2}^T \tilde{c}_1 & \tilde{c}_{2}^T \tilde{c}_2 & \cdots & \tilde{c}_{2}^T \tilde{c}_n \\ \vdots  & \vdots & \vdots  \\ \tilde{c}_{n}^T \tilde{c}_1 & \tilde{c}_{n}^T \tilde{c}_2  & \cdots & \tilde{c}_{n}^T \tilde{c}_n \end{bmatrix}  }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\; =  \begin{bmatrix} \tilde{c}_{1}^T \tilde{c}_1 & \tilde{c}_{2}^T \tilde{c}_1 & \cdots & \tilde{c}_{n}^T \tilde{c}_1 \\ \tilde{c}_{1}^T \tilde{c}_2 & \tilde{c}_{2}^T \tilde{c}_2 & \cdots & \tilde{c}_{n}^T \tilde{c}_2 \\ \vdots  & \vdots & \vdots  \\ \tilde{c}_{1}^T \tilde{c}_n & \tilde{c}_{2}^T \tilde{c}_n  & \cdots & \tilde{c}_{n}^T \tilde{c}_n \end{bmatrix}  }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\; =  \begin{bmatrix} \langle \tilde{c}_1,\tilde{c}_1 \rangle & \langle \tilde{c}_2,\tilde{c}_1 \rangle & \cdots & \langle \tilde{c}_n,\tilde{c}_1 \rangle \\ \langle \tilde{c}_1,\tilde{c}_2 \rangle & \langle \tilde{c}_2,\tilde{c}_2 \rangle & \cdots & \langle \tilde{c}_n,\tilde{c}_2 \rangle \\ \vdots & \vdots & \vdots & \vdots \\ \langle \tilde{c}_1,\tilde{c}_n \rangle & \langle \tilde{c}_2,\tilde{c}_n \rangle & \cdots & \langle \tilde{c}_n,\tilde{c}_n \rangle \end{bmatrix}  }


これはグラム行列であり,仮定.(1.3)と冒頭の過去記事(グラム行列)定理 7.2.10.(b)から {\displaystyle C C^T } は正定値したがって正則です.このことは後で用います.


(2.1.1)の上部の方程式について以下を得ます.

{\displaystyle \;\;\; 2 \hat{x} + C^T \hat{z} = 0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \hat{x} = - (1/2) C^T \hat{z}  \;\;\; } (※)

(2.1.1)の下部の方程式について以下を得ます.

{\displaystyle \;\;\; C \hat{x} = d }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \  C ( -(1/2) C^T \hat{z} ) = d \;\;\; \because } (※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ -(1/2) C C^T \hat{z} = d }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \  C C^T \hat{z} =-2 d }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \   \hat{z} =-2 (C C^T)^{-1} d \;\;\;\;\; \because } 仮定.(1.3)より {\displaystyle C^T } は線形独立な列をもつので {\displaystyle C C^T } は正則

(2.1.1)の上部の方程式に戻って以下を得ます.

{\displaystyle \;\;\; } (※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \hat{x} = - (1/2) C^T (-2 (C C^T)^{-1} d )  \;\;\; }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \hat{x} = C^T (C C^T)^{-1} d  }


したがって(2.1.1)は以下で表されるただ一つの解をもちます.

(2.2.1){\displaystyle \;\;\; \hat{x} =  C^T (C C^T)^{-1} d  }

仮定.より {\displaystyle C } は行フルランクであることと冒頭の過去記事(ムーア・ペンローズ逆行列の定義)より行列 {\displaystyle C^T (C C^T)^{-1} } は行列 {\displaystyle C } のムーア・ペンローズ逆行列(擬似逆行列)です.

(2.2.2){\displaystyle \;\;\; C^+ =  C^T (C C^T)^{-1}  }

(2.2.3){\displaystyle \;\;\; \hat{x} =  C^+ d }

{\displaystyle C } は行フルランクなので,連立一次方程式 {\displaystyle Cx = d } はあらゆる {\displaystyle d } について無数の解をもちます.冒頭の過去記事(行列のランク落ち)にあります.{\displaystyle C^+ }{\displaystyle C } の右逆行列なので(2.2.3)は {\displaystyle Cx = d } の無数にある解の一つであり,その(無数にある解の)中で最小のノルムをもつ解です.

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

以上,最小ノルム解の基礎をまとめました.



参考文献
[1] Boyd, S., and Vandenberghe, L. (2018), Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares, Cambridge University Press.
[2] Wolfram MathWorld Inner Product のページ http://mathworld.wolfram.com/InnerProduct.html
[3] Wikipedia Matrix norm のページ https://en.wikipedia.org/wiki/Matrix_norm
[4] Stanford University Stephen Boyd先生のノート https://see.stanford.edu/materials/lsoeldsee263/08-min-norm.pdf

おまけ
[1] へのリンク http://vmls-book.stanford.edu/vmls.pdf