最小平方法 1

給定一個矩陣 $A$ 以及一個向量 $b$, 我們想要找到一個向量 $x$ 使得 $\|Ax - b\|^2$ 最小.

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

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

$$ \newcommand{\argmin}{\arg\min} \tag{1} \hat{x} = \argmin_{x\in\mathbb{R}^n}\|Ax - b\|^2. $$

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, \quad Q^TQ = I, $$ 但是 $Q$ 不是個方陣, $N(R^T)=\{0\}$.

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

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

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

給定 $A$ 與 $b$

• 找到一個向量 $\hat{x}\in\mathbb{R}^n$, 使得 $\|A\hat{x}-b\|^2$ 最小.
• 找到一個向量 $\hat{b}\in C(A)\subseteq\mathbb{R}^m$, 使得 $\|\hat{b}-b\|^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)$ 的投影向量, $$ \tag{2} \hat{b} = \arg\min_{\hat{b}\in\mathbb{R}^m}\|\hat{b}-b\|^2. $$

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)$.

$$ \tag{3} \begin{align} \|p - b\|^2 &= <p-b, p-b> \\
&= <\hat{b} + e - b, \hat{b} + e - b>\\
&= \|\hat{b} - b\|^2 + 2<\hat{b} - b, e> + \|e\|^2\\
&= \|\hat{b} - b\|^2 + \|e\|^2, \end{align} $$

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)$, $\|p - b\|^2 \ge \|\hat{b} - b\|^2$, and the minimal of $\|p - b\|^2$ occurs when $\|e\|^2=0$, that is when $p=\hat{b}$.

由這 lemma 我們知道 $\hat{b}$ 可以從 $(\hat{b}-b)\perp C(A)$ 這個條件下手, 也就是要找一個 $\hat{b}$ 滿足

$$ \tag{4} A^T(\hat{b}-b)=0. $$

那因為 $\hat{b}\in C(A)$, 一定存在某個 $\hat{x}\in\mathbb{R}^n$ 使得 $A\hat{x}=\hat{b}$. 因此 (4) 就變成

$$ \tag{5} A^T(A\hat{x}-b)=0. $$

展開就知道 $\hat{x}$ 要滿足

$$ \tag{6} A^TA\hat{x}=A^Tb. $$

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

• 找到一個向量 $\hat{x}\subseteq\mathbb{R}^n$, 使得 $\|A\hat{x}-b\|^2$ 最小.
  • $\hat{x}$ 滿足 $A^TA\hat{x}=A^Tb$.
• 找到一個向量 $\hat{b}\in C(A)\subseteq\mathbb{R}^m$, 使得 $\|\hat{b}-b\|^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^TA$ 就可逆, 然後我們就可以把 $\hat{x}$ 顯式的寫下來, 就得到 $$ \tag{7} \hat{x} = (A^TA)^{-1}A^Tb. $$ 在這情況下, $b$ 在 $C(A)$ 的投影也可以寫下來, 就是 $$ \tag{8} \hat{b} = A(A^TA)^{-1}A^Tb. $$ 或是我們可以更近一步定義投影到 $C(A)$ 的投影矩陣, 就是 $$ \tag{9} P = A(A^TA)^{-1}A^T. $$

4. Dependent columns

$A^TA$ 不可逆

Case 1

假設 $m<n$ 並且 $\text{rank}(A)=n$.

在這情況下, $A$ 的 columns 不是 linearly independent, $A^TA$ 不可逆, 並且 $N(A)\ne{0}$. 所以若有一個最小平方解, 那就還會有無窮多個. 不過我們至少先找到一個再說.

因為 $A$ 的 rows 會線性獨立, 因此我們對 $A^T$ 做 (reduced) QR 分解得到

$$ \tag{10} A^T = QR, $$ where $Q^TQ= I$, $Q\in M_{n\times m}$ and $R\in M_{m\times m}$. 並且我們知道 $R$ 是可逆矩陣.

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

$$ \tag{11} QRR^TQ^T \hat{x} = QRb. $$

兩邊同乘 $(R^T)^{-1}R^{-1}Q^T$ 我們得到

$$ \tag{12} Q^T \hat{x} = (R^T)^{-1}b. $$

最後, 如果我們選擇

$$ \tag{13} \hat{x} = Q(R^T)^{-1}b, $$

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

Case 2

假設 $\text{rank}(A)=r$, 並且 $r<m$, $r<n$.

我們對 $A$ 做 (reduced) QR 分解得到

$$ \tag{14} A = QR, $$ where $Q^TQ= I$, $Q\in M_{m\times r}$ and $R\in M_{r\times n}$.

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

$$ \tag{15} R^TR \hat{x} = R^TQ^Tb. $$

不過要注意的是這裡 $R^TR\in M_{n\times n}$ 不是一個可逆矩陣, 所以操作上無法兩邊同乘其反矩陣. 但是好消息是 $R^T$ 的 columns 是線性獨立的, 所以我們會有

$$ \tag{16} R \hat{x} = Q^Tb. $$

接著我們試著在 row space 裡找解. 假設 $\hat{x} = R^T \hat{y}$, $\hat{y}\in\mathbb{R}^r$, 那 (16) 可以改寫為

$$ \tag{17} RR^T \hat{y} = Q^Tb. $$

這樣, 由於 $RR^T\in M_{r\times r}$ 並且可逆, 我們就有 $\hat{y} = (RR^T)^{-1}Q^Tb$. 最後

$$ \tag{18} \hat{x} = R^T(RR^T)^{-1}Q^Tb. $$

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

Remark: QR 的這整套做法也適用於 $A$ 的 columns 線性獨立的情形. 而且在這情形之下的 $R$ 矩陣會是個可逆方陣, 因此有 $(RR^T)^{-1} = (R^T)^{-1}R^{-1}$. 代入之後得到

$$ \tag{19} \hat{x} = R^{-1}Q^Tb. $$

5. Conclusion

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

$$ \min_{x\in\mathbb{R}^n}|Ax - b|^2. $$

並且我們令最佳解為 $\hat{x}$.

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

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

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