最近想寫一篇系列博客比較系統(tǒng)的解釋一下 SLAM 中運用到的優(yōu)化理論相關內(nèi)容,包括線性最小二乘、非線性最小二乘、最小二乘工具的使用、最大似然與最小二 乘的關系以及矩陣的稀疏性等內(nèi)容。一方面是督促自己對這部分知識進行總結,另一方面也希望能夠對其他人有所幫助。由于內(nèi)容比較多希望能夠堅持寫完。

       本篇博客主要講解線性最小二乘問題，主要包括以下內(nèi)容：

  • 最小二乘問題的定義

  • 正規(guī)方程求解

  • 喬姆斯基分解法求解

  • QR分解法求解

  • 奇異值分解法求解

  • 齊次方程的最小二乘

一. 問題的定義

　　最小二乘問題通常可以表述為,通過搜集到的一些數(shù)據(jù)(獲取得到的樣本),對某一個模型進行擬合,并盡可能的使得模型結果和樣本達到某種程度上的最佳擬合:

　　轉化為數(shù)學表達式為:

　　其中 x 為模型中參數(shù)所組成的向量,e 通常被稱為殘差向量(residual vector).
　　現(xiàn)在假設我們的模型函數(shù)為 Ax,樣本為 b 且方程數(shù)大于未知量數(shù)則有:
　　轉化為最小二乘表達式為:
　　該方程通?？梢酝ㄟ^正規(guī)方程、QR 分解、喬姆斯基分解(Cholesky decomposition)和奇異值分解(SVD)等方法求解。

二. 求解方法

       2.1. 正規(guī)方程(Normal Equation)

將展開可以得到:
為了求解得到該方程的最優(yōu)解(即最小值),我們可以求解其對于參數(shù) x 的偏導數(shù),并令其等于零:
化簡后得到:
以上被稱為最小二乘的正規(guī)方程(Normal Equation)。進一步求解可得到:
該結果亦可表示為矩陣的偽逆形式(偽逆為逆矩陣廣義形式,奇異陣或非方陣不存在逆矩陣,但可以求解其偽逆矩陣)

       2.2. 喬姆斯基分解(Cholesky Decomposition)

以下內(nèi)容參考[1].
由于簡單的正規(guī)方程計算運算量,因此為了更快更穩(wěn)定的求解,通常可以運用喬姆斯基分解進行求解。
對正規(guī)矩陣左側進行喬姆斯基分解有:

該喬姆斯基分解會生成一個上三角矩陣 R ? 和它的轉置矩陣,所以我們能夠通過連續(xù)的向前和向后的替換來計算求解向量:

       2.3. QR分解

以下圖片參考[4]

　　QR 分解可以將矩陣分解稱為一個標準正交方陣和一個上三角矩陣的積:

QR 分解的計算方式有很多,以下以 Householder 變換為例進行分析。首先我們對基于 Householder 的 QR 分解進行簡單的分析,假設 A 為一個 5X4 的矩陣,我們用 X 表示這次變換未變化的元素,用+表示發(fā)生變換的元素則有:

  

以此類推,通過四次 Householder 變換就可以將矩陣 A 轉換為一個上三角矩陣,且若 A列不相關,則 R 為非奇異矩陣,則有:

那么具體到實際的運算中我們應該怎么通過 Householder 方法計算 QR 分解呢?首先我們先來回顧一下 Householder 變化,對于 Householder 變換我們有以下定義:

然后我們通過一個實際的計算例子來說明 Householder 的 QR 分解變化。案例參考[2]。假設現(xiàn)在我們有以下五個數(shù)據(jù):

(-1, 1), (-0.5, 0.5), (0, 0), (0.5, 0.5), (1.2)

并且有滿足該數(shù)據(jù)的線性系統(tǒng)如下所示:

　　首先我們隊第一列進行處理:

　　其中的√5為的值,然后我們可以通過公式計算得到

　　然后依次類推,對第二列和第三列進行求解:

至此完成矩陣 A 的 QR 分解。
通過以上方法我們能夠求得 Q 和 R 矩陣,那么如何通過他們解決最小二乘問題呢。
對于一個最小二乘問題我們有:

對 A 進行 QR 分解,我們能夠得到:

　　在這里我們將拆分為兩部分,Q1 代表最開始的 n 行,而 Q2 代表后面與零相乘的剩余部分。

由此進一步我們有:

該結果就為 QR 分解求解線性最小二乘的表達式。

       2.4. 奇異值分解(SVD)

以上形式的最小二乘問題還可以通過 SVD 分解的方法進行求解。對于我們對其中的矩陣 A 進行 SVD 分解有:

由于我們已經(jīng)假設問題為超定(m>n),因此有:

SVD 的求解方法總結如下,參考[3]. 

三. 齊次方程的最小二乘

之前我們討論的最小二乘問題其形式都為Ax ? b = 0,如果問題形式發(fā)生改變,變?yōu)?/span>Ax = 0,那么這樣的最小二乘問題應該如何求解呢?

Ax = 0形式的問題經(jīng)常出現(xiàn)在重建問題(reconstruction)中。我們期望找到方程Ax = 0中 x 不等于零的解。由于該方程的特殊形式我們會發(fā)現(xiàn)對于 x 不等于零的解我們乘上任意的尺度因子 k 使解變?yōu)?kx 都不會改變最終結果。因為我們可以將問題轉化為求解 x 使得||Ax||值最小并且||x||=1。

現(xiàn)在對矩陣 A 進行 SVD 分解有:

通過 SVD 分解中 D 矩陣的性質我們能夠發(fā)現(xiàn),D 為一個對角矩陣,且它的對角線元素呈降序排列。因此方程的解應該為:

該解在最后的位置有一個值為 1 的非零項。依據(jù)此結果,再根據(jù)方程:

我們可以發(fā)現(xiàn),x 的值就為矩陣 V 的最后一列。

-------------------------------------------------------------------------------------------------------------------------

附:

對于Ax=b, A為一個mXn的矩陣,其結果有以下三種可能性:

  • m<n, 未知數(shù)個數(shù)大于方程格式,在這種情況下不存在唯一解,但是存在一個解的向量集合;

  • m=n, 如果矩陣A可逆,存在唯一解;

  • m>n, 方程個數(shù)大于未知數(shù)個數(shù).通常情況下方程不會有解,除非b恰好位于矩陣A的列空間中;

 以上內(nèi)容如有謬誤還請告知.

 

參考內(nèi)容:

[1]. 使用Math.NET求解線性和非線性最小二乘問題

[2]. Least Squares Approximation/Optimization

[3]. Multiple View Geometry in Computer Vision, Appendix 5, Least-squares Minimization

[4]. 機器學習中的矩陣方法03：QR 分解

http://www.cnblogs.com/leexiaoming/p/7224781.html