線性系統的最小平方解（最佳化簡介）

本文要介紹是一個線性系統在不同限制下的最小平方解法。主要內容為 Multiple View Geometry in Computer Vision 書中的 Appendix 5。

Solution of linear equations

首先考慮要解的是 \(Ax=b\)，其中 \(A\) 是 \(m \times n\) 的矩陣，且 \(m>n\)、\(A\) 的 rank 為 \(n\)。由於 \(m>n\)，我們能找出的是一組 \(x\) 使得 \(\left \| Ax-b \right \|\) 最小。解法如下：

1. 將 A 用 SVD 分解成，因此 \(\left \| Ax-b \right \| = \left \| UDV^T x-b \right \|\) 
2. U 矩陣不改變線性系統的 norm，因此可寫成 \(\left \| DV^T x - U^Tb \right \|\)
3. 令 \(y = V^T x\)，\(b' = U^T b\)，則可寫成 \(\left \| Dy - b' \right \|\)
4. 由於 \(D\) 是個只有對角線上不為零的矩陣，整個系統可以看成此形式： \[ \begin{bmatrix} d_1 & & & \\ & d_2 & & \\ & & \ddots & \\ & & & d_n\\ & & \vdots & \\ & & 0 & \end{bmatrix} \begin{bmatrix} y_1\\ y_2\\ \vdots \\ y_n \end{bmatrix} = \begin{bmatrix} b'_1\\ b'_2\\ \vdots \\ b'_n\\ \vdots\\ b'_m\\ \end{bmatrix} \] 
5. 因此 \(y_i = b'_i / d_i\)，而解 \(x = Vy\)。
6. 在實務上有可能 \(A\) 的 rank 小於 \(n\)，則無唯一解。若不確定 rank，可以計算 \(d_i/d_0\) 跟一個很小的 \(\delta\) 做比較來決定是否將它視為零。 

Pseudo-inverse

一個對角線方陣 \(D\) 的 pseudo-inverse \(D^+\) 定義為： \[ D^+_{ii}= \left\{\begin{matrix} 0\quad \mathrm{if}\ D_{ii}=0\\ D_{ii}^{-1}\quad \mathrm{otherwise} \end{matrix}\right. \] 而 \(A\) 的 pseudo-inverse 定義為：\[A^+=VD^+U^T\]而一個線性系統 \(Ax=b\) 當 A 的 rank 為 n 時解即為 \(x = A^+b\)。（註：\(A^+b = VD^+U^Tb\)，這與上述的演算法完全相同。）

Normal equations

我們也可以用 normal equations 來解最小平方化問題，其中 \(A^T A\) 被稱為 normal matrix。此方法如下：

1. 式子為 \(A^TAx=A^Tb\)
2. 若 \(A^TA\) 的反矩陣存在，則 \(x = (A^TA)^{-1}A^Tb\)
3. 當 A 的 rank 為 n 時，\((A^TA)^{-1}A^T\) 即為 pseudo-inverse。

到目前為止我們有兩種方法來計算 pseudo-inverse。實務上我們會看 n 的大小，若 n 很小的話計算 \((A^TA)^{-1}\) 會比 SVD 還要快，反之則該使用 SVD 求解。

Solution of homogeneous equations

要解的問題是給定 \(A\)，要找到一組 \(x\) 使得 \(\left \| Ax \right \|\) 最小，但得滿足 \(\left \| x \right \|=1\) 的條件。推導如下：

1. \(A=UDV^T\)，則問題變成 \(\left \| UDV^Tx \right \|\)。
2. 由於 \(U\) 與 \(V^T\) 不影響 norm，因此我們可以當成解 \(\left \| DV^Tx \right \|\) 要滿足 \(\left \| V^Tx \right \|=1\) 的條件。
3. 令 \(V^Tx=y\)，則上式變成 \(\left \| Dy \right \|\)，條件變成 \(\left \| y \right \|=1\)。
4. 由於對角矩陣 \(D\) 的對角線上是由大至小排列，因此 \(y\) 的最佳解為 \((0,0,...0,1)^T\) 
5. 最後由於 \(x=Vy\)，因此 \(x\) 的解為 \(V\) 的最後一個 column。

Solution to constrained systems 

要解的問題是給定 \(A\)，要找到一組 \(x\) 使得 \(\left \| Ax \right \|\) 最小，但得滿足兩個條件：

1. \(\left \| x \right \|=1\)
2. \(Cx = 0\) 

思路如下：

1. 若 C 的 row 少於 column 數目，則補零使 C 成為方陣。
2. SVD 分解 \(C = UDV^T\)，並假設 C 的 rank 為 r。
3. C 的 row space 可由 V^T 的前 r 個 row 展開，而剩下的 row 就是 C 的 orthogonal complement。
4. 令 \(C^\perp \) 為 V 拿掉前面 r 個 column 的矩陣，則 \(CC^\perp=0\)。
5. 由於 \(Cx=0\)，因此 x 可由 \(C^\perp\) 的 column 展開，因此我們可以將 \(\left \| x \right \|\) 轉化成 \(\left \| C^\perp x' \right \|\)
6. 此問題變轉化成要找到一組 \(x'\) 使得 \(\left \| AC^\perp x' \right \|\) 最小，並滿足 \(x'\) 的 norm 為 1，即可用 Solution of homogeneous equations 來解。

More constrained minimization

要解的問題是給定 \(A\)，要找到一組 \(x\) 使得 \(\left \| Ax \right \|\) 最小，但得滿足兩個條件：

1. \(\left \| x \right \|=1\)
2. \(x = G \hat{x}\)，其中 \(G\) 為已知，\(\hat{x}\) 為未知

這個問題的技巧與上題相同。我們分解 \(G=UDV^T\)，並假設 \(G\) 的 rank 為 r。令 \(U'\) 為 \(U\) 的前 r 個 column，則 \(G\) 與 \(U'\) 的 column space 相同。因此我們轉化 \(x = U'x'\)，即可滿足條件 2，也因此能用 Solution of homogeneous equations 來解了。

Yet another minimization problem

要解的問題是給定 \(A\)，要找到一組 \(x\) 使得 \(\left \| Ax \right \|\) 最小，但得滿足 \(\left \| Cx \right \|=1\) 的條件。推導如下：  

1. 分解 \(C=UDV^T\)，\(\left \| UDV^Tx \right \| = 1\) 等價於 \(\left \| DV^Tx \right \| = 1\)。
2. 令 \(x' = V^Tx\)，則題目變成使得 \(\left \| AVx' \right \|\) 最小，條件是 \(\left \| Dx' \right \|=1\)，並再用 \(A'\) 替換 \(AV\)。
3. \(D\) 有 \(r\) 個非零值與 \(s\) 個零，而 \(r+s=n\)。因此對於 \(x_i\) 來說，當 \(i>r\) 時 \(x_i\) 對於 \(\left \| Dx' \right \|\) 沒任何影響。
   
4. 將 \(A'\) 拆成 \(A'_1\) 與 \(A'_2\)，\(A'_1\) 為 \(A'\) 的前 r 個 column，\(A'_2\) 為 \(A'\) 的後 s 個 column，則此問題轉化為：給定 \(A'_1, A'_2\)，要找到一組 \(x'_1, x'_2\) 使得 \(\left \| A'_1 x'_1 + A'_2 x'_2 \right \|\) 最小，但得滿足 \(\left \| D_1x'_1 \right \|=1\) 的條件。
5. 先解 \(x'_2\)，我們先當 \(A'_1 x'_1\) 為常數，則要解的式子為讓 \(\left \| A'_2 x'_2 - (- A'_1 x'_1) \right \|\) 最小，而解為 \( x'_2 = - A_{2}^{'+} ( A'_1 x'_1 )\)。
6. 再把 \(x'_2\) 代回去，可得 \(\left \| A'_1 x'_1 + A'_2  (- A_2^{'+}(A'_1 x'_1)) \right \|\)，也就是 \(\left \| (A_2^{'}A_2^{'+} - I)A'_1 x'_1 \right \|\)
7. 令 \(x_1'' = D_1 x'_1\)，代入上式，最終的問題轉化為：要找到一組 \(x_1''\) 使得 \(\left \| (A_2^{'}A_2^{'+} - I)A'_1 D_1^{-1} x''_1 \right \|\) 最小，但得滿足 \(\left \| x'' \right \|=1\) 的條件。
8. 上式可由 Solution of homogeneous equations 來解出答案。