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

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

多目的最小二乗法の基礎をまとめる

数学 数理最適化

本記事は以下の過去記事で得た結果を用います．

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

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


勉強を進めていて，多目的最小二乗法(multi-objective least squares method)(重み付き最小二乗法(weighted least squares method))について知りました．応用でよく使われているようなので，その内容をまとめておくことにしました．Boyd and Vandenberghe(2018)の15章1節をベースにしています．

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

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. 多目的最小二乗法
{\displaystyle \;\;\; } 1.1. 多目的最小二乗問題とただ一つの解
{\displaystyle \;\;\; } 1.2. スタックド行列の列の線形独立性


[ 0. 準備 ]

記号を準備します．

{\displaystyle \;\;\; I \;\;\;\;\;\;\;\;\;\; } {\displaystyle n \times n } 単位行列
{\displaystyle \;\;\; x \;\;\;\;\;\;\;\;\;\; } {\displaystyle n } 次元ベクトル
{\displaystyle \;\;\; \hat{x} \;\;\;\;\;\;\;\;\;\; } {\displaystyle n } 次元ベクトル
{\displaystyle \;\;\; A_1,\ldots, A_k \;\;\;\;\;\;\;\; } {\displaystyle m_1 \times n } 行列{\displaystyle , \ldots,m_k \times n } 行列 {\displaystyle \;\;\; (m_1 + \cdots + m_k = m) }
{\displaystyle \;\;\; b_1,\ldots, b_k \;\;\;\;\;\;\;\;\;\; } {\displaystyle m_1 \times 1 } ベクトル{\displaystyle , \ldots,m_k \times 1 } ベクトル

{\displaystyle \;\;\; \lambda_1, \ \ldots, \lambda_k \;\;\;\;\;\;\;\;\;\; } 正の実数


{\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]にあります)


以下を準備します．

(0.1){\displaystyle \;\;\; \tilde{A} = \begin{bmatrix} \sqrt{\lambda_1} A_1 \\ \vdots \\ \sqrt{\lambda_k} A_k \end{bmatrix} \;\;\;\;\; (m \times n) }

(0.2){\displaystyle \;\;\; \tilde{b} = \begin{bmatrix} \sqrt{\lambda_1} b_1 \\ \vdots \\ \sqrt{\lambda_k} b_k \end{bmatrix} \;\;\;\;\;\;\; ( m \times 1) }

(0.3){\displaystyle \;\;\; \tilde{A}^T \tilde{A} = \begin{bmatrix} \sqrt{\lambda_1} A_1^T & \cdots & \sqrt{\lambda_k} A_k^T \end{bmatrix} \begin{bmatrix} \sqrt{\lambda_1} A_1 \\ \vdots \\ \sqrt{\lambda_k} A_k \end{bmatrix} \;\;\;\;\; (n \times m) \times (m \times n) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \lambda_1 A_1^T A_1 + \cdots + \lambda_k A_k^T A_k \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (n \times n) }

(0.4){\displaystyle \;\;\; \tilde{A}^T \tilde{b} = \begin{bmatrix} \sqrt{\lambda_1} A_1^T & \cdots & \sqrt{\lambda_k} A_k^T \end{bmatrix} \begin{bmatrix} \sqrt{\lambda_1} b_1 \\ \vdots \\ \sqrt{\lambda_k} b_k \end{bmatrix} \;\;\;\;\;\;\; (n \times m) \times (m \times 1) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \lambda_1 A_1^T b_1 + \cdots + \lambda_k A_k^T b_k \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (n \times 1) }


(0.1)の {\displaystyle \tilde{A} } はスタックド行列(stacked matrix)といいます．

(0.3)の {\displaystyle \tilde{G} \ (= \tilde{A}^T \tilde{A} )} は重み付きグラム行列(weighted gram matrix)といい，これ自体冒頭の過去記事(グラム行列)にあるグラム行列です．{\displaystyle A_1^T A_1,\ldots, A_k^T A_k } もグラム行列です．


本記事では以下を仮定します．

仮定.
(0.1) {\displaystyle \; \tilde{A} } は縦長の行列( {\displaystyle \Leftrightarrow [ \ m_1 + \cdots + m_k = m \gt n \ ] } )
(0.2) {\displaystyle \; \mathrm{rank}\ \tilde{A} = n \; } ( {\displaystyle \Leftrightarrow \tilde{A} } の列 {\displaystyle \tilde{a}_1,\ldots,\tilde{a}_n } は線形独立)

これは列フルランクであることと同値です．



[ 1. 多目的最小二乗法 ]
[ 1.1. 多目的最小二乗問題とただ一つの解 ]

多目的最小二乗問題のベースである最小二乗問題(least squares problem)は，目的関数 {\displaystyle \left\| Ax - b \right\|^2 } を最小にする {\displaystyle \hat{x} } を探索する問題です．冒頭の過去記事(最小二乗法)にあります．

以下の複数の目的関数を考えます．

{\displaystyle \;\;\; J_1 = \left\| A_1 x - b_1 \right\|^2, \;\;\; \ldots \;\;\; , \;\;\; J_k = \left\| A_k x - b_k \right\|^2 }

これらのすべてを可能な範囲で小さくする {\displaystyle \hat{x} } を探索するとします．そのために以下の加重和目的関数(weighted sum objective)を考えます．{\displaystyle \lambda_1, \ldots , \lambda_k } は(正の)重みです．

(1.0){\displaystyle \;\;\; J = \lambda_1 J_1 + \cdots + \lambda_k J_k }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \lambda_1 \left\| A_1 x - b_1 \right\|^2 + \; \cdots \; + \lambda_k \left\| A_k x - b_k \right\|^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \left\| \sqrt{\lambda_1} (A_1 x - b_1) \right\|^2 + \; \cdots \; + \left\| \sqrt{\lambda_k} ( A_k x - b_k ) \right\|^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \left\| \begin{bmatrix} \sqrt{\lambda_1}(A_1 x - b_1) \\ \vdots \\ \sqrt{\lambda_k}(A_k x - b_k) \end{bmatrix} \right\|^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \left\| \begin{bmatrix} \sqrt{\lambda_1} A_1 \\ \vdots \\ \sqrt{\lambda_k} A_k \end{bmatrix} x - \begin{bmatrix} \sqrt{\lambda_1} b_1 \\ \vdots \\ \sqrt{\lambda_k} b_k \end{bmatrix} \right\|^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \left\| \tilde{A} x - \tilde{b} \right\|^2 }


この {\displaystyle J } を最小にする {\displaystyle \hat{x} } を探索する問題を多目的最小二乗問題(multi-objective least squares problem)といい，以下のように定式化します．

(1.1){\displaystyle \;\;\; \mathrm{minimize} \;\;\;\; \left\| \tilde{A}x - b \right\|^2 }

この問題は仮定.より冒頭の過去記事(最小二乗法)の最小二乗問題(1.1)に帰着でき，ただ一つの解は同記事の(2.1.3)と同様にして以下となります．

(1.2)
{\displaystyle \; \hat{x} = ( \tilde{A}^T \tilde{A} )^{-1} \tilde{A}^T \tilde{b} }
{\displaystyle \;\;\;\; = ( \lambda_1 A_1^T A_1 + \cdots + \lambda_k A_k^T A_k )^{-1} (\lambda_1 A_1^T b_1 + \cdots + \lambda_k A_k^T b_k) \;\;\;\; \because } (0.3)(0.4)


[ 1.2. スタックド行列の列の線形独立性 ]

{\displaystyle \tilde{A} } が線形独立な列をもつことと，{\displaystyle A_1,\ldots, A_k } のそれぞれが線形独立な列をもつことは同値ではありません．仮定.(0.2)に関連して以下の事実が成り立ちます．

事実.
{\displaystyle A_1,\ldots, A_k } のうち少なくとも一つ(それは縦長の行列でなければならない)が線形独立な列をもつ，あるいは同じことであるがいずれかの {\displaystyle i \ (=1,\ldots,k) } について {\displaystyle A_i x=0 } をみたす零ベクトルでない {\displaystyle x } が存在しないとき，重み付きグラム行列 {\displaystyle \tilde{G} } は正則である．またこのとき {\displaystyle \tilde{A} } は線形独立な列をもつ．

証明.
冒頭の過去記事(グラム行列)定理 7.2.10.(a)より，重み付きグラム行列(0.3)の {\displaystyle A_1^T A_1,\ldots, A_k^T A_k } は半正定値である．いま {\displaystyle i = I } について {\displaystyle A_I } が線形独立な列をもつとすると，同記事定理 7.2.10.(b)より {\displaystyle A_I^T A_I } は正定値である．したがって {\displaystyle i=1,\ldots, k } のとき {\displaystyle x^T A_i^T A_i x \ge 0 } であり {\displaystyle i=I } のとき {\displaystyle x^T A_I^T A_I x \gt 0 } である．これらを用いると以下を得る．

{\displaystyle \;\;\; x^T \tilde{G} x = x^T \tilde{A}^T \tilde{A} x }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = x^T (\lambda_1 A_1^T A_1 + \cdots + \lambda_k A_k^T A_k ) x }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \lambda_1 x^T A_1^T A_1 x + \cdots + \lambda_k x^T A_k^T A_k x^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \lambda_1 x^T A_1^T A_1 x + \cdots + \lambda_I x^T A_I^T A_I x + \cdots + \lambda_k x^T A_k^T A_k x^T }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; \gt 0 }

したがって {\displaystyle \tilde{G} } は正定値であり，よって正則である．さらに同記事定理 7.2.10.(b)より {\displaystyle \tilde{a}_1,\ldots,\tilde{a}_n } は線形独立である．(証明終わり)

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

以上，多目的最小二乗法の基礎をまとめました．



参考文献
[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

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