極小範數解

本文的閱讀等級：中級

令 $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$ ，其中 $Q$ 是 $n\times m$ 階矩陣滿足 $Q^TQ=I_m$ ， $R$ 是 $m\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 偽逆矩陣”。

13 Responses to 極小範數解

GR says:

10/05/2014 at 5:21 pm

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

- ccjou says:
  
  10/05/2014 at 9:25 pm
  
  在多數文獻中， $A^T$ 或 $A'$ 表示轉置，而 $A^\ast$ 或 $A^H$ 表示共軛轉置。請參考下文：
  
  https://ccjou.wordpress.com/2013/02/27/%E8%BD%89%E7%BD%AE%E8%88%87%E5%85%B1%E8%BB%9B%E8%BD%89%E7%BD%AE/
  
  adjoint 的詳細討論請見下文：
  https://ccjou.wordpress.com/2011/06/27/%E7%B7%9A%E6%80%A7%E6%B3%9B%E5%87%BD%E8%88%87%E4%BC%B4%E9%9A%A8/
  
Tim Huang says:

02/03/2015 at 10:33 am

周老師你好，
幾個問題請教，
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嗎？

- ccjou says:
  
  02/03/2015 at 11:41 am
  
  1) 是的，如定理一所述，任一特解可唯一分解為 $\mathbf{x}=\mathbf{y}+\mathbf{z}$ ，其中 $\mathbf{y}\in C(A^T)$ 且 $\mathbf{z}\in N(A)$ 。但 $C(A^T)=N(A)^{\perp}$ ，正交補集之意，故 $\mathbf{y}$ 即是 $\mathbf{x}$ 至列空間 $C(A^T)$ 的正交投影。
  3) 是的，詳細請參閱
  https://ccjou.wordpress.com/2009/06/10/%E9%80%9A%E9%81%8E%E6%8E%A8%E5%B0%8E%E5%81%BD%E9%80%86%E7%9F%A9%E9%99%A3%E8%AA%8D%E8%AD%98%E7%B7%9A%E6%80%A7%E4%BB%A3%E6%95%B8%E7%9A%84%E6%B7%B1%E5%B1%A4%E7%B5%90%E6%A7%8B/
  
  - Tim Huang says:
    
    02/03/2015 at 1:06 pm
    
    老師你好，
    我已經閱讀完並大致了解pseudoinverse了，但這要先求A的SVD，然後再做矩陣的相乘才能求得minimal solution，計算量也蠻大的。
    為甚麼不直接找row space 的一組orthonormal basis 然後再算特解X在 A之row space上的正交投影向量就可以求得minimum norm least square solution ，這樣計算量感覺比較不那麼複雜？
    謝謝了！
    
    - ccjou says:
      
      02/03/2015 at 1:17 pm
      
      SVD是穩定的數值算法，手算自然複雜。求極小範數解有很多方法，請參見下文：
      https://ccjou.wordpress.com/2014/06/23/%E6%AF%8F%E9%80%B1%E5%95%8F%E9%A1%8C-june-23-2014/
      
      - 曾中奕 says:
        
        06/19/2020 at 1:27 am
        
        老師請問你定理二的最後一句話等號發生在z=0故得證是什麼意思謝謝
        
Tim Huang says:

02/03/2015 at 10:38 am

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

yufenglyu says:

11/07/2016 at 9:00 pm

正文第二行开始的地方， $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 says:
  
  11/07/2016 at 9:11 pm
  
  這裡 $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$ 的線性映射。
  
Murphy says:

07/10/2017 at 6:55 am

你好，我在用Lagrange 乘数求解一个类似的问题，约束条件也是一个方程组 AX = b, 我的目标是最大化解的信息熵。但最后会有无穷多解，请问为什么会出现这样的情况？

- ccjou says:
  
  07/13/2017 at 2:18 pm
  
  $AA^T$ 是可逆的嗎？
  
曾中奕 says:

06/19/2020 at 1:29 am

老師請問你定理二的最後一句話等號發生在z=0故得證是什麼意思謝謝

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨