本文要介紹是一個線性系統在不同限制下的最小平方解法。主要內容為 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 \|\) 最小。解法如下:
- 將 A 用 SVD 分解成,因此 \(\left \| Ax-b \right \| = \left \| UDV^T x-b \right \|\)
- U 矩陣不改變線性系統的 norm,因此可寫成 \(\left \| DV^T x - U^Tb \right \|\)
- 令 \(y = V^T x\),\(b' = U^T b\),則可寫成 \(\left \| Dy - b' \right \|\)
- 由於 \(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} \]
- 因此 \(y_i = b'_i / d_i\),而解 \(x = Vy\)。
- 在實務上有可能 \(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。此方法如下:
- 式子為 \(A^TAx=A^Tb\)
- 若 \(A^TA\) 的反矩陣存在,則 \(x = (A^TA)^{-1}A^Tb\)
- 當 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\) 的條件。推導如下:
- \(A=UDV^T\),則問題變成 \(\left \| UDV^Tx \right \|\)。
- 由於 \(U\) 與 \(V^T\) 不影響 norm,因此我們可以當成解 \(\left \| DV^Tx \right \|\) 要滿足 \(\left \| V^Tx \right \|=1\) 的條件。
- 令 \(V^Tx=y\),則上式變成 \(\left \| Dy \right \|\),條件變成 \(\left \| y \right \|=1\)。
- 由於對角矩陣 \(D\) 的對角線上是由大至小排列,因此 \(y\) 的最佳解為 \((0,0,...0,1)^T\)
- 最後由於 \(x=Vy\),因此 \(x\) 的解為 \(V\) 的最後一個 column。
Solution to constrained systems
要解的問題是給定 \(A\),要找到一組 \(x\) 使得 \(\left \| Ax \right \|\) 最小,但得滿足兩個條件:
- \(\left \| x \right \|=1\)
- \(Cx = 0\)
思路如下:
- 若 C 的 row 少於 column 數目,則補零使 C 成為方陣。
- SVD 分解 \(C = UDV^T\),並假設 C 的 rank 為 r。
- C 的 row space 可由 V^T 的前 r 個 row 展開,而剩下的 row 就是 C 的 orthogonal complement。
- 令 \(C^\perp \) 為 V 拿掉前面 r 個 column 的矩陣,則 \(CC^\perp=0\)。
- 由於 \(Cx=0\),因此 x 可由 \(C^\perp\) 的 column 展開,因此我們可以將 \(\left \| x \right \|\) 轉化成 \(\left \| C^\perp x' \right \|\)
- 此問題變轉化成要找到一組 \(x'\) 使得 \(\left \| AC^\perp x' \right \|\) 最小,並滿足 \(x'\) 的 norm 為 1,即可用 Solution of homogeneous equations 來解。
More constrained minimization
要解的問題是給定 \(A\),要找到一組 \(x\) 使得 \(\left \| Ax \right \|\) 最小,但得滿足兩個條件:
- \(\left \| x \right \|=1\)
- \(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\) 的條件。推導如下:
- 分解 \(C=UDV^T\),\(\left \| UDV^Tx \right \| = 1\) 等價於 \(\left \| DV^Tx \right \| = 1\)。
- 令 \(x' = V^Tx\),則題目變成使得 \(\left \| AVx' \right \|\) 最小,條件是 \(\left \| Dx' \right \|=1\),並再用 \(A'\) 替換 \(AV\)。
- \(D\) 有 \(r\) 個非零值與 \(s\) 個零,而 \(r+s=n\)。因此對於 \(x_i\) 來說,當 \(i>r\) 時 \(x_i\) 對於 \(\left \| Dx' \right \|\) 沒任何影響。
- 將 \(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\) 的條件。
- 先解 \(x'_2\),我們先當 \(A'_1 x'_1\) 為常數,則要解的式子為讓 \(\left \| A'_2 x'_2 - (- A'_1 x'_1) \right \|\) 最小,而解為 \( x'_2 = - A_{2}^{'+} ( A'_1 x'_1 )\)。
- 再把 \(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 \|\)
- 令 \(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\) 的條件。
- 上式可由 Solution of homogeneous equations 來解出答案。