SLAM中的優化理論（一）——線性最小二乘

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

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

• 最小二乘問題的定義

• 正規方程求解

• 喬姆斯基分解法求解

• QR分解法求解

• 奇異值分解法求解

• 齊次方程的最小二乘

一. 問題的定義

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

轉化為數學表達式為:

其中 x 為模型中參數所組成的向量,e 通常被稱為殘差向量(residual vector).

現在假設我們的模型函數為 Ax,樣本為 b 且方程數大於未知量數則有:

轉化為最小二乘表達式為:

該方程通常可以通過正規方程、QR 分解、喬姆斯基分解(Cholesky decomposition)和奇異值分解(SVD)等方法求解。

二. 求解方法

2.1. 正規方程(Normal Equation)

將展開可以得到:

為了求解得到該方程的最優解(即最小值),我們可以求解其對於參數 x 的偏導數,並令其等於零:

化簡後得到:

以上被稱為最小二乘的正規方程(Normal Equation)。進一步求解可得到:

該結果亦可表示為矩陣的偽逆形式(偽逆為逆矩陣廣義形式,奇異陣或非方陣不存在逆矩陣,但可以求解其偽逆矩陣)

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

以下內容參考[1].

由於簡單的正規方程計算運算量,因此為了更快更穩定的求解,通常可以運用喬姆斯基分解進行求解。

對正規矩陣左側進行喬姆斯基分解有:

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

2.3. QR分解

以下圖片參考[4]

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

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

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

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

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

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

並且有滿足該數據的線性系統如下所示:

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

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

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

至此完成矩陣 A 的 QR 分解。

通過以上方法我們能夠求得 Q 和 R 矩陣,那麼如何通過他們解決最小二乘問題呢。

對於一個最小二乘問題我們有:

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

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

由此進一步我們有:

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

2.4. 奇異值分解(SVD)

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

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

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

三. 齊次方程的最小二乘

之前我們討論的最小二乘問題其形式都為Ax ? b = 0,如果問題形式發生改變,變為Ax = 0,那麼這樣的最小二乘問題應該如何求解呢?

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

現在對矩陣 A 進行 SVD 分解有:

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

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

我們可以發現,x 的值就為矩陣 V 的最後一列。

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

附:

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

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

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

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

以上內容如有謬誤還請告知.

文章來自博客園

「勤工儉學計劃」，給你一個真正0元學習IT技術的機會！

http://www.ujiuye.com/zt/qgjx/?wt.bd=fq37300j

找工作太難？不是你不行，我們來幫你！

http://www.ujiuye.com/zt/jyfc/?wt.bd=fq37300j

交流群：345648424

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！