新的求解超大規(guī)模最小二乘問題的隨機(jī)算法.pdf

1、最小二乘法是誤差擬合、模型估計(jì)的常用方法，在科學(xué)技術(shù)領(lǐng)域有廣泛的應(yīng)用．對(duì)于超大規(guī)模的最小二乘問題，在通常情況下得不到精確解，而利用傳統(tǒng)的矩陣分解方法在規(guī)模增大的情況下會(huì)大大增加求解時(shí)間和空間復(fù)雜度．隨著隨機(jī)算法的不斷成熟以及它所具有的簡(jiǎn)單快速的優(yōu)點(diǎn)，為不精確求解最小二乘問題提供了一種有效方法．本文主要介紹了一種新的隨機(jī)算法求解最小二乘問題．
　　一方面，本文首先介紹了求解最小二乘問題的隨機(jī)投影算法——Blendenpik算法及其在

2、求解過程中表現(xiàn)出來(lái)的優(yōu)勢(shì)，并指出其不能求解超大規(guī)模最小二乘問題的缺點(diǎn)．進(jìn)一步對(duì)此算法進(jìn)行改進(jìn)并提出通過對(duì)超大規(guī)模矩陣的行進(jìn)行隨機(jī)采樣，為了改進(jìn)矩陣的一致性，通過快速walsh-Hadamard變換對(duì)采樣后矩陣進(jìn)行變換，將矩陣的維數(shù)降低，最后，對(duì)新得到的最小二乘問題利用QR分解進(jìn)行求解．
　　另一方面，本文證明了新算法得到的解滿足誤差邊界，以及解的收斂性問題，并分析算法求解需要的時(shí)間和空間復(fù)雜度．最后，通過數(shù)值試驗(yàn)表明隨機(jī)采樣算法相