[線性代數] 找擬合線上投影點 - Part1 - SVD解擬合線篇

二點可以完全確定一直線，而在資料點超過三點的情況時蠻有可能找不到一個完美直線讓所有資料點都能夠與某直線重合，此時只能找所謂的最佳解，合理的命題如下：

嘗試找到一直線，使所有資料點對此直線的距離的總和，是所有可能的解裡的最小值

設定欲求解的直線方程式以一般式（general form）表達：

$$ax+by+c=0$$

接著把每個已知資料點以齊次座標方式$(x_{i},y_{i},1)$表達，共n個資料點，裝載在同一矩陣裡：

$$
\begin{bmatrix}
x_1 & y_1 & 1 \\
x_2 & y_2 & 1 \\
\vdots \\
x_n & y_n & 1 \\
\end{bmatrix}
$$

因為資料點不見得落在線上，所以資料點套入$ax+by+c$後不見得為零，可能會有剩餘量$b_i$，因此命題可以被整理成矩陣形式：

$$
b=
\begin{bmatrix}
b_1 \\
b_2 \\
\vdots \\
b_n \\
\end{bmatrix}
=
\begin{bmatrix}
x_1 & y_1 & 1 \\
x_2 & y_2 & 1 \\
\vdots \\
x_n & y_n & 1 \\
\end{bmatrix}
\begin{bmatrix}
a \\
b \\
c
\end{bmatrix}
=
Ax
$$

目標至此很明確，我們要分析矩陣A的性質，找到一組x使得b的向量長度是所有可能解裡最小的，而分析矩陣的工具，首選SVD！（因為我只會這個）：

$$
A=
UDV^{T}=
\begin{bmatrix} u_{1} &
u_{2} & \cdots & u_{n}
\end{bmatrix}_{n \times n}

\begin{bmatrix} \sigma_1&0&0\\
0&\sigma_2 &0\\
0&0&\sigma_3 \\
0&0&0\\
\vdots
\end{bmatrix}_{n \times 3}

\begin{bmatrix} v_{1}\\
v_{2}\\
v_{3}
\end{bmatrix}_{3 \times 3}
$$

其中$ u_1 u_2 \cdots u_n $的維度個別都是 $ 1 \times n $，向量$v_1  v_2  v_3$的維度個別都是$ 1 \times 3 $

SVD分解的意義就是將定義域$R^m$肢解成標準正交基$v_1 \cdots v_m$，並用$D$矩陣表達表示各標準正交基在映射過程的放大倍率$\sigma_1 \cdots \sigma_n$；可以從$A$分解出的$D$矩陣看出，在資料點在超過3點時，$\sigma$至多只會有3個，也就是說，即便有n個$u_i$標準正交基底構成完整值域$R^n$，但對於A來說，映射在值域上的子空間最多只由3個正交基構成
（畢竟來源空間維度只有3，可以想成以3種元素交叉變換組合產生新的化合物，這些化合物們的構成元素至多只會有3種，某種程度像是數學上的物質不滅吧？）

由於$v_i u_i$標準正交基，長度皆為1，也就是說各組$v_i$投射到$R^n$空間的向量長度，完全是由$\sigma_i$所控制，所以我們又可以進一步轉換命題：

要選擇哪一組$v_i$，使得對應的$\sigma \times u_i$的向量長度最短呢？

問題至此，已經從最初的開放式題目透過SVD分解，變成選擇題，答案也十分明顯：

選擇最小的$\sigma$對應的$v_i$

假如最小的放大倍率為$\sigma_2$，則最小平方解就會是$v_2$，對應在$R^n$的向量則是$\sigma_2 \times u_2$（長度為$\sigma_2$的$u_2$向量），不過一般來說SVD分解後都會是以降冪形式排列，所以對應的最小平方解一般是$v_3$，最小殘餘量$b=\sigma_3 \times u_3$