極小範數解

本文的閱讀等級:中級

A 為一個 m\times n 階實矩陣,C(A) 代表 A 的行空間 (column space,值域),即 C(A)=\{A\mathbf{x}\vert\mathbf{x}\in\mathbb{R}^n\}。對於任一 \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,見“線性代數基本定理 (二)”),因此 n 維特解 \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 mAA^T 是可逆矩陣,故 \mathbf{c}=(AA^T)^{-1}\mathbf{b},即得 \mathbf{x}^+=A^T(AA^T)^{-1}\mathbf{b}

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

\displaystyle \min_{A\mathbf{x}=\mathbf{b}}\Vert\mathbf{x}\Vert

注意,最小化 \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}-2\boldsymbol{\lambda}^T(A\mathbf{x}-\mathbf{b})

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

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

令上面兩式為零,最佳解 \mathbf{x}^+ 滿足 A\mathbf{x}^+=\mathbf{b}A^T\boldsymbol{\lambda}=\mathbf{x}^+。第二式左乘 AAA^T\boldsymbol{\lambda}=A\mathbf{x}^+=\mathbf{b},解出 \boldsymbol{\lambda}=(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}

  
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 偽逆矩陣”。

This entry was posted in 線性代數專欄, 內積空間 and tagged , , , . Bookmark the permalink.

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