# 求 minimal sol / least squares sol

先上圖，懶得看英文可以直接看下面我的中文解釋再對照著看～


## minimal solution

如果 $A\vec{x} = \vec{b}$ 有很多解（即有很多個 $\vec{x}$ 滿足這這個式子）時，我們希望能找到這麼多解裡面長度最小的那個。

為什麼上面的圖中會寫如果 $\vec{b} \in CS(A)$，$A\vec{x} = \vec{b}$ 就有解呢？

> 因為如果 $\vec{b} \in CS(A)$，代表 $\vec{b}$ 可寫成 $A\vec{x}$ 的形式
> （因為 by definition， $CS(A)$ 就是收集所有可以寫成 $A\vec{x}$ 形式的向量）
> 因此也就代表說，存在一個 $\vec{x}$ 使 $A\vec{x} = \vec{b}$ 成立

現在我們假設滿足 $A\vec{x} = \vec{b}$ 的 $\vec{x}$ 可能不止一個，於是 minimal solution 就是在說，那就求一個滿足等式的 $\vec{x}$ 裡長度最小的那個吧！

那要怎麼找這個長度最小的 $\vec{x}$ 呢？
此 proposition 要告訴我們的就是：

這個長度最小的 $\vec{x}$ 就會恰好是某個在 $CS(A^T)$ 裡的向量

> 也可以說是在 $RS(A)$ 裡的，因為 $CS(A^T) = RS(A)$
> Why?
> 直觀的想法：你把 $A$ 取轉置之後，$A$ 的列變成行，行變成列，所以 $A^T$ 的行所生成的空間（$CS(A^T)$）也就是原本 $A$ 的列所生成的空間（$RS(A)$）

並且，在 $RS(A)$ 裡只會有一個 $\vec{x}$ （用 $\vec{x_0}$ 代表）會滿足 $A\vec{x} = \vec{b}$

#### 找 minimal solution 的方法

任找一個滿足 $A\vec{x} = \vec{b}$ 的 $\vec{x}$ ，再把這個 $\vec{x}$ 投影到列空間即可

==$x_0 = Proj_{C(A^T)}(x)$==

Gilbert Strang 書裡的圖比較方便想像：


> $\vec{x} = \vec{x_r} + \vec{x_n}$
> 是滿足 $A\vec{x} = \vec{b}$ 的其中一個解
> 但如果我們要求 minimal solution （所有解裡面長度最短的解），就是把 $\vec{x}$ 投影到 $RS(A) = C(A^T)$ 上，得到的 $\vec{x_r}$
>> 幫助想像，從圖上也可以看得出來 $\vec{x}$ 比 $\vec{x_r}$ 長

## least squares solution

如果 $A\vec{x} = \vec{b}$ 無解時，我們希望能找到一個 $\vec{x}$ ，使得 $A\vec{x}$ 和 $\vec{b}$ 最接近來當作一個近似解。

什麼時候 $A\vec{x} = \vec{b}$ 無解？
> $A\vec{x} = \vec{b}$ 無解代表說找不到一個 $\vec{x}$ 帶進去滿足這個式子，也就是說 $\vec{b}$ 沒辦法寫成 $A\vec{x}$ 的形式，既然如此，根據行空間 $CS(A)$ 的定義，要可以寫成 $A\vec{x}$ 的形式才會被收集到行空間中，因此 $\vec{b} \notin CS(A)$

> 如果 $A\vec{x} = \vec{b}$ 有解的時候，因為等號成立，所以我們可以把 $\vec{b}$ 搬到等號左側，變成 $A\vec{x} - \vec{b} = 0$
> 但是現在 $A\vec{x} = \vec{b}$ 無解，所以 $A\vec{x} - \vec{b} \not= 0$
> 既然不等於零，一定會有某一個 $\vec{x}$ 使得 $A\vec{x} - \vec{b}$ 最小，也就是說這個 $\vec{x}$ 讓 $A\vec{x}$ 和 $\vec{b}$ 最接近，我們用 $\vec{x^*}$ 來代表這個 $\vec{x}$
>
> 因為 $A\vec{x^*} - \vec{b}$ 是有方向性的，但我們在考慮它們要最接近的時候不用管到底是哪個方向，所以加上 norm：

least squares solution 即求：

\begin{equation}
\min ||\ A\vec{x^*} - \vec{b} \ ||
\end{equation}

這個圖很清晰的表示了找 least squares solution 件事：


> 綠色的點點是收集到的數據的值，當我們要找他們之間的關聯時，就想去畫一條線（回歸線 Regression Line）來描述這些點之間的關係，但是收集到的數據可能不會剛好都在這條直線上，所以我們畫出的線和實際的 observed value 之間會有誤差（Error）。
>
> 在求 least squares solution 的時候其實也是這個想法，這條線就是 $CS(A) = A\vec{x}$，也就是一個 $A \in F^{m \times n}$ 把所有 $\vec{x} \in F^{n \times 1}$ 送到的全部向量所成的空間，$\vec{b}$ 就是上面那些綠色的點（observed value），因為我們很難找到一個完美符合這些點的 regression line，在這樣的情況下，我們只好退而求其次找 error 最小的。

回到原本的問題，那我們如何求滿足 $\min ||A\vec{x^*} - \vec{b}||$ 的 $\vec{x^*}$？

### 找 least squares solution 的方法

#### 解 normal equation


我畫了一個簡單的圖說明 XD

從圖中我們可以看到黑色的向量 $\vec{b}$，以及一個紅色的向量 $A\vec{x^*}$ 在 $CS(A)$ 上，要找他們兩個之間最近的距離，很直觀的想法就是直接畫一條垂直線下來，這條線就是 $A\vec{x^*} - \vec{b}$

因為$A\vec{x^*} - \vec{b}$ 和 $CS(A)$ 垂直，所以 $A\vec{x^*} - \vec{b}$ 就會在 $CS(A)^\perp$，也就是 $CS(A)$ 的 orthogonal complement 中
> $CS(A)^\perp$：一個收集 和 「$CS(A)$ 裡所有向量」垂直的向量 的 subspace。

$CS(A)^\perp$ 又是什麼呢？
$\rightarrow$ 實際上就是 $N(A^T)$

不多說明直接上一個很好用的圖：


:::success
\begin{equation}
\begin{split}
N(A) = C(A^T)^\perp \\
N(A^T) = C(A)^\perp
\end{split}
\end{equation}
:::
> 詳細說明可參考 Gilbert Strang 的書，觀念寫超好，書的資訊附在下方 Reference。

所以也就是說 $A\vec{x^*} - \vec{b}$ 會在 $N(A^T)$ 中。

>根據 null space（也就是 kernel）的定義：
>
>$N(A)$ 會收集所有可以被 $A$ 送到 $\vec0$ 的 $\vec x$
>$\rightarrow$ $N(A^T)$ 會收集所有可以被 $A^T$ 送到 $\vec0$ 的 $\vec x$

既然 $A\vec{x^*} - \vec{b}$ 在 $N(A^T)$ 中，代表 $A^T$ 也會把 $A\vec{x^*} - \vec{b}$ 送到 $\vec0$，於是我們得到：

$A^T(A\vec{x^*} - \vec{b}) = \vec0$

把它展開：
$A^TA\vec{x^*} - A^T\vec{b} = \vec0$

移項：

:::success
\begin{equation}
A^TA\vec{x^*} = A^T\vec{b}
\end{equation}
:::

這個式子也叫做 normal equation，如果不知道推導的過程的話會覺得很神奇，因為它字面上的意思就是說：

>如果我們發現 $A\vec{x} = \vec{b}$ 沒有解，只要左右同乘 $A^T$ 就會有近似解了，還能保證這個近似解是最佳的近似解。

#### 當 A 行獨立時的公式

另外，當 <font color = "red">$A$ 行獨立</font>，$A^TA$ 就會可逆（有興趣可以翻閱課本看證明）因此存在 $(A^TA)^{-1}$ ，所以我們就可以把這個式子：

$A^TA\vec{x^*} = A^T\vec{b}$

>左右同乘 $(A^TA)^{-1}$：

$(A^TA)^{-1}A^TA\vec{x^*} = (A^TA)^{-1}A^T\vec{b}$

>左邊的 $(A^TA)^{-1}$ 和 $A^TA$ 消掉：

:::success
\begin{equation}
\vec{x^*} = (A^TA)^{-1}A^T\vec{b}
\end{equation}
:::

從這個式子我們就可以發現，在 $A$ 行獨立的情況下，$\vec{x^*}$ 是唯一的，但是如果 $A$ 行相依，代表說 $ker(A)$ 不是零空間，根據定理，$ker(A) = ker(A^TA)$，所以 $ker(A^TA)$ 也不是零空間（有除了零向量以外的向量在 $ker(A^TA)$ 中）

這代表我們可以把 $ker(A^TA)$ 中的任意向量加 $\vec{x^*}$ 去獲得許許多多的不同的解

> 舉例來說：
>
> 假設 $\vec{x^*}$ 是我們解 $A^TA\vec{x} = A^T\vec{b}$ 求除來的其中一個解
> 並且我們假設 $ker(A^TA) \not= \{\vec 0\}$
> $\vec x_1 \in ker(A^TA)$ 是 $ker(A^TA)$ 裡的任意一個向量
>
> $\because \vec x_1 \in ker(A^TA)$
> $\therefore A^TA\vec x_1 \ = \ \vec 0$
>
> 因為我們假設 $A^TA\vec{x^*} = A^T\vec{b}$，我們可把這個兩個式子相加，得到：
>
> $A^TA\vec{x^*} \ + \ A^TA\vec x_1 \ = \ A^T\vec{b} \ + \ \vec 0$
> $\rightarrow A^TA\vec{x^*} \ + \ A^TA\vec x_1 \ = \ A^T\vec{b}$
>
> 把左邊的 $A^TA$ 提出來：
> $\rightarrow A^TA\ (\vec{x^*} \ + \ \vec x_1) \ = \ A^T\vec{b}$
>
> 從這個式子可以發現， $\vec{x^*} \ + \ \vec x_1$ 也是一個解，因為我們對 $ker(A^TA)$ 裡的所有向量都可以重複這個做法去得到不同的解，所以只要 $ker(A^TA)$ 不是零空間，解就不唯一。

因此，結論就是如果 $A$ 行相依，normal equation 的解不唯一。

總之，如果題目問 least squares solution 且有特別說 $A$ 行獨立，我們就直接把 $\vec{b}$ 左乘 $(A^TA)^{-1}A^T$ 就是答案了；但如果 $A$ 沒有行獨立，就乖乖解 normal equation 就好。

---
## Reference
- Gilbert Strang (2006).Linear Algebra and Its Applications, 4/e
- [stanford lecture notes](https://math.stanford.edu/~jmadnick/R3.pdf)