最小ノルム解の基礎をまとめる
本記事は以下の過去記事の内容を用います.
制約付き最小二乗法の基礎をまとめる - エンジニアを目指す浪人のブログ
行列における全射,左零空間が零ベクトルのみ,行フルランクは同値であることを証明する - エンジニアを目指す浪人のブログ
グラム行列についての定理を証明する - エンジニアを目指す浪人のブログ
ムーア・ペンローズ逆行列の定義,構成,一意性についてまとめる - エンジニアを目指す浪人のブログ
行列のランク落ち,列フルランク,行フルランク,フルランクそれぞれのときの4つの基本部分空間を図示する - エンジニアを目指す浪人のブログ
勉強を進めていて,最小ノルム解(least norm solutions)について知りました.応用でよく使われているようなので,その内容をまとめておくことにしました.Boyd and Vandenberghe(2018)の16章1,2,3節を参考にして,問題を設定し最小ノルム解を導出していきます.
=================================================================================
目次
0. 準備
1. 制約付き最小二乗問題としての最小ノルム問題
2. 解
2.1. KKT方程式
2.2. 最小ノルム解
[ 0. 準備 ]
記号を準備します.
単位行列
次元ベクトル ( )
次元ベクトル
行列
行列
次元ベクトル
次元ベクトル
正の実数
通常の内積 (性質は文献[2]にあります)
(ユークリッド)ノルム (性質は文献[3]にあります)
[ 1. 制約付き最小二乗問題としての最小ノルム問題 ]
最小ノルム問題のベースである制約付き最小二乗問題(constrained least squares problem)は,冒頭の過去記事(制約付き最小二乗法)にあるように以下です.
(1.0)
制約付き最小二乗問題(1.0)で として以下です.
(1.1)
これは連立一次方程式 をみたす最小のノルムをもつベクトルを探索する問題であり,最小ノルム問題(least norm problem)(minimum-norm problem)といいます.
冒頭の過去記事(制約付き最小二乗法)仮定.(0.1)(0.2)は以下となります.(1.4)は(任意の について)常に成り立ちます.
仮定.
(1.3) は線形独立な行をもつ.
(1.4) は線形独立な列をもつ.
さらに以下を仮定し以後 は行フルランクであるとします.冒頭の過去記事(行列における全射)も参考になります.
仮定.
(1.5) は横長の行列( )
[ 2. 解 ]
[ 2.1. KKT方程式 ]
冒頭の過去記事(制約付き最小二乗法)KKT方程式(2.1.1)は として以下です.この方程式をみたす解を とします.
(2.1.1)
同記事のただ一つの解(2.1.2)は同様に以下です.
(2.1.2)
[ 2.2. 最小ノルム解 ]
行列 について以下が成り立ちます. は の行です.
これはグラム行列であり,仮定.(1.3)と冒頭の過去記事(グラム行列)定理 7.2.10.(b)から は正定値したがって正則です.このことは後で用います.
(2.1.1)の上部の方程式について以下を得ます.
(※)
(2.1.1)の下部の方程式について以下を得ます.
(※)
仮定.(1.3)より は線形独立な列をもつので は正則
(2.1.1)の上部の方程式に戻って以下を得ます.
(※)
したがって(2.1.1)は以下で表されるただ一つの解をもちます.
(2.2.1)
仮定.より は行フルランクであることと冒頭の過去記事(ムーア・ペンローズ逆行列の定義)より行列 は行列 のムーア・ペンローズ逆行列(擬似逆行列)です.
(2.2.2)
(2.2.3)
は行フルランクなので,連立一次方程式 はあらゆる について無数の解をもちます.冒頭の過去記事(行列のランク落ち)にあります. は の右逆行列なので(2.2.3)は の無数にある解の一つであり,その(無数にある解の)中で最小のノルムをもつ解です.
=================================================================================
以上,最小ノルム解の基礎をまとめました.
参考文献
[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