最小平方法

給定一個矩陣

$A$ 以及一個向量

$b$, 我們想要找到一個向量

$x$ 使得

$\Vert Ax-b{\Vert }^2$ 最小.

$$A\in M_{m\times n},b\in M_{m\times 1},x\in M_{n\times 1}.$$

首先我們定義

$\hat{x}$ 為找到的那個解, 也就是說, 我們要解以下這個問題

$$\begin{array}{}\text{(1)}& \hat{x}=\arg \underset{x\in {\mathbb{R}}^n}{min}\Vert Ax-b{\Vert }^2.\end{array}$$

1. Notations

• $C(A)$: column space of
  $A$.
  
  $$C(A)=\{Ax|x\in {\mathbb{R}}^n\}\subseteq {\mathbb{R}}^m.$$
• $N(A)$: null space of
  $A$.
  
  $$N(A)=\{x\in {\mathbb{R}}^n|Ax=0\}\subseteq {\mathbb{R}}^n.$$
• Reduced QR for
  $A$.
  
  $$A=QR,Q^{T}Q=I,$$
  但是
  $Q$ 不是個方陣,
  $N(R^T)=\{0\}$.

2. 最小平方解與投影子空間

要找到最小平方解首先我們做個重要的觀察.

事實上, 以下三件事是等價敘述:

給定

$A$ 與

$b$

• 找到一個向量
  $\hat{x}\in {\mathbb{R}}^n$, 使得
  $\Vert A\hat{x}-b{\Vert }^2$ 最小.
• 找到一個向量
  $\hat{b}\in C(A)\subseteq {\mathbb{R}}^m$, 使得
  $\Vert \hat{b}-b{\Vert }^2$ 最小.
• 將
  $b$ 投影到
  $C(A)$.

因為

$A\hat{x}$ 可以視為

$A$ 的 columns 的線性組合. 而任何在 column space

$C(A)$ 裡的向量也都可以被寫成

$Ax$.

所以若我們知道怎樣解其中一個, 另外兩個問題就同時解出來了. 我們先證明以下這個 lemma.

Lemma

任意給定一個向量

$b\in {\mathbb{R}}^m$, 如果我們能夠找到一個向量

$\hat{b}\in {\mathbb{R}}^m$ 滿足

$(\hat{b}-b)\perp C(A)$, 那這個向量就會是

$b$ 在

$C(A)$ 的投影向量,

$$\begin{array}{}\text{(2)}& \hat{b}=\arg \underset{\hat{b}\in {\mathbb{R}}^m}{min}\Vert \hat{b}-b{\Vert }^2.\end{array}$$

pf:

Let

$\hat{b}\in C(A)\subseteq {\mathbb{R}}^m$ such that

$(\hat{b}-b)\perp C(A)$.

Given

$p\in C(A)$, we define

$e=p-\hat{b}$ and we have

$e\in C(A)$.

$$\begin{array}{}\text{(3)}& \begin{array}{rl}\Vert p-b{\Vert }^2& =<p-b,p-b>\\ & =<\hat{b}+e-b,\hat{b}+e-b>\\ & =\Vert \hat{b}-b{\Vert }^2+2<\hat{b}-b,e>+\Vert e{\Vert }^2\\ & =\Vert \hat{b}-b{\Vert }^2+\Vert e{\Vert }^2,\end{array}\end{array}$$

where we have used the fact that

$(\hat{b}-b)\perp C(A)$ and

$e\in C(A)$, so that

$<\hat{b}-b,e>=0$.

Therefore, for any

$p\in C(A)$,

$\Vert p-b{\Vert }^2\ge \Vert \hat{b}-b{\Vert }^2$, and the minimal of

$\Vert p-b{\Vert }^2$ occurs when

$\Vert e{\Vert }^2=0$, that is when

$p=\hat{b}$.

由這 lemma 我們知道

$\hat{b}$ 可以從

$(\hat{b}-b)\perp C(A)$ 這個條件下手, 也就是要找一個

$\hat{b}$ 滿足

$$\begin{array}{}\text{(4)}& A^T(\hat{b}-b)=0.\end{array}$$

那因為

$\hat{b}\in C(A)$, 一定存在某個

$\hat{x}\in {\mathbb{R}}^n$ 使得

$A\hat{x}=\hat{b}$. 因此 (4) 就變成

$$\begin{array}{}\text{(5)}& A^T(A\hat{x}-b)=0.\end{array}$$

展開就知道

$\hat{x}$ 要滿足

$$\begin{array}{}\text{(6)}& A^{T}A\hat{x}=A^{T}b.\end{array}$$

因此, 我們剛剛說的事其解就是:

• 找到一個向量
  $\hat{x}\subseteq {\mathbb{R}}^n$, 使得
  $\Vert A\hat{x}-b{\Vert }^2$ 最小.
  • $\hat{x}$ 滿足
    $A^{T}A\hat{x}=A^{T}b$.
• 找到一個向量
  $\hat{b}\in C(A)\subseteq {\mathbb{R}}^m$, 使得
  $\Vert \hat{b}-b{\Vert }^2$ 最小.
  • $\hat{b}$ 滿足
    $(\hat{b}-b)\perp C(A)$, 或是
    $A^T(\hat{b}-b)=0$.

Remark:

1. 以上推導都是充分條件, 就是如果我們解出 (4) 或 (6), 那他們就一定是 (1) 的解.
2. 以上推導跟
   $A$ 的 column 有沒有 linearly independent 無關.

3. Independent columns

如果

$A$ 的 column 是 linearly independent, 那

$A^{T}A$ 就可逆, 然後我們就可以把

$\hat{x}$ 顯式的寫下來, 就得到

$$\begin{array}{}\text{(7)}& \hat{x}=(A^{T}A{)}^{-1}{A}^{T}b.\end{array}$$

在這情況下,

$b$ 在

$C(A)$ 的投影也可以寫下來, 就是

$$\begin{array}{}\text{(8)}& \hat{b}=A(A^{T}A{)}^{-1}{A}^{T}b.\end{array}$$

或是我們可以更近一步定義投影到

$C(A)$ 的投影矩陣, 就是

$$\begin{array}{}\text{(9)}& P=A(A^{T}A{)}^{-1}{A}^T.\end{array}$$

4. Dependent columns

$A^{T}A$ 不可逆

Case 1

假設

$m<n$ 並且

$\text{rank}(A)=n$.

在這情況下,

$A$ 的 columns 不是 linearly independent,

$A^{T}A$ 不可逆, 並且

$N(A)\ne \{0\}$. 所以若有一個最小平方解, 那就還會有無窮多個. 不過我們至少先找到一個再說.

因為

$A$ 的 rows 會線性獨立, 因此我們對

$A^T$ 做 (reduced) QR 分解得到

$$\begin{array}{}\text{(10)}& A^T=QR,\end{array}$$

where

$Q^{T}Q=I_{m\times m}$,

$Q\in M_{n\times m}$ and

$R\in M_{m\times m}$. 並且我們知道

$R$ 是可逆矩陣.

接著我們知道最小平方解必須滿足 (6), 也就是

$$\begin{array}{}\text{(11)}& QR{R}^T{Q}^T\hat{x}=QRb.\end{array}$$

兩邊同乘

$(R^T{)}^{-1}{R}^{-1}{Q}^T$ 我們得到

$$\begin{array}{}\text{(12)}& Q^T\hat{x}=(R^T{)}^{-1}b.\end{array}$$

最後, 如果我們選擇

$$\begin{array}{}\text{(13)}& \hat{x}=Q(R^T{)}^{-1}b,\end{array}$$

那可以很容易驗證 (12) 是滿足的. 也就是說 (13) 會是這個問題的一個解.

Case 2

假設

$\text{rank}(A)=r$, 並且

$r<m$,

$r<n$.

我們對

$A$ 做 (reduced) QR 分解得到

$$\begin{array}{}\text{(14)}& A=QR,\end{array}$$
where

$Q^{T}Q=I_{r\times r}$,

$Q\in M_{m\times r}$ and

$R\in M_{r\times n}$.

接著我們知道最小平方解必須滿足 (6), 也就是

$$\begin{array}{}\text{(15)}& R^{T}R\hat{x}=R^T{Q}^{T}b.\end{array}$$

不過要注意的是這裡

$R^{T}R\in M_{n\times n}$ 不是一個可逆矩陣, 所以操作上無法兩邊同乘其反矩陣. 但是好消息是

$R^T$ 的 columns 是線性獨立的, 所以我們會有

$$\begin{array}{}\text{(16)}& R\hat{x}=Q^{T}b.\end{array}$$

接著我們試著在 row space 裡找解. 假設

$\hat{x}=R^T\hat{y}$,

$\hat{y}\in {\mathbb{R}}^r$, 那 (16) 可以改寫為

$$\begin{array}{}\text{(17)}& R{R}^T\hat{y}=Q^{T}b.\end{array}$$

這樣, 由於

$R{R}^T\in M_{r\times r}$ 並且可逆, 我們就有

$\hat{y}=(R{R}^T{)}^{-1}{Q}^{T}b$. 最後

$$\begin{array}{}\text{(18)}& \hat{x}=R^T(R{R}^T{)}^{-1}{Q}^{T}b.\end{array}$$

一樣可以很容易驗證 (16) 是滿足的. 也就是說 (18) 會是這個問題的一個解.

Remark: Case 2 的這整套 QR 做法也適用於

$A$ 的 columns 線性獨立的情形. 而且在這情形之下的

$R$ 矩陣會是個可逆方陣, 因此有

$(R{R}^T{)}^{-1}=(R^T{)}^{-1}{R}^{-1}$. 代入之後得到

$$\begin{array}{}\text{(19)}& \hat{x}=R^{-1}{Q}^{T}b.\end{array}$$

5. Conclusion

我們考慮以下最小平方法問題

$$\underset{x\in {\mathbb{R}}^n}{min}\Vert Ax-b{\Vert }^2.$$

並且我們令最佳解為

$\hat{x}$.

• 如果
  $A$ 的 columns 線性獨立
  
  $$\hat{x}=(A^{T}A{)}^{-1}{A}^{T}b.$$
  • 如果對
    $A$ 做 (reduced) QR,
    $A=QR$, 並且
    $Q^{T}Q=I_{n\times n}$,
    
    $$\hat{x}=R^{-1}{Q}^{T}b.$$
• 如果
  $A$ 的 columns 線性相依

  則有無窮多解, 以下是一特解 (並且是所有的解裡面長度最短的).

  • 對
    $A$ 做 (reduced) QR,
    $A=QR$, 並且
    $Q^{T}Q=I_{r\times r}$,
    
    $$\hat{x}=R^T(R{R}^T{)}^{-1}{Q}^{T}b.$$
  • 或是若
    $\text{rank}(A)=n$, 則可對
    $A^T$ 做 (reduced) QR,
    $A^T=QR$, 並且
    $Q^{T}Q=I_{m\times m}$,
    
    $$\hat{x}=Q(R^T{)}^{-1}b.$$