極小範數解

本文的閱讀等級:中級

A 為一個 m\times n 階實矩陣。我們用 C(A) 代表 A 的行空間 (值域,column space),即 C(A)=\{A\mathbf{x}\vert\mathbf{x}\in\mathbb{R}^n\}。請注意,C(A)\mathbb{R}^m 的一個子空間。對於任一 \mathbf{b}\in C(A),線性方程 A\mathbf{x}=\mathbf{b} 必定有解。在解集合中,有一個解最為特別,該特解位於 A 的列空間 (row space),即 A^T 的行空間 C(A^T),並具有最小的2-範數 (歐氏範數,見“向量範數”),稱為極小範數解 (minimum norm solution),記為 \mathbf{x}^{+}。這篇短文介紹極小範數解的性質與表達式。

 
定理一:若 \mathbf{b}\in C(A),則存在唯一的 \mathbf{y}\in C(A^T) 使得 A\mathbf{y}=\mathbf{b}

\mathbf{x}\in\mathbb{R}^n 使得 A\mathbf{x}=\mathbf{b}。在 \mathbb{R}^n 中,矩陣 A 的列空間 C(A^T) 是零空間 (nullspace) N(A) 的正交補餘 (orthogonal complement,見“線性代數基本定理 (二)”),特解 \mathbf{x} 可唯一分解為 \mathbf{x}=\mathbf{y}+\mathbf{z},其中 \mathbf{y}\in C(A^T)\mathbf{z}\in N(A)。證明於下:將分解式代入線性方程,

\displaystyle  A\mathbf{x}=A(\mathbf{y}+\mathbf{z})=A\mathbf{y}+A\mathbf{z}=A\mathbf{y}=\mathbf{b}

可知 \mathbf{y} 也是一個特解。接著證明唯一性,假設 \mathbf{y},\mathbf{y}'\in C(A^T) 使得 A\mathbf{y}=\mathbf{b}A\mathbf{y}'=\mathbf{b}。令兩式相減,可得 A(\mathbf{y}-\mathbf{y}')=\mathbf{0},說明 (\mathbf{y}-\mathbf{y}')\in N(A)。然而,\mathbf{y}\mathbf{y}' 的任意線性組合必仍在列空間內,(\mathbf{y}-\mathbf{y}')\in C(A^T)。合併以上結果,(\mathbf{y}-\mathbf{y}')\in N(A)\cap C(A^T)=\{\mathbf{0}\},推得 \mathbf{y}=\mathbf{y}'

 
定理二:若 \mathbf{b}\in C(A)\mathbf{y}\in\{\mathbf{x}\vert A\mathbf{x}=\mathbf{b}\} 具有最小2-範數,則 \mathbf{y}\in C(A^T)

定理一表明任一特解皆可表示為 \mathbf{x}=\mathbf{y}+\mathbf{z},其中 \mathbf{y}\in C(A^T)\mathbf{z}\in N(A),且 \mathbf{y} 唯一存在。因為 \mathbf{y}\perp\mathbf{z},畢氏定理說 \Vert\mathbf{x}\Vert^2=\Vert\mathbf{y}\Vert^2+\Vert\mathbf{z}\Vert^2\ge \Vert\mathbf{y}\Vert^2,等號發生於 \mathbf{z}=\mathbf{0},故得證。

 
根據定理一與定理二,對於每一 \mathbf{b}\in C(A),我們定義極小範數解為 \mathbf{x}^+\in C(A^T) 使得 A\mathbf{x}^+=\mathbf{b}。接下來討論極小範數解 \mathbf{x}^+ 的表達式。

 
定理三:若 \text{rank}A=m,即 A 有線性獨立的列,則 A\mathbf{x}=\mathbf{b} 必然有解,且極小範數解為

\displaystyle  \mathbf{x}^+=A^T(AA^T)^{-1}\mathbf{b}

\text{rank}A=m,則 \dim C(A)=m,行空間 C(A) 充滿 \mathbb{R}^m,這意味任一 \mathbf{b}\in\mathbb{R}^m 皆使 A\mathbf{x}=\mathbf{b} 有解。下面解說兩個推導極小範數解的方法。第一個方法採用向量空間分析。因為 A 有線性獨立的列,極小範數解 \mathbf{x}^+\in C(A^T) 可唯一表示為 A 的列向量的線性組合,即存在唯一的 \mathbf{c} 使得 \mathbf{x}^+=A^T\mathbf{c}。將上式代入 A\mathbf{x}^+=\mathbf{b},就有 AA^T\mathbf{c}=\mathbf{b}。因為 \text{rank}(AA^T)=\text{rank}A=m (見“利用 Gramian 矩陣證明行秩等於列秩”),推論 m\times m 階 Gramian 矩陣 AA^T 是可逆的,故 \mathbf{c}=(AA^T)^{-1}\mathbf{b},即得 \mathbf{x}^+=A^T(AA^T)^{-1}\mathbf{b}

  
第二個方法運用約束優化 (constrained optimization) 技巧。考慮這個問題

\displaystyle  \begin{array}{ll}  \hbox{minimize}&\Vert\mathbf{x}\Vert\\  \hbox{subject to}&A\mathbf{x}=\mathbf{b}.  \end{array}

請注意,最小化 \Vert\mathbf{x}\Vert 等價於最小化 \Vert\mathbf{x}\Vert^2=\mathbf{x}^T\mathbf{x}。使用 Lagrange 乘數法 (見“Lagrange 乘數法”),寫出 Lagrangian 函數

\displaystyle  L(\mathbf{x},\boldsymbol{\lambda})=\mathbf{x}^T\mathbf{x}+\boldsymbol{\lambda}^T(A\mathbf{x}-\mathbf{b})

其中 \boldsymbol{\lambda}m 維 Lagrange 乘數向量。計算偏導數 (見“矩陣導數”,SV-9,SV-11),

\displaystyle\begin{aligned}  \frac{\partial L}{\partial\mathbf{x}}&=2\mathbf{x}+A^T\boldsymbol{\lambda}\\  \frac{\partial L}{\partial\boldsymbol{\lambda}}&=A\mathbf{x}-\mathbf{b}.  \end{aligned}

令上面兩式為零得到最佳條件式。將 \mathbf{x}^+=-\frac{1}{2}A^T\boldsymbol{\lambda} 代入 A\mathbf{x}^+=\mathbf{b},可得 -\frac{1}{2}AA^T\boldsymbol{\lambda}=\mathbf{b},解出 \boldsymbol{\lambda}=-2(AA^T)^{-1}\mathbf{b},因此 \mathbf{x}^+=A^T(AA^T)^{-1}\mathbf{b}

 
在數值計算時,我們可以採用 QR 分解 (見“線代膠囊──QR 分解”)。設 A^T=QR,其中 Qn\times m 階矩陣滿足 Q^TQ=I_mRm\times m 階上三角矩陣。因此,

\displaystyle\begin{aligned}  \mathbf{x}^+&=A^T(AA^T)^{-1}\mathbf{b}=QR(R^TQ^TQR)^{-1}\mathbf{b}\\  &=QR(R^TR)^{-1}\mathbf{b}=QRR^{-1}(R^T)^{-1}\mathbf{b}\\  &=Q(R^T)^{-1}\mathbf{b}.  \end{aligned}

所求的最佳值為

\displaystyle  \begin{aligned}  \Vert\mathbf{x}^+\Vert^2&=\left(A^T(AA^T)^{-1}\mathbf{b}\right)^T\left(A^T(AA^T)^{-1}\mathbf{b}\right)\\  &=\mathbf{b}^T(AA^T)^{-1}\mathbf{b}\\  &=\mathbf{b}^T(R^TR)^{-1}\mathbf{b}.  \end{aligned}

  
A 有線性相關的列,即 \text{rank}A<m,這時 AA^T 是不可逆的,定理三給出的表達式不成立。對於 \mathbf{b}\in C(A),線性方程 A\mathbf{x}=\mathbf{b} 仍存在極小範數解 \mathbf{x}^+=A^+\mathbf{b},其中 A^+ 稱為 A 的 Moore-Penrose 偽逆矩陣 (pseudoinverse)。欲深入了解這個主題的讀者,請參閱
偽逆矩陣與轉置矩陣的二三事” (見Q7) 和“Moore-Penrose 偽逆矩陣”。

Advertisements
本篇發表於 線性代數專欄, 內積空間 並標籤為 , , , 。將永久鏈結加入書籤。

9 則回應給 極小範數解

  1. GR 說道:

    老师您好,请问A^T是不是A的转置?我看有的文章上说是共轭转置,还有的是说共轭算子,这很让我困惑。这究竟是怎么回事呢?Hermitian adjoint operator应该如何求呢?能否给些启发,或是相关资料的链接,谢谢您

  2. Tim Huang 說道:

    周老師你好,
    幾個問題請教,
    1.這個極小範數解會是特解 X 在列空間的正交投影向量嗎?
    2. 定理三中若A沒有full row rank 的話要怎麼解呢?
    3. 若是在求 Ax=b 且 b不在C(A)中的minimum 2-norm least square approximation,是要先把b做
    正交投影到C(A) (令這向量為c ) 然後再解Ax=c的minimum 2-norm solution嗎?

  3. Tim Huang 說道:

    剛剛沒看完 , 第二個問題我會去參考pseudoinverse的資料
    謝謝!

  4. yufenglyu 說道:

    正文第二行开始的地方,C(A)=\{A\mathbf{x}\vert\mathbf{x}\in\mathbb{R}^n\} 应该是 C(A)=\{A\mathbf{x}\vert\mathbf{x}\in\mathbb{R}^m\}

    • ccjou 說道:

      這裡 A 是一個 m\times n 階矩陣,\mathbf{x} 必須是 n 維向量 (即 n\times 1 階矩陣) 才能算得 A\mathbf{x}。因此,\mathbf{x}\in\mathbb{R}^n,而 A\mathbf{x}\in\mathbb{R}^m,故 C(A)\mathbb{R}^m 的一個子空間。你可以將 A 視為一個從 \mathbb{R}^n 映至 \mathbb{R}^m 的線性映射。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s